Binary Consensus

Summary

Binary consensus (also called binary Byzantine agreement) is a distributed protocol where \(n\) parties, each holding an input \(v_i \in \{0, 1\}\), must agree on a common output bit. First solved by Ben-Or [1] in 1983 using randomization to circumvent the FLP impossibility result, which shows that no deterministic asynchronous protocol can solve consensus with even one crash fault.

Formal Definition

A protocol among \(n\) parties, of which at most \(t\) may be faulty, solves binary consensus if the following hold:

  • Agreement: all honest parties output the same value \(v \in \{0, 1\}\).
  • Validity: if all honest parties have the same input \(v_i = v\), then the output must be \(v\).
  • Termination: all honest parties eventually output a value.

Bounds

Impossibility

  • No deterministic protocol solves binary consensus in the asynchronous model with even \(t = 1\) crash fault (FLP impossibility).

Resilience

  • Asynchronous, Byzantine: \(t < n/3\) is tight. Achieved by Bracha [2].
  • Asynchronous, crash: \(t < n/2\).
  • Synchronous, Byzantine: \(t < n/3\) without signatures, \(t < n\) with signatures.

Round complexity

  • Deterministic synchronous protocols require at least \(t + 1\) rounds.
  • Randomized protocols circumvent this: Ben-Or [1] achieves constant expected rounds for \(t = O(\sqrt{n})\) in the synchronous setting.

Communication

  • Mostefaoui et al. [3] achieve \(O(n^2)\) messages and \(O(1)\) expected time for asynchronous Byzantine with \(t < n/3\), signature-free.

Notes

  • Ben-Or's original async Byzantine protocol tolerates \(t < n/5\) with exponential expected running time [1]. Bracha [2] improved the resilience to the optimal \(t < n/3\).
  • Binary consensus is a fundamental building block for multi-valued consensus, validated Byzantine agreement, and asynchronous common coin protocols.

References

[1] Michael Ben-Or. 1983. “Another advantage of free choice (Extended Abstract).” https://dl.acm.org/doi/abs/10.1145/800221.806707.
[2] Gabriel Bracha. 1984. “An asynchronous [(n - 1)/3]-resilient consensus protocol.” http://portal.acm.org/citation.cfm?doid=800222.806743.
[3] Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. 2015. “Signature-Free Asynchronous Binary Byzantine Consensus with t $ n/3, O(n2) Messages, and O(1) Expected Time.” https://doi.org/10.1145/2785953.