This tutorial describes well-known algorithms for distributed consensus problems, from classical consensus to blockchain consensus, and discusses exact algorithms that are high-level as in pseudocode and directly executable at the same time. The tutorial consists of five parts:

  1. A introduction to different distributed consensus problems, from classical consensus and 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.

  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.

  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 and Nakamoto's Bitcoin algorithm for blockchain consensus.

  5. A demo of the direct execution of these exact algorithms by distributed processes.

Additional information and materials for the workshop will be made available here (at http://darlab.cs.stonybrook.edu/consensus), including slides and executable algorithms/programs.

  . slides, containing complete executable specification (DistAlgo program) for Bitcoin backbone protocol.

  . paxos, containing complete executable specifications (DistAlgo programs) for Paxos variants in the slides, including for Basic Paxos and for Multi-Paxos with preemption, replicated state machine, and reconfiguration and optimized with state reduction and failure detection (as well as TLA+ specification and machine-checked TLAPS proof for the latter).


Distributed consensus is at the core of distributed systems and services, which are increasingly indispensable in daily life.

  . There is an increasing interest in algorithms for both classical consensus and blockchain consensus, especially the exact algorithms for deeper understanding and possible improvements by researchers, practitioners, and students.

  . Especially desired are also languages and methods for expressing distributed algorithms and protocols precisely at a very high level, to facilitate the design and implementation, as well as analysis and verification, of these algorithms and protocols.


DistAlgo minimally extends the Python programming languages for expressing distributed algorithms at a high level.

  . DistAlgo has been used to express a wide variety of important distributed algorithms, including over a dozen well-known algorithms and variants for classical consensus and blockchain consensus.

  . DistAlgo has been used by hundreds of students in graduate and undergraduate courses in dozens of different course projects, implementing the core of network protocols, distributed graph algorithms, distributed coordination services, distributed hash tables, distributed file systems, distributed databases, parallel processing platforms, security protocols, and more.

  . The algorithms and systems can be programmed much more easily and clearly compared to using conventional programming languages, e.g., in 30 lines instead of 300 lines, not to mention 3000 lines or more.


The tutorial content is based on our studies of distributed algorithms, e.g., [1,2], as well as many more algorithms studied in our ongoing research project, From Clarity to Efficiency for Distributed Algorithms, e.g., [3,4], after a dedicated workshop on Languages for Distributed Algorithms organized by Black and Liu (http://sites.google.com/site/ladameeting)

[1] Y.A. Liu, S. Chand, and S.D. Stoller. Moderately Complex Paxos Made Simple: High-Level Executable Specification of Distributed Algorithm. In Proc. 21st International Symposium on Principles and Practice of Declarative Programming (PPDP), Oct. 2019, ACM Press. (https://arxiv.org/pdf/1704.00082v4.pdf)

[2] Y.A. Liu, Logical Clocks Are Not Fair: What Is Fair? A Case Study of High-level Language and Optimization. In Proc. Workshop on Advanced Tools, Programming Languages, and Platforms for Implementing and Evaluating Algorithms for Distributed Systems (APPLIED), pages 21-27, July 2018, ACM Press. (http://www.cs.stonybrook.edu/~liu/papers/LclockUnfair-APPLIED18.pdf)

[3] Y.A. Liu, S.D. Stoller, B. Lin, and M. Gorbovitski. From Clarity to Efficiency for Distributed Algorithms. In Proc. 27th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA), pages 395-410, Oct. 2012. (http://www.cs.stonybrook.edu/~liu/papers/DistPL-OOPSLA12.pdf)

      Extended description of DistAlgo language and method appears in ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 39, Number 3, May 2017. (https://arxiv.org/pdf/1412.8461v3.pdf)

      Open-source implementation is available on github and sourceforge, version 1.0 released Nov. 2016. (http://distalgo.cs.stonybrook.edu/)

[4] Y.A. Liu, S.D. Stoller, and B. Lin. High-Level Executable Specifications of Distributed Algorithms. In Proc. 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), volume 7596 of LNCS, pages 95-110, Oct. 2012. (http://www.cs.stonybrook.edu/~liu/papers/DistSpec-SSS12.pdf)

      This paper received the Best Student Paper Award.