Easy impossibility proofs for distributed consensus problems

Paper: [1]

This paper gives impossibility results.

  1. Byzantine Agreement
  2. Weak Agreement
  3. Byzantine Firing Squad
  4. Approximate Agreement
  5. Clock Synchronization

To tolerate \(f\) faults, we need \(>3f\) nodes and \(2f+1\) connectivity. Assume deterministic (Locality Axiom) and no PKI + Byzantine (Fault Axiom).

Definitions

  • Inadequate graphs: If the connectivity is less than \(2f+1\).

References

[1] Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. 1986. “Easy impossibility proofs for distributed consensus problems.” https://doi.org/10.1007/BF01843568.