The Weak Byzantine Generals Problem

Original paper: The Weak Byzantine Generals Problem. L. Lamport. 1983

Summary

  • Presents the definition of weak Byzantine Generals
  • In BG, if broadcaster is honest, then all non-faulty nodes output broadcaster's value
  • In WBG, if all processes are non-faulty, then every process i obtains the broadcaster's value
  • TODO: Section 2 result
  • They present a protocol that works for any number of faults but may send infinite messages
  • If you further relax WBG to allow approximate agreement, then there this is a finite algorithm for any \(t
  • Network: Synchrony
  • Unauthenticated
  • They also present the weak interactive consistency problem

Notes

  • Transaction Commit Problem is WBG

References

L. Lamport. 1983. “The Weak Byzantine Generals Problem.” https://dl.acm.org/doi/10.1145/2402.322398.