Efficient Condition-Based Consensus.
Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Matthieu Roy · 2001
The condition-based approach for consensus solvability (that we have introduced in a previous paper, ACM STOC'01) consists in identifying sets of input vectors for which it is possible to design a protocol solving the consensus problem for n processes despite the occurrence of up to f process crashes. For each value of f these conditions actually define a hierarchy. This paper continues our investigation of this approach. It has three main contributions. It first show that it is possible to define conditions from very simple weight functions. Interestingly any weight function defines an acceptable condition, i.e., a condition that allows to solve the consensus problem. The second contribution is an efficient protocol whose wait-free part has a number of shared memory accesses upper bounded by O(n log 2 (f 1)) (actually, according to the vector and the number of actual crashes, this upper bound is rarely attained). A process that decides by itself, has to write the value it decides in shared memory in order to help decide processes that cannot decide by themselves. The third contribution of the paper is the study of conditions that allow processes to save this write. When this occurs, the only write to shared memory by a process is the initial write of the value it proposes.