Synchronous Byzantine Agreement Protocols

The synchronous model (a known bound on message delay) is the natural starting point because protocols are simplest here — a party can safely conclude “if I haven’t heard from you by round $k$, I never will.” The Phase-King protocol is the classic textbook Byzantine agreement protocol for this model; Dolev-Strong authenticated broadcast achieves broadcast with a PKI (digital signatures), tolerating any number of corruptions (no threshold needed) by having parties relay and collect signatures. Crusader Broadcast is a weaker but useful non-equivocation primitive (with a PKI) that several later protocols build on. Covers modern, more practical synchronous protocols — Sync HotStuff and an optimistically responsive variant (fast when the network happens to be fast, not just when it’s guaranteed to be), the streamlined Streamlet protocol, and a survey of the authenticated-protocol landscape — plus a recursive technique achieving asymptotically optimal communication, the use of randomization for crash/omission (rather than Byzantine) failures, and Scalable Agreement, which achieves near-linear expected communication and constant expected time against a weak adaptive omission adversary.

Outline (TODO — flesh out each)

• The synchronous model
• The Phase-King protocol
• The Dolev-Strong authenticated broadcast protocol
• Crusader Broadcast (non-equivocation with a PKI)
• Sync HotStuff
• An optimal optimistically responsive synchronous protocol
• Streamlet
• Survey of authenticated synchronous protocols
• Recursion for optimal communication complexity
• Randomization for crash and omission failures
• Scalable Agreement