Paxos is a family of protocols for achieving consensus in a distributed system of unreliable nodes. It ensures that multiple nodes agree on a single value, even when some nodes fail.
Developed by: Leslie Lamport (1989, published 1998)
Key Property: Safety - never chooses conflicting values
Fault Tolerance: Tolerates f failures with 2f + 1 nodes
| Role | Responsibilities | State |
|---|---|---|
| Proposer |
• Proposes values to be agreed upon • Generates unique proposal numbers • Sends PREPARE and ACCEPT messages |
• Proposal number (unique, increasing) • Proposed value • Set of promises/accepts received |
| Acceptor |
• Votes on proposals • Promises to ignore lower-numbered proposals • Accepts proposals that meet conditions |
• Highest promised proposal number • Highest accepted proposal |
| Learner |
• Receives ACCEPTED messages • Determines when consensus is reached • Learns the chosen value |
• Tracking which proposals were accepted • The learned consensus value |
Proposer sends: PREPARE(proposal_number)
Purpose: Ask acceptors if they will accept this proposal
Proposal number must be: Unique and higher than any previous
Acceptor responds with PROMISE if:
Promise includes:
Acceptor responds with NACK if:
Proposer sends: ACCEPT(proposal_number, value)
Value must be:
Acceptor responds with ACCEPTED if:
Acceptor updates state:
Consensus is reached when:
Issue: Competing proposers can interrupt each other indefinitely
Example:
Solution: Multi-Paxos with leader election (one proposer at a time)
| Property | Guarantee | Explanation |
|---|---|---|
| Safety | Only one value can be chosen | Never produces conflicting results, even with failures |
| Fault Tolerance | Tolerates f failures with 2f+1 nodes | With 5 acceptors, can tolerate 2 failures |
| Termination | Not guaranteed | May not reach consensus if proposers keep interrupting |
| Message Complexity | O(n²) | n acceptors × multiple phases |
| Latency | 2 round trips | Phase 1 (prepare) + Phase 2 (accept) |
class Acceptor:
"""Acceptor role in Paxos - votes on proposals
State:
- promised_proposal: Highest proposal number it has promised to consider
- accepted_proposal: Highest proposal it has accepted
"""
def __init__(self, node_id: str):
self.node_id = node_id
self.promised_proposal: Optional[Proposal] = None
self.accepted_proposal: Optional[Proposal] = None
def receive_prepare(self, proposal: Proposal) -> Message:
"""Phase 1b: Respond to prepare request
Rules:
- If proposal number > any previously promised, send PROMISE
- Include any previously accepted proposal
- Otherwise send NACK
"""
if self.promised_proposal is None or proposal.number > self.promised_proposal.number:
# Promise to not accept proposals with lower numbers
self.promised_proposal = proposal
return Message(
type=MessageType.PROMISE,
from_node=self.node_id,
to_node="proposer",
proposal=proposal,
accepted_proposal=self.accepted_proposal
)
else:
# Already promised a higher proposal number
return Message(
type=MessageType.NACK,
from_node=self.node_id,
to_node="proposer",
proposal=proposal,
promised_proposal=self.promised_proposal
)
def receive_accept(self, proposal: Proposal) -> Message:
"""Phase 2b: Respond to accept request
Rules:
- If proposal number >= promised number, accept it
- Otherwise send NACK
"""
if self.promised_proposal is None or proposal.number >= self.promised_proposal.number:
# Accept the proposal
self.accepted_proposal = proposal
self.promised_proposal = proposal
return Message(
type=MessageType.ACCEPTED,
from_node=self.node_id,
to_node="proposer",
proposal=proposal
)
else:
# Already promised a higher proposal number
return Message(
type=MessageType.NACK,
from_node=self.node_id,
to_node="proposer",
proposal=proposal,
promised_proposal=self.promised_proposal
)class Proposer:
"""Proposer role in Paxos - proposes values"""
def __init__(self, node_id: str, value: Any):
self.node_id = node_id
self.value = value
self.proposal_number = 1
self.promises_received: Set[str] = set()
self.highest_accepted: Optional[Proposal] = None
def prepare(self, acceptors: Dict[str, Acceptor]) -> bool:
"""Phase 1a: Send PREPARE to all acceptors
Returns True if majority promised, False otherwise
"""
self.proposal_number += len(acceptors) # Ensure uniqueness
proposal = Proposal(self.proposal_number, self.value)
self.promises_received.clear()
# Send PREPARE to all acceptors
for acceptor_id, acceptor in acceptors.items():
response = acceptor.receive_prepare(proposal)
if response.type == MessageType.PROMISE:
self.promises_received.add(acceptor_id)
# Track highest accepted proposal from responses
if response.accepted_proposal:
if self.highest_accepted is None or response.accepted_proposal > self.highest_accepted:
self.highest_accepted = response.accepted_proposal
# CRITICAL: Must use value from highest accepted proposal
self.value = self.highest_accepted.value
# Check if we have majority
majority = len(acceptors) // 2 + 1
return len(self.promises_received) >= majority
def accept(self, acceptors: Dict[str, Acceptor]) -> bool:
"""Phase 2a: Send ACCEPT to all acceptors
Returns True if majority accepted, False otherwise
"""
proposal = Proposal(self.proposal_number, self.value)
self.accepts_received.clear()
for acceptor_id, acceptor in acceptors.items():
response = acceptor.receive_accept(proposal)
if response.type == MessageType.ACCEPTED:
self.accepts_received.add(acceptor_id)
majority = len(acceptors) // 2 + 1
return len(self.accepts_received) >= majority
def propose(self, acceptors: Dict[str, Acceptor]) -> Optional[Any]:
"""Run full Paxos protocol"""
# Phase 1: Prepare
if not self.prepare(acceptors):
return None # Failed to get majority promises
# Phase 2: Accept
if not self.accept(acceptors):
return None # Failed to get majority accepts
return self.value # Success!class Learner:
"""Learner role in Paxos - learns the chosen value"""
def __init__(self, node_id: str):
self.node_id = node_id
self.accepted_proposals: Dict[int, Set[str]] = {}
self.learned_value: Optional[Any] = None
def receive_accepted(self, acceptor_id: str, proposal: Proposal, total_acceptors: int):
"""Process ACCEPTED message from an acceptor"""
if proposal.number not in self.accepted_proposals:
self.accepted_proposals[proposal.number] = set()
self.accepted_proposals[proposal.number].add(acceptor_id)
# Check if majority accepted this proposal
majority = total_acceptors // 2 + 1
if len(self.accepted_proposals[proposal.number]) >= majority:
self.learned_value = proposal.value
print(f"LEARNED: Value '{self.learned_value}' has been chosen!")
def get_learned_value(self) -> Optional[Any]:
"""Get the learned consensus value"""
return self.learned_value| Feature | Paxos | Raft |
|---|---|---|
| Understandability | Complex, hard to grasp | Designed for clarity |
| Leader | No leader (Multi-Paxos adds one) | Strong leader-based |
| Log Replication | Not built-in (needs Multi-Paxos) | Built-in, core feature |
| Variants | Many (Multi-Paxos, Fast Paxos, EPaxos) | Fewer variants, standardized |
| Implementation | Harder to implement correctly | Easier to implement |
| Used In | Google Chubby, ZooKeeper, Spanner | etcd, Consul, CockroachDB |
Purpose: Distributed lock service
Consensus: Multi-Paxos for leader election and state replication
Scale: Thousands of cells across Google infrastructure
Purpose: Coordination service for distributed applications
Consensus: ZAB (ZooKeeper Atomic Broadcast) - similar to Multi-Paxos
Features: Leader election, configuration management, distributed synchronization
Purpose: Globally distributed database
Consensus: Paxos for replication groups
Innovation: TrueTime API for global consistency