Easy impossibility proofs for distributed consensus problems

Paper: Easy impossibility proofs for distributed consensus problems. Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. 1986

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

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