Paxos Algorithm

A Learner is an agent that discovers which value has been chosen by the Acceptors. Learners are passive observers that do not participate in the voting phases but must be informed of the outcome to execute the agreed-upon action.

• Role: Learn the chosen value to update their local state or execute a command.
• Notification: Typically informed by Acceptors or a distinguished Leader (a special Proposer).
• System Design: In practical deployments, all nodes often act as Proposers, Acceptors, and Learners combined.

The Prepare Phase is the first stage where a Proposer seeks permission to issue a proposal. It ensures no previously accepted higher-numbered proposal is overlooked.

1. Prepare Request: A Proposer selects a unique, monotonically increasing proposal number n and sends a Prepare(n) request to a majority of Acceptors.
2. Promise Response: An Acceptor replies with a Promise not to accept any more proposals numbered less than n. If it has already accepted a value, it includes that value and its corresponding proposal number in the response.

The Accept Phase is where a Proposer attempts to get its value formally accepted by a majority. The value it proposes is constrained by promises received in Phase 1.

1. Propose Value: If the Proposer receives promises from a majority, it sends an Accept(n, v) request. The value v is either its own intended value or, critically, the value associated with the highest-numbered proposal among the promises it received.
2. Accepted Response: An Acceptor accepts the proposal (n, v) unless it has already promised not to (i.e., it has promised to a higher-numbered proposal). If a majority accepts, the value v is formally chosen.

These two concepts are the linchpins of Paxos's safety and liveness guarantees.

• Proposal Number: A unique, totally ordered identifier (e.g., a timestamp + node ID). It establishes priority and resolves conflicts between competing Proposers. A higher number overrides promises made to lower numbers.
• Quorum: Any majority subset of the Acceptors. The protocol's correctness depends on the mathematical fact that any two quorums must intersect. This intersection guarantees that at most one value can be chosen, as information about a potentially chosen value is always preserved across quorums.

Raft is a consensus algorithm designed for understandability, which manages a replicated log to ensure state machine replication across a cluster. Created as a more understandable alternative to Paxos, it explicitly separates the roles of leader election, log replication, and safety. Its clear specification has made it the foundation for systems like etcd and Consul.

State Machine Replication (SMR) is a fundamental fault-tolerance technique where a deterministic service is replicated across multiple machines. Each replica processes the same sequence of client requests in the same order, producing identical state transitions and outputs. Consensus protocols like Paxos and Raft are used to agree on this total order of requests, making SMR possible.

A quorum is the minimum number of members of a distributed system that must agree on an operation or value for it to be considered valid. In Paxos, a majority quorum (N/2 + 1) is required to ensure that any two quorums intersect, guaranteeing that at least one node knows the most recent decision. This mathematical principle is key to the protocol's safety and liveness guarantees.

The CAP theorem is a fundamental principle stating that a distributed data store can provide only two of three guarantees simultaneously: Consistency (every read receives the most recent write), Availability (every request receives a response), and Partition tolerance (the system continues operating despite network failures). Paxos is a CP (Consistent and Partition-tolerant) system, prioritizing agreement over availability during a network partition.