The Synchronous Condition-Based Consensus Hierarchy



The condition-based approach studies restrictions on the inputs of a distributed problem, called conditions, that make it solvable, or (if it is solvable without restricting its inputs) allow the design of more efficient solutions. Previous work studied conditions for consensus and other agreement problems, mostly in the context of asynchronous systems made up of n processes where at most " 1 <= t < n" can crash. This paper considers the condition-based approach in the context of synchronous systems. It first introduces a full classification of conditions for consensus, establishing a discrete range between the asynchronous and synchronous models, with the following hierarchy "$ {\cal S}_t^{[-t]}\subset\cdots\subset {\cal S}_t^{[0]}\subset\cdots\subset {\cal S}_t^{[t]} $" where "${\cal S}_t^{[t]}$" includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition "$C \in{\cal S}_t^{[d]}$", "$-t \leq d \leq t$", we have:

After having introduced the hierarchy of conditions for synchronous systems (i.e., for "$d > 0$"), the paper presents a generic synchronous early-deciding uniform consensus protocol. This protocol enjoys the following noteworthy property: when instantiated with a condition "$C \in {\cal S}_t^{[d]}$" ("$1\leq d \leq t < n$"), the processes decide in at most "min$(\alpha+1,f+2,t+1)$", where "$f$" is the number of actual crashes, and "$\alpha=d$" if the input vector belongs to "$C$", or "$\alpha=+\infty$" otherwise. Finally, the paper establishes a corresponding lower bound stating that at least "$d+1$" rounds are necessary to get a decision when the input vector belong to "$C$" (with "$C \in {\cal S}_t^{[d]}$").