Paxos Consensus Algorithm

In this lesson, you will learn how the Paxos consensus algorithm achieves agreement among distributed nodes by assigning distinct roles to participants.

In a distributed database, achieving consensus means multiple nodes must agree on a single value—such as the outcome of a transaction or the order of operations—even when some nodes fail or network partitions occur. Paxos achieves this by decomposing the process into three logical roles: Proposers, Acceptors, and Learners.

The Three Roles

1. Proposers: These nodes act as the advocates for a specific value. A proposer receives a request from a client and attempts to convince the network to accept it. To ensure progress, a proposer must first obtain permission from a majority of acceptors by submitting a proposal number.
2. Acceptors: These are the "voters" of the system. They act as the fault-tolerant memory of the protocol. When an acceptor receives a proposal, it decides whether to accept it based on its current state (i.e., whether it has already promised to follow a higher-numbered proposal). A value is considered "chosen" only when a majority of acceptors agree on it.
3. Learners: Once a majority of acceptors have reached consensus, the learners act as the final recipients of the agreed-upon value. They do not participate in the voting process; instead, they wait for the acceptors to broadcast the decided value so they can update their local database state accordingly.

Conceptual Workflow

While a single node can play multiple roles, the logic remains separated to ensure safety. The interaction follows a two-phase process:

-- Conceptual Paxos Phase 1: Prepare
-- Proposer sends: PREPARE(proposal_number_N)
-- Acceptor responds: PROMISE(last_accepted_value) if N > any previous

-- Conceptual Paxos Phase 2: Accept
-- Proposer sends: ACCEPT(N, value)
-- Acceptor responds: ACCEPTED(N, value) if no higher proposal promised

Because Paxos requires a quorum (a majority of acceptors), the system continues to function correctly even if a minority of nodes experience failures. This design allows the database to maintain strong consistency despite the inherent unreliability of distributed networks.

Key Takeaway: Paxos reaches consensus by separating the network into Proposers that advocate values, Acceptors that reach a majority-based decision, and Learners that adopt the final, agreed-upon outcome.