Consensus

Paxos

Paxos is the classical crash-fault-tolerant consensus algorithm introduced by Leslie Lamport in 1989. Paxos and its derivatives (Multi-Paxos, Cheap Paxos, Vertical Paxos, EPaxos, Flexible Paxos) are foundational to distributed systems theory and are used in Google Chubby, Spanner, Megastore, and others.

GitHub

Other Resources

🔗
Specification
https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
🔗
Reference
https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf
🔗
Reference
https://en.wikipedia.org/wiki/Paxos_(computer_science)

API entry from apis.yml

apis.yml Raw ↑ 
aid: consensus:paxos
name: Paxos
description: Paxos is the classical crash-fault-tolerant consensus algorithm introduced by Leslie Lamport
  in 1989. Paxos and its derivatives (Multi-Paxos, Cheap Paxos, Vertical Paxos, EPaxos, Flexible Paxos)
  are foundational to distributed systems theory and are used in Google Chubby, Spanner, Megastore, and
  others.
humanURL: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
baseURL: https://lamport.azurewebsites.net
tags:
- Lamport
- Paxos
- Replication
properties:
- type: Specification
  url: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
- type: Reference
  url: https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf
- type: Reference
  url: https://en.wikipedia.org/wiki/Paxos_(computer_science)
x-features:
- Tolerates up to f crash failures with 2f+1 acceptors
- Phases prepare, promise, accept, accepted
- Multi-Paxos pipelines decisions for log replication
- Underlies Google Chubby and Spanner
x-useCases:
- Replicated state machines
- Distributed configuration services (Chubby, ZooKeeper-like)
- Globally consistent databases