The Synchronous Condition-Based Consensus Hierarchy

Authors

Achour Mostefaoui, Universite de Rennes
Sergio Rajsbaum, UNAM
Michel Raynal, Universite de Rennes

Abstract

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:

For values of "$d \leq 0$" consensus is solvable in an asynchronous system with "$t$" failures, and we get a hierarchy of conditions (we introduced in PODC'01) that allows us to solve asynchronous consensus with more and more efficient protocols as we go from "$d=0$" to "$d=-t$".
For values of "$d > 0$" consensus is not solvable in an asynchronous system with "$t$" failures, but we get a hierarchy of conditions that allows us to solve synchronous consensus with protocols that take more and more rounds, as we go from "$d=1$" (two rounds) to "$d=t$" ("$t+1$" rounds).
"$d=0$" is the borderline case where consensus is solvable in an asynchronous system with $t$ failures, and optimally in a synchronous system.

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]}$").