Clear DefinitionsPaxos
1 min read
Pronunciation
[pak-sos]
Analogy
Paxos is like a committee that must agree on a proposal via multiple rounds of voting, even if some members fail to respond.
Definition
Key Points Intro
Basic Paxos achieves agreement via these roles and phases:
Key Points
Proposers, Acceptors, Learners: Distinct roles in the protocol.
Prepare phase: Proposer solicits promises from acceptors.
Accept phase: Proposer sends value to acceptors who promised.
Quorum: Majority of acceptors needed to progress.
Example
Google’s Chubby lock service uses Paxos to ensure only one client holds a lock at a time across multiple servers.
Technical Deep Dive
In Phase 1, a proposer picks a proposal number n and sends Prepare(n) to acceptors. Acceptors reply with promise not to accept lower numbers and include any prior accepted value. In Phase 2, proposer sends Accept(n, value) to acceptors; if a majority accepts, the value is chosen. Learners learn the chosen value via acceptor notifications.
Security Warning
Under high contention, Paxos can suffer livelock; backoff and randomized retries mitigate this.
Caveat
Paxos is notoriously difficult to implement correctly due to subtle edge cases.
Paxos - Related Articles
No related articles for this term.