The Gap in Circumventing the Consensus Impossibility

Rachid Guerraoui, Petr KouznetsovInfoscience 2004

Abstract

The seminal impossibility of reaching consensus in an asynchronous and crash-prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value out of two possible values 0 or 1. On the other hand, abstractions that were shown to be, in some precise sense, minimal to circumvent the impossibility were determined for a stronger variant of the problem, called consensus, where the processes need to decide on one of the values they initially propose (0 or 1). This paper addresses the question of whether these abstractions were actually also minimal to circumvent the impossibility of weak consensus. We first show that any deterministic object type that implements weak consensus also implements consensus. Then we exhibit a non-deterministic type that implements weak consensus, among any number of processes, but not consensus, even among two processes. In modern terminology, this type has consensus power 1 and weak consensus power ∞. Finally, we exhibit a failure detector that implements weak consensus but not consensus.

Introduction

In the realm of distributed computing, the Consensus problem is a cornerstone of reliability. It requires a group of independent processes to agree on a single value despite the potential for process crashes. However, the famous Fischer, Lynch, and Paterson (FLP) impossibility result proved that in a purely asynchronous system, achieving consensus is impossible if even one process might fail.

To bypass this barrier, researchers have historically introduced "minimal" abstractions, such as specialized hardware primitives (e.g., Compare-and-Swap) or failure detectors (oracles that provide hints about which processes have crashed). This paper investigates a fundamental nuance: does the definition of the consensus problem itself change the power required from these abstractions? Specifically, the authors explore the computational gap between Strong Consensus and Weak Consensus.

Defining the Variants

To understand the gap, one must first distinguish between the two variants of the problem:

  1. Consensus (Strong): Processes must agree on a value (0 or 1), and that value must be one of the values originally proposed by a process.
  2. Weak Consensus: Processes must agree on a value (0 or 1). The only constraint is that both 0 and 1 must be possible outcomes in different executions of the system (to prevent trivial solutions where everyone always decides 0).

The central question is whether the tools required to solve the Strong version are also strictly necessary for the Weak version, or if there exists a middle ground where a tool is powerful enough for Weak Consensus but insufficient for the Strong variant.

Determinism as a Leveler

The authors first examine systems restricted to deterministic objects, such as standard registers, queues, or stacks. Using the concept of "valence"—the set of possible future decision values from a given system state—they prove that for deterministic building blocks, no gap exists.

Theorem 3 of the paper establishes that any set of deterministic types capable of solving Weak Consensus can also be used to solve Strong Consensus. In this context, the "Consensus Hierarchy" (which ranks the power of synchronization primitives) remains identical for both problems. If you are limited to deterministic tools, the distinction between Weak and Strong Consensus is computationally irrelevant.

The "Rambler" Paradox and Non-Determinism

The landscape changes dramatically when non-deterministic objects are introduced. The authors construct a novel object type called the rambler. The rambler is designed such that processes cannot use it to communicate their proposed values to one another; it effectively prevents meaningful information transfer.

Surprisingly, the authors prove (Theorem 6) that the rambler has "Weak Consensus Power ∞" but "Consensus Power 1." This means the rambler can solve Weak Consensus for any number of processes, yet it is as useless as a simple read/write register for solving Strong Consensus, even for just two processes.

This paradox highlights a deep theoretical insight: Strong Consensus is fundamentally about information transfer (ensuring the decision matches a proposal), whereas Weak Consensus is merely about coordination (ensuring everyone picks the same side). The rambler allows for coordination through its internal state transitions without allowing the processes to "fetch" the specific values proposed by their peers.

Failure Detector Gaps

The paper extends this investigation to failure detectors. Traditionally, failure detectors were defined based on properties of single executions. However, because Weak Consensus is defined by properties across a set of possible executions, the authors had to refine the existing formalism to accurately compare the two problems.

They demonstrate that $\Omega$—the failure detector long considered the "weakest" oracle for solving Strong Consensus—is not the weakest for Weak Consensus. They exhibit a specific failure detector, $\mathcal{Y}(F_0, F_1)$, which is strictly weaker than $\Omega$ but remains sufficient to solve the Weak Consensus problem. This proves that the "minimal" requirements to circumvent FLP impossibility depend heavily on which version of consensus is being targeted.

Conclusion

This research reveals that the equivalence of Weak and Strong Consensus is an artifact of determinism. In a world of non-deterministic objects and failure oracles, a significant gap emerges. While the authors have successfully mapped the existence of this gap, the "bottom" of the failure detector hierarchy for Weak Consensus remains an open question. Future work is needed to identify the absolute weakest possible failure detector for Weak Consensus and to determine if these gaps persist in other failure models, such as Byzantine environments.

Summary updated

Abstract

The seminal impossibility of reaching consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value out of two possible values 0 or 1. On the other hand, abstractions that were shown to be, in some precise sense, minimal to circumvent the impossibility were determined for a stronger variant of the problem, called consensus, where the processes need to decide on one of the values they initially propose (0 or 1). These abstractions include synchronization primitives, namely shared object types, as well as failure detector oracles. This paper addresses the question of whether these abstractions were actually also minimal to circumvent the impossibility of weak consensus. We first show that any deterministic object type that implements weak consensus also implements consensus. Then we exhibit a non-deterministic type that implements weak consensus, among any number of processes, but not consensus, even among two processes. In modern terminology, this type has consensus power 1 and weak consensus power ∞. Finally, we exhibit a failure detector that implements weak consensus but not consensus.
BibTeX
@inproceedings{guerraoui2004gap,
  author = {Rachid Guerraoui and Petr Kouznetsov},
  title = {{The Gap in Circumventing the Consensus Impossibility}},
  booktitle = {Infoscience},
  year = {2004},
}

Loading related content...

Figure