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