Tutorial at PODC 2021: Byzantine Agreement and Leader Election: From Classical to the Modern

Friday, July 30 at 15:00 – 18:00 CEST

Brief Abstract. In this three-part tutorial, we will present the fundamentals of Byzantine agreement and leader election problems from a modern perspective that is largely inspired by recent P2P applications like Blockchain and cryptocurrencies. In the first part, we will present the historic foundations of Byzantine agreement and leader election and describe the fundamentals that underlie our modern understanding of these problems. Motivated by sparse real-world distributed networks such as peer-to-peer (P2P) networks, our second part will focus on Byzantine resilient protocols for sparse networks. Our final part will be on dynamic networks aimed at addressing nodes continuously joining and leaving P2P networks.

Registration is free at the PODC web site.

Part 1: Classical Byzantine Agreement (by Anisur Rahaman Molla)

This part will focus on both classical and recent results on Byzantine agreement and leader election focusing on complete networks.

Distributed network models and formulation of Byzantine agreement and leader election problems.
Fundamental bounds on efficiency and fault-tolerance.
Fundamental algorithms for Byzantine agreement and leader election.
Contrasting classical Byzantine protocols with protocols used in modern blockchain and crytocurrency systems.

Part 1 Slides

Part 2: Byzantine protocols in Sparse Networks (by Gopal Pandurangan)

Motivated by modern real-world networks such as P2P networks which are sparse and bounded degree the second part will focus on results and techniques for Byzantine resilient protocols on sparse networks.

A history of Byzantine algorithms for sparse networks.
Efficient algorithms for Byzantine agreement in sparse networks.
Efficient algorithms for Byzantine leader election in sparse networks.

Part 2 Slides

Part 3: Byzantine Protocols for Dynamic Networks (by John Augustine)

Real-world networks such as P2P networks are inherently very dynamic — nodes and/or edges are deleted or added constantly over time. The third part will focus on dynamic peer-to-peer networks and discuss Byzantine protocols on such networks.

Dynamic network model for P2P networks.
Techniques for designing and analyzing dynamic network algorithms.
Byzantine agreement in dynamic networks.
Byzantine leader election in dynamic networks.

Part 3 Slides