How does Paxos work?

Paxos employs $leaders$ and $acceptors$ -- specialized processes that coordinate the replicas. The table below summarizes the functions of each type of process and how many of each are needed to tolerate $f$ failures in Paxos.

Process Type Description Minimum #
Replica • maintains application state
• receives requests from clients
• asks leaders to serialize the requests so all replicas see the same sequence
• applies serialized requests to the application state
• responds to clients
Acceptor • maintains the fault tolerant memory of Paxos
Leader • receives requests from replicas
• serializes requests and responds to replicas

To understand how Paxos works one must understand how each type of process works. Each process is a deterministic state machine on its own right, maintaining state and undergoing state transitions in response to incoming messages. For each type of process, we will first describe what state it maintains and what invariants need to hold for correctness during state transitions. We then give an operational description using pseudo-code and discuss how the invariants are maintained during operation.