Paxos: Achieving Consensus in Unreliable Networks

WHY IT EXISTS Distributed systems need a way to agree on a single source of truth. If you have a database replicated across three servers, and one fails during a write, how do the remaining two know what the correct state is? Paxos was created to solve this consensus problem, ensuring that a group of unreliable servers can agree on a single value and make forward progress.

THE MENTAL MODEL Think of a group of part-time legislators in ancient Greece trying to pass a single law. They can only communicate via unreliable messengers who might lose messages or deliver them out of order. Paxos is the formal procedure they follow. A legislator (a Proposer) suggests a law with a proposal number. Other legislators (Acceptors) can promise not to vote for any older proposals. If a majority makes this promise, the Proposer can send a commit request. If a majority accepts the commit, the law is passed. The key is that the protocol guarantees only one law can ever be chosen, even if legislators crash or messages are lost.

HOW IT WORKS Paxos is a multi-phase protocol. In its simplest form, it has two phases. Phase 1 (Prepare): A node, acting as a Proposer, picks a proposal number and sends a 'prepare' message to a majority of nodes, called Acceptors. An Acceptor will promise not to accept any older proposals and replies with the highest-numbered proposal it has already accepted, if any. Phase 2 (Accept): If the Proposer receives promises from a majority of Acceptors, it sends an 'accept' request to them containing the value to be decided. If an Acceptor has not made a conflicting promise, it accepts the value. If a majority of Acceptors accept the value, it is officially chosen by the system.

WHEN TO USE IT Use Paxos when you need strong consistency and fault tolerance for critical state in a distributed system. It's the theoretical foundation for many distributed databases (like Google Spanner via its variants), replicated state machines, and coordination services like Apache ZooKeeper (which uses a similar protocol, ZAB).

WHEN NOT TO USE IT Do not use Paxos if eventual consistency is acceptable, as the protocol's multiple communication rounds introduce latency. More importantly, do not implement it yourself. The protocol is famously subtle and difficult to get right. For most practical purposes, use a battle-tested library or a more understandable consensus algorithm like Raft, which was designed specifically for implementation clarity.

ONE CANONICAL EXAMPLE A distributed key-value store needs to replicate a write operation (e.g., SET key = 'value') across three servers to ensure fault tolerance. One server acts as the Proposer for this operation. It uses Paxos to get the other two servers (the Acceptors) to agree on this specific operation as the next entry in their shared, replicated log. Once a majority agrees, the operation is committed, ensuring all servers apply the same writes in the same order, even if one server fails.