Awesome Consensus

A curated selection of artisanal consensus algorithms and hand-crafted distributed lock services.

Paxos - Algorithm

• Part-time Parliament
• Paxos made Simple
• Paxos made Practical
• Wikipedia: Paxos
• Paxos lecture (Raft user study)
• The Paxos Algorithm (Google Tech Talk by Luis Quesada Torres)
• [Dr. TLA+ Series] Paxos - Andrew Helwer
• Paxos Agreement - Computerphile
• Paxos Simplified by Chris Colohan
• Neat Algorithms: Paxos Visualized
• Model Checking Paxos in Spin
• Paxos Consensus, Deconstructed and Abstracted (Extended Version)

Paxos - Engineering

• Lessons Learned from Implementing Paxos
• Tencent/phxpaxos
• Practical Experience Report: The Performance of Paxos in the Cloud
• Paxos for System Builders
• Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore
• Paxos made Moderately Complex, website
• Paxos made Live
• Paxos made code: Implementing a high throughput Atomic Broadcast, libpaxos
• 500 lines or less: Clustering by Consensus
• ScalienDB: Designing and Implementing a Distributed Database using Paxos
• Seamless Paxos Coordinators
• IronFleet: Proving Practical Distributed Systems Correct
• Low-Overhead Paxos Replication

Zookeeper

• Zab: A Simple Totally Ordered Broadcast Protocol
• ZooKeeper: Wait-free coordination for Internet-scale systems

Raft

• The Raft Consensus Algorithm
• Raft: In Search of an Understandable Consensus Algorithm
• Raft lecture (Raft user study)
• ARC: Analysis of Raft Consensus
• Raft Refloated: Do We Have Consensus?
• Raft Understandable Distributed Consensus Visualization
• Ark: A Real-World Consensus Implementation
• Understanding performance aspects of etcd and Raft - Hitoshi Mitake, NTT Laboratories
• Raft does not Guarantee Liveness in the face of Network Faults

Raft - Engineering

• braft
• sofa-jraft
• dragonboat

Chubby

• The Chubby Lock Service for Loosely-Coupled Distributed Systems
• Papers We Love

Viewstamped Replication

• Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems Liskov '88
• Viewstamped Replication Revisited
• From Viewstamped Replication to Byzantine Fault Tolerance

CASPaxos

• CASPaxos: Replicated State Machines without logs
• Paxos on Steroids and a Crash Course in TLA+
• A TLA+ specification for Gryadka

Fast Paxos

• Fast Paxos
• Dr. TLA+ Series - Fast Paxos
• The Performance of Paxos and Fast Paxos
• On the Coordinator's Rule for Fast Paxos

AllConcur

• AllConcur: Leaderless Concurrent Atomic Broadcast (Extended Version)
• Formal Specification and Safety Proof of a Leaderless Concurrent Atomic Broadcast Algorithm

Multi-Paxos

• Formal Verification of Multi-Paxos for Distributed Consensus
• Multi-Paxos: An Implementation and Evaluation
• Moderately Complex Paxos Made Simple: High-Level Specification of Distributed Algorithm

Other Paxos Variants

• There is more consensus in egalitarian parliaments (paper), video, efficient/epaxos
• Flexible Paxos: Quorum intersection revisited, Dr TLA+ talk
• Designing Distributed Systems Using Approximate Synchrony in Data Center Networks, UWSysLab/specpaxos
• WPaxos: Ruling the Archipelago with Fast Consensus
• Paxos Quorum Leases: Fast Reads Without Sacrificing Writes
• Self-Stabilizing Paxos
• Generalized Paxos Made Byzantine (and Less Complex)
• PaxosLease: Diskless Paxos for Leases

Stellar

• The Stellar Consensus Protocol: A Federated Model for Internet-level Consensus
• Understanding the Stellar Consensus Protocol

Distributed Consensus

• Heidi Howard - Distributed Consensus: Making Impossible Possible
• Can’t we all just agree? -- 10 part blog series on distributed consensus algorithms
• Consensus in the Cloud: Paxos Systems Demystified
• On Ways to Agree: DistSys Vocabulary
• On Ways to Agree: Path to Atomic Broadcast
• A Generalised Solution to Distributed Consensus, morning paper summary
• Paxosmon: Gotta Consensus Them All: A detailed summary of many different Paxos variants
• Consensus in Presensus of Partial Synchrony
• The latest gossip on BFT consensus

Other

• Time, Clocks and the Ordering of Events in a Distributed System
• A brief history of Consensus, 2PC and Transaction Commit
• Paxos Protocol Framework
• Byzantine Generals
• Practical Byzantine Fault Tolerance
• Just say NO to Paxos Overhead: Replacing Consensus with Network Ordering
• Impossibility of Distributed Consensus with One Faulty Process - FLP
• Practical Byzantine Fault Tolerance and Proactive Recovery
• Vive La Difference: Paxos vs. Viewstamped Replication vs. Zab
• Aleph: A Leaderless, Asynchronous, Byzantine Fault Tolerant Consensus Protocol
• Flexible Byzantine Fault-Tolerance
• Delegated Byzantine Fault Tolerance