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 <= d <= t, we have: For values of d <= 0 consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = -t. For values of d > 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 <= d <= t. The main result is that the necessary and sufficient number of rounds needed to solve uniform consensus for a condition C is an element of S-i([d]) (such that C is not an element of S-i([d-1])) is d + 1. In more detail, the paper presents a generic synchronous early-deciding uniform consensus protocol that enjoys the following properties. Let f be the number of actual crashes, I the input vector and C is an element of S-t([d]) the condition the protocol is instantiated with. The protocol terminates in two rounds when I is an element of C and f <= t - d, and in at most d + 1 rounds when I is an element of C and f > 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])).