Synchronous condition-based consensus
The condition-based approach studies restrictions on the inputs to a distributed problem, called conditions, that facilitate its solution. Previous work considered mostly the asynchronous model of computation. This paper studies conditions for consensus in a synchronous system where processes can fail by crashing. It describes a full classification of conditions for consensus, establishing a continuum between the asynchronous and synchronous models, with the following hierarchy S-t([-i]) subset of (...) S-t([0]) subset of (...) subset of S-t([i]) where S-t([i]) includes all conditions (and in particular the trivial one made up of all possible input vectors). For a con dition C E St, t   0 consensus is known not solvable in an asynchronous system with t failures, but we obtain a hierarchy of conditions that allows solving synchronous consensus with protocols that can take more and more rounds, as we go from d = 0 to d = t. d = 0 is the borderline case where consensus can be solved in an asynchronous system with t failures, and can be solved optimally in a synchronous system. After having established the complete hierarchy, the paper concentrates on the two last items: 0   t - d. (It also terminates in one round when I is an element of C and d = f = 0.) Moreover, whether I belongs or not to C, no process requires more than min(t + 1, f + 2) rounds to decide. The paper then proves a corresponding lower bound stating that at least d + I rounds are necessary to get a decision in the worst case when I is an element of C (for C is an element of S-t([d]) and C is not an element of S-t([d-1])).
consensus input vector early deciding process crash failure synchronous distributed system