Paxos Algorithm

A Proposer is an agent that initiates the consensus process by putting forward a proposed value for the system to agree upon. In a multi-agent system, any node can act as a proposer when it needs the cluster to decide on a new command or piece of data.

• Role: Generate proposal numbers and drive the protocol forward.
• Behavior: Must gather promises from a majority of Acceptors before sending an Accept request.
• Fault Tolerance: Multiple proposers can operate concurrently, which may cause conflicts resolved by higher proposal numbers.

Acceptors form the fault-tolerant memory of the Paxos protocol. They collectively store the state of the voting process and the potentially chosen value.

• Role: Receive and respond to Prepare and Accept messages from Proposers.
• Promise Rule: An Acceptor must promise not to accept proposals with numbers less than any it has already promised to.
• Majority Requirement: A value is chosen only when a quorum (a majority) of Acceptors have accepted it. This ensures progress despite individual failures.

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.

A consensus protocol is a distributed algorithm that enables a group of independent agents or nodes to agree on a single data value or a sequence of actions, ensuring system consistency despite failures. Paxos is a canonical example. These protocols are the bedrock of reliable distributed systems, enabling state machine replication and forming the core of many databases and coordination services.

Byzantine Fault Tolerance (BFT) is a property of a distributed system that allows it to reach consensus and continue operating correctly even when some components fail arbitrarily, including by sending malicious or conflicting information. While classic Paxos assumes crash-fault models (nodes stop working), BFT protocols like Practical Byzantine Fault Tolerance (PBFT) defend against arbitrary, potentially malicious behavior, a critical consideration for adversarial environments.

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.