Guest Speaker: Annie Liu
Abstract: This talk examines well-known algorithms for distributed consensusproblems, from classical consensus to blockchain consensus. We discuss
exact algorithms that are high-level as in pseudocode and directly
executable as programs at the same time, focusing on how to quickly
program, configure, run, and check these algorithms as well as distributed
algorithms and systems in general. The talk consists of five parts:
1. An introduction to different distributed consensus problems, from
classical consensus to Byzantine consensus to blockchain consensus.
2. An overview of well-known algorithms, from Paxos for classical consensus
to the Bitcoin algorithm for blockchain consensus, including important
variants such as Viewstamped Replication and Virtual Synchrony, as well
as Proof-of-Stake vs. Proof-of-Work and Byzantine fault tolerance (BFT)
protocols.
3. An overview of a method and language, DistAlgo, for expressing
distributed algorithms precisely at a high-level as pseudocode and
having them be directly executable at the same time, and be easily
configured and checked for safety and liveness properties.
4. A study of exact algorithms expressed at a high level for the most
extensively studied algorithm variants, including Lamport's Paxos for
classical consensus, Nakamoto's Bitcoin algorithm for blockchain
consensus, and more recent BFT protocols, focusing on their exact
programming, configuration, execution, and checking.
5. A demo of direct execution and checking of these algorithms running as
distributed processes.
Additional information on DistAlgo can be found at
https://distalgo.cs.stonybrook
