ZZ - Distributed Consensus Reading List

• [Theoretical results](#theoretical-results)
• [Surveys](#surveys)
• [Algorithms for consensus](#algorithms-for-consensus)
• [Consensus for specialist hardware](#consensus-for-specialist-hardware)
• [Consensus for geo-distributed systems](#consensus-for-geo-distributed-systems)
• [Consensus in production](#consensus-in-production)
• [Implementations of consensus](#implementations-of-consensus)
• [Evaluations of consensus](#evaluations-of-consensus)
• [State machine replication](#state-machine-replication)
• [Reconfiguration](#reconfiguration)

• [Weaker consistency models](#weaker-consistency-models)
• [Failures](#failures)
• [Clocks](#clocks)
• [Correctness of consensus algorithms](#correctness-of-consensus-algorithms)
• [Quorum systems](#quorum-systems)
• [Byzantine fault tolerance](#byzantine-fault-tolerance)
  • [BFT surveys](#bft-surveys)
  • [BFT in theory](#bft-in-theory)
  • [BFT in practice](#bft-in-practice)
• [Alternative fault models in distributed consensus](#alternative-fault-models-in-distributed-consensus)
• [Misc](#misc)

• [Blogroll](#blogroll)
• [Reading lists](#reading-lists)
• [Academic conferences & symposiums](#academic-conferences–symposiums)
• [Academic workshops](#academic-workshops)
• [Academic journals & magazines](#academic-journals–magazines)

## Distributed Consensus

### Theoretical results This section lists theoretical results relating to distributed consensus.

• Easily one of the most influential papers in distributed computing. Introduces the "happens-before" relation and [Lamport clocks](https://en.wikipedia.org/wiki/Lamport_timestamp).

• Precursor to Paxos, notes on achieving fault-tolerance with some degree of clock synchronization.

• The famous FLP result, proving that distributed consensus algorithms need synchrony to guarantee progress.

• Follow up to the FLP result with some extra considerations

• Featured in [the morning paper](https://blog.acolyer.org/2016/02/09/the-heard-of-model/)

### Surveys This section lists surveys, tutorials, and systemization of knowledge papers covering distributed consensus algorithms.

• Describes single-degree Paxos as well as Multi-Paxos for SMR
• Is much more readable than the original Paxos paper
• Featured in [the morning paper](https://blog.acolyer.org/2015/03/04/paxos-made-simple/)

• Featured in [the morning paper](https://blog.acolyer.org/2015/03/11/vive-la-difference-paxos-vs-viewstamped-replication-vs-zab/)

### Algorithms for consensus This section lists papers describing algorithms for distributed consensus. These papers tend to be theory papers (venues such as PODC, DISC, OPODIS) whereas the [Implementations of consensus](#implementations-of-consensus) section focuses on systems papers.

• As known as the Ben-Or algorithm

• Featured in [the morning paper](https://blog.acolyer.org/2015/03/02/viewstamped-replication-a-new-primary-copy-method-to-support-highly-available-distributed-systems/)

• The original paper introducing Paxos
• Featured in [the morning paper](https://blog.acolyer.org/2015/03/03/the-part-time-parliament/)

• This paper describes how to replace acceptors in Paxos with disks
• Each disk is divided into blocks, one for each proposer. Each proposer may only write to its own block and read from other blocks, which they do in each of the two usual Paxos phases
• Each block contains the rough equivalent to last promised ballot number and last accepted proposal for the assigned proposer

• This paper makes Disk Paxos more “Paxos like” by assuming the disks support more operations e.g. conditional write
• ADP claims that Disk Paxos requires a fixed set of proposers and that ADP fixes this.

• Introduces the idea of deciding a partial ordering of values instead of a total ordering

• Variant of Paxos where proposers can bypass the leader by allowing multiple values to be proposed in the same ballot. This requires stronger quorums intersection, e.g. fast paxos needs 3/4 of acceptors (instead of a simple majority) to provide the same liveness guarantees as classic Paxos.

• Featured in [the morning paper](https://blog.acolyer.org/2016/01/13/consensus-on-transaction-commit/)

• Variant of Paxos which replaces the one leader with a group of leaders. Clients send operations to all leaders and they all propose values to the acceptors. Acceptors only accept a value if they have received proposals from a quorum of leaders. Similar to the non-equivocation phase in BFT. Liveness now does not depend on the leader.

• Featured in [the morning paper](https://blog.acolyer.org/2015/03/06/viewstamped-replication-revisited/)

• Extends the idea of master read leases to allow the master to promise to use a specified subset of acceptors in every majority quorum. Acceptors in this quorum can then serve reads locally.
• Similar to master read leases, it relies on clock synchrony.

• Featured in [the morning paper](https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-intersection-revisited/)

• Consensus algorithm which permits multiple proposals in the same round (similar to Fast Paxos) but uses two phases instead of larger quorums.

### Consensus for specialist hardware This section lists papers describing consensus algorithms using specialist hardware such as [SDN](https://en.wikipedia.org/wiki/Software-defined_networking), [IP-multicast](https://en.wikipedia.org/wiki/IP_multicast), or [RDMA](https://en.wikipedia.org/wiki/Remote_direct_memory_access).

• Featured in [the morning paper](https://blog.acolyer.org/2015/05/05/taming-uncertainty-in-distributed-systems-with-help-from-the-network/)

• Featured in [the morning paper](https://blog.acolyer.org/2016/09/28/distributed-consensus-and-the-implications-of-nvm-on-database-management-systems/)

• P4xos is also evaluated in The Case For In-Network Computing On Demand [[acmdl](https://dl.acm.org/citation.cfm?id=3303979),[pdf](https://www.inf.usi.ch/faculty/soule/pubs/eurosys2019.pdf),[code](https://github.com/P4xos/P4xos)]

• Derecho: Group Communication at the Speed of Light, Unpublished [[pdf](https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/Derecho-Protocols.pdf)]
• Groups, Subgroups and Auto-Sharding in Derecho: A Customizable RDMA Framework for Highly Available Cloud Services, Unpublished [[pdf](https://pdfs.semanticscholar.org/5dc4/ac5ac578fae726adcc5776d2a277f09dd9b5.pdf?_ga=2.198677487.1756250239.1559555537-1469340531.1559555537)]

• Featured in [the morning paper](https://blog.acolyer.org/2018/04/30/netchain-scale-free-sub-rtt-coordination/)

• SMR over [Trusted Execution Environments (TEEs)](https://en.wikipedia.org/wiki/Trusted_execution_environment).

### Consensus for geo-distributed systems This section covers papers describing consensus algorithms for WANs and/or geo-replicated systems. Many of these algorithms (such as [EPaxos](https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf)) are leaderless and decide a partial-ordering over values instead of the more traditional total-ordering approach.

• This paper describes EPaxos, which realizes [Generalized Paxos](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2005-33.pdf) and makes some further improvements (e.g. reducing the size of fast quorums by 1).

• Related blog post, [Modelling Paxos performance in wide area](http://charap.co/modeling-paxos-performance-in-wide-area-part-3/)

• Implements an optimization to EPaxos

• Describes Tempo, a leaderless partial ordering protocol that uses timestamp ordering.

### Consensus in production This section lists papers describing experiences of deploying distributed consensus in production.

• Featured in [the morning paper](https://blog.acolyer.org/2015/02/13/the-chubby-lock-service-for-loosely-coupled-distributed-systems/)

• Featured in [the morning paper](https://blog.acolyer.org/2015/03/05/paxos-made-live/)

• Featured in [the morning paper](https://blog.acolyer.org/2015/01/27/zookeeper-wait-free-coordination-for-internet-scale-systems/)

• Megastore uses SMR with witnesses, replicas that participate in log replication but do not run a state machine and read-only replicas that only run a state machine. This paper seems to use an unusual definition of Multi-Paxos where each instance is district but the 1a/1b messages for slot i is piggybacked onto 2a2/b for slot i-1.

• Widely utilized Apache licensed open source project written in Java [project website](https://zookeeper.apache.org)
• [Apache Kafka](https://kafka.apache.org) uses Zookeeper, as well as its own replication protocol, by described [here](https://www.confluent.io/blog/distributed-consensus-reloaded-apache-zookeeper-and-replication-in-kafka/). This is no longer true.
• Architecture is similar to Google's Chubby but unlike Chubby is described in detail and is open source
• Writes are linearizable, reads may be stale. Note: calling sync before a read doesn't make it linearizable
• Clients may have multiple outstanding requests, they will be handled FIFO
• Uses primary-backup replication instead of state machine replication
• Featured in [the morning paper](https://blog.acolyer.org/2015/03/09/zab-high-performance-broadcast-for-primary-backup-systems/)

• Featured in [the morning paper](https://blog.acolyer.org/2015/05/07/large-scale-cluster-management-at-google-with-borg/)

• Featured in [the morning paper](https://blog.acolyer.org/2019/09/04/slog/)

• Featured in [the morning paper](https://blog.acolyer.org/2020/03/04/millions-of-tiny-databases/)

### Implementations of consensus This section lists papers describing implementations of distributed consensus algorithms.

• Featured in [the morning paper](https://blog.acolyer.org/2019/03/29/calvin-fast-distributed-transactions-for-partitioned-database-systems/)

• Featured in [the morning paper](https://blog.acolyer.org/2017/05/02/corfu-a-distributed-shared-log/)

• AKA the RAFT consensus paper
• Implemented in [etcd](https://etcd.io), open sourced and widely utilized including by [kubernetes](https://kubernetes.io), [CockroachDB](https://www.cockroachlabs.com/docs/stable/), [Consul](https://www.consul.io) from [HashiCorp](https://www.hashicorp.com), [Atomix](https://atomix.io) and many other systems.
• Featured in [the morning paper](https://blog.acolyer.org/2015/03/12/in-search-of-an-understandable-consensus-algorithm/)

• Weakly consistent key-val store with support for linearizability as requested. Geo-distributed performance is evaluated
• Useful related blog post [Lessons learned from TAPIR(s)](https://irenezhang.net/blog/2015/04/02/tapir.html) & featured in [the morning paper](https://blog.acolyer.org/2015/10/21/building-consistent-transactions-with-inconsistent-replication/)

• Featured in [the morning paper](https://blog.acolyer.org/2017/07/04/azure-data-lake-store-a-hyperscale-distributed-file-service-for-big-data-analytics/)

• Uses Fast Paxos to decide on membership changes. Conflicts are rare as the proposed value is the output of a membership algorithm so proposers usually propose the same proposal.
• Fast Paxos implementation is [here](https://github.com/lalithsuresh/rapid/blob/master/rapid/src/main/java/com/vrg/rapid/FastPaxos.java) and [here](https://github.com/lalithsuresh/rapid/blob/master/rapid/src/main/java/com/vrg/rapid/Paxos.java)

• Also supports BFT

• Featured in [the morning paper](https://blog.acolyer.org/2019/03/15/exploiting-commutativity-for-practical-fast-replication/)

• A two phase quorum read algorithm which does not require the leader and does not rely on bounded clock drift like read leases.

• Latest edition in the line of papers on shared totally-ordered logs: Tango, Corfu, vCorfu, Scalog, Delos

• Looks at using gossip to reduce communication overhead of Multi-Paxos. An unstructured version of PigPaxos/Canopus.

### Evaluations of consensus This section lists papers describing standalone evaluations of consensus algorithms.

• [Author's blog post](http://muratbuffalo.blogspot.com/2019/07/dissecting-performance-bottlenecks-of.html)

• Performance anaylsis of 5 consensus systems, 3 non-byzantine algorithms (including etcd) and 2 byzantine consensus algorithms

• Study of the efficiency (CPU utilization) of Multi-Paxos vs EPaxos, finding that EPaxos provides better throughput than Multi-Paxos at the cost of much worse efficiency.

### State machine replication This section lists papers about the application of consensus to State Machine Replication (SMR/RSMs) and Linearizability.

• Optimistic execution of transactions before ordering in CFT-SMR.

### Reconfiguration This section lists papers on reconfiguration & leader election.

• Describes [Zookeeper's approach to reconfiguration](https://zookeeper.apache.org/doc/r3.5.3-beta/zookeeperReconfig.html).

• Related blog post, [UPaxos and primary-backup replication](https://davecturner.github.io/2017/09/18/upaxos-primary-backup.html)

## Related Topics

### Weaker consistency models This section lists papers that discuss alternative consistency models to [linearizability](https://en.wikipedia.org/wiki/Linearizability) and/or systems that depend upon synchrony for correctness (not just liveness).

• This paper introduced the idea of leases for distributed caches. This idea is used in master leases and read quorum leases.

• PODC keynote in which [Eric Brewer](https://en.wikipedia.org/wiki/Eric_Brewer_(scientist)) proposed the now infamous [CAP theorem](https://en.wikipedia.org/wiki/CAP_theorem).

• Offline consistency checking of key-value traces

• Not discussed in the paper but Cassandra now uses Paxos for [lightweight transactions](https://docs.datastax.com/en/archived/cassandra/3.0/cassandra/dml/dmlLtwtTransactions.html).

• Popular benchmarking tool for key-values stores, actively maintained with support for various data stores.

• Provides linearizability but it assumes a bounded clock drift
• Google implements this using Truetime, GPS, and atomic clocks in their data centers instead of [NTP](https://en.wikipedia.org/wiki/Network_Time_Protocol).
• Closed source but now available as a cloud service called [Cloud Spanner](https://cloud.google.com/spanner/).

• Featured in [the morning paper](https://blog.acolyer.org/2016/12/08/just-say-no-to-paxos-overhead-replacing-consensus-with-network-ordering/)

• Related blog on [all things distributed](https://www.allthingsdistributed.com/2019/03/Amazon-Aurora-design-cloud-native-relational-database.html)
• Featured in [the morning paper](https://blog.acolyer.org/2019/03/25/amazon-aurora-design-considerations-for-high-throughput-cloud-native-relational-databases/)

• Featured in [the morning paper](https://blog.acolyer.org/2019/03/27/amazon-aurora-on-avoiding-distributed-consensus-for-i-os-commits-and-membership-changes/)

• Featured in [the morning paper](https://blog.acolyer.org/2018/11/05/sharding-the-shards-managing-datastore-locality-at-scale-with-akkio/)

• Implemented on programmable switches
• Comes with TLA+ spec in [tech report](https://arxiv.org/pdf/1904.08964.pdf)

• [talk/slides](https://www.usenix.org/conference/fast20/presentation/ganesan)

• New consistency models which are invariant equivalent to linearizability.

### Failures This section lists papers that analyze and/or handle real-world failures of distributed systems.

• [Interested related talk by Jon Currey](https://www.hashicorp.com/resources/failure-detection-in-the-era-of-gray-failures)

• Featured in [the morning paper](https://blog.acolyer.org/2017/03/08/redundancy-does-not-imply-fault-tolerance-analysis-of-distributed-storage-reactions-to-single-errors-and-corruptions/)

### Clocks The liveness of distributed consensus depends on some degree of clock synchronization. The following section lists papers on the topic of clock synchronization.

• [Useful write up by Aleksey Charapko](http://charap.co/reading-group-sundial-fault-tolerant-clock-synchronization-for-datacenters/)

• Some great examples of things that can go wrong with clocks.

• Substantially reduced clock drift when time synchronization (such as NTP, PTP, Sundial) fails. Uses only commodity hardware. Won best paper award.

### Correctness of consensus algorithms This section lists papers on proving or testing the correctness of consensus algorithms.

• Directory of TLA+ specs, including many for consensus algorithms [TLA+ Examples](https://github.com/tlaplus/Examples)

• Paxos implementation in a datalog like [logic language](https://en.wikipedia.org/wiki/Logic_programming).

• Featured in [the morning paper](https://blog.acolyer.org/2015/10/15/ironfleet-proving-practical-distributed-systems-correc/)

• Featured in [the morning paper](https://blog.acolyer.org/2015/03/26/lineage-driven-fault-injection/)

• Featured in [the morning paper](https://blog.acolyer.org/2016/02/01/psync/)

• TLA+ specs are [online](https://www.losa.fr/research/leaderless/)

• Featured in [the morning paper](https://blog.acolyer.org/2017/08/23/growing-a-protocol/)

• Describes DSLabs, an alternative to TLA+, for model checking distributed protocols.
• Featured in [the morning paper](https://blog.acolyer.org/2019/04/17/teaching-rigorous-distributed-systems-with-efficient-model-checking/)

• Automatic inference of Paxos's inductive invariants

• Next step in the inference of inductive invariants for distributed protocols, following on from Ivy and I4. Still does not support Paxos.

• Formal proofs of distributed protocols in Coq including Multi-Paxos, produces verified C executables.

### Quorum systems This section lists papers on quorum systems.

• Featured in [the morning paper](https://blog.acolyer.org/2016/10/03/the-load-capacity-and-availability-of-quorum-systems/)

### Byzantine fault tolerance This section lists papers on [Byzantine Fault Tolerance](https://en.wikipedia.org/wiki/Byzantine_fault) (BFT), often used as the basis of permissioned blockchains.

#### BFT surveys

• Featured in [the morning paper](https://blog.acolyer.org/2018/02/12/sok-consensus-in-the-age-of-blockchains/)

• New survey paper on BFT, more up-to-date than "Consensus in the Age of Blockchains".

#### BFT in theory

• Considered to be the first proof that Byzantine agreement requires at least 3f+1 nodes to tolerate f faults.

• Famous Lamport paper which popularized the Byzantine agreement problem

• Another proof that crash fault tolerance requires 2f+1 nodes and BFT requires 3f+1 nodes.

• Similar to the [Naor and Wool paper on the load, capacity, and availability of quorum systems](https://epubs.siam.org/doi/pdf/10.1137/S0097539795281232) but with Byzantine faults.

• Follow up to Byzantine quorum systems paper.

• Describes FaB, similar in nature to Q/U.

• Bosco: One-Step Byzantine Asynchronous Consensus, DISC 2008 [[acmdl](https://dl.acm.org/citation.cfm?id=1432322),[pdf](https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/52180438.pdf)]
  • Byzantine consensus in 1 round trip (instead of the usual three) using quorums of 4f+1 from 5f+1 nodes.

• Also see: [Mechanically Checked Safety Proof of a Byzantine Paxos Algorithm](https://lamport.azurewebsites.net/tla/byzpaxos.html)

• Describes bugs in Zyzzyva and FaB

• Liveness proof for various BFT protocols including view synchtronization

#### BFT in practice

• Considered to be the first practical BFT-SMR protocol.

• Proposes decoupling consensus from state machine execution, similar to the distinction in Paxos between proposers/acceptors and learners.
• Byzantized variant of Disk Paxos.

• Describes the Q/U protocol, leaderless but requires 5f+1 nodes instead of 3f+1 nodes

• Develops a BFT fork of Zookeeper and HDFS, source code does not seem to be used/maintained

• Describes an approach to reconfigure BFT systems

• BFT-SMR implementation, similar to PBFT. Often used as a benchmark against which new BFT protocols are evaluated.

• Casper FFG, the proposed PoS alternative for [Ethereum](https://ethereum.org/en/) (aka [Eth2](https://ethereum.org/en/eth2/))

• 2nd of the two Algorand papers

• Describes [Tendermint](https://tendermint.com)

• Includes Isabelle/HOL proof in [AFP](https://www.isa-afp.org/entries/Stellar_Quorums.html)

• Formal verification in Ivy and Isabelle/HOL

• Identifies and fixes a liveness issue in [PBFT](http://pmg.csail.mit.edu/papers/osdi99.pdf)'s fast path for non-linearizable read-only operations

• Reputation-based leader rotation algorithm as an alternative to simple round robin.

• Describes the latest version of DiemBFT, based on a variant of HotStuff with 2-phases and quadratic view changes.

• Parallel execution of transactions in BFT-SMR, implemented in [DiemBFT](https://developers.diem.com/papers/diem-consensus-state-machine-replication-in-the-diem-blockchain/2021-08-17.pdf).

### Alternative fault models in distributed consensus Most of these papers handle crash faults or byzantine faults. This section considers the fault models between crash and byzantine.

• Enabling nodes who lose persistent storage (e.g. due to corruption) to rejoin consensus systems without reconfiguration.
• Implemented & evaluated in LogCabin and Zookeeper, but no source code is available
• Best paper award at FAST 2018
• Authors' claim to have model checked with TLA+ but no spec is available
• Featured in [the morning paper](https://blog.acolyer.org/2018/02/27/protocol-aware-recovery-for-consensus-based-storage/)

### Misc Blog posts, books, talks, dissertations, etc…

—

## Future reading list The following lists contain places to watch for new writings in the field of distributed consensus. They are in no particular order.

### Blogroll

### Reading lists

### Academic conferences & symposiums

• Biennial odds only, [Annual from 2023](https://twitter.com/sosp2021/status/1453406095716888586?lang=en-GB)

[Dan Tsafrir](http://www.cs.technion.ac.il/~dan/index.html) maintains a useful list of [systems conferences by deadline](http://www.cs.technion.ac.il/~dan/index_sysvenues_deadline.html).

### Academic workshops

### Academic journals & magazines

• [Transactions on Computer Systems (TOCS)](https://tocs.acm.org)
• [Journal of the ACM (JACM)](https://jacm.acm.org)
• [Communications of the ACM (CACM)](https://cacm.acm.org)
• [SIGOPS Operating Systems Review (OSR)](https://www.sigops.org/osr.html)
• [Computing Surveys (CSUR)](https://csur.acm.org)
• [Transactions on Database Systems (TODS)](https://tods.acm.org)
• [ACM Queue](https://queue.acm.org)
• [SIGACT News](https://dl.acm.org/citation.cfm?id=J697)
• [Distributed Ledger Technologies: Research and Practice (DLT)](https://dl.acm.org/journal/dlt)

• [Transactions on Dependable and Secure Computing (TDSC)](https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=8858)
• [Transactions on Parallel and Distributed Systems (TPDS)](https://www.computer.org/csdl/journal/td)
• [Transactions on Computers (TC)](https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=12)
• [Transactions on Software Engineering](https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=32)