Paxos Algorithm

The Proposer is an agent that initiates the consensus process by putting forward a proposed value for the system to agree upon. Its primary function is to shepherd a proposal through the voting phases.

• A Proposer generates a unique, monotonically increasing proposal number to distinguish its request.
• It must gather promises (promises) from a majority of Acceptors in Phase 1.
• In Phase 2, it sends an accept request for a value to the Acceptors.
• Multiple Proposers can exist concurrently, which can lead to contention and require collision resolution through higher proposal numbers.

The Acceptor acts as the voting body in the Paxos protocol. These agents store the state of the voting process and ultimately choose the agreed-upon value.

• Acceptors respond to two types of messages: prepare requests and accept requests.
• They make a promise not to accept proposals with numbers lower than the highest they have seen.
• They accept a value for a given proposal number if it does not violate a prior promise.
• A value is chosen when a majority (a quorum) of Acceptors have accepted it for the same proposal number. Acceptors are typically replicated for fault tolerance.

The Learner is a passive agent that discovers the outcome of the consensus protocol. Learners are informed of the chosen value so the rest of the system can act upon the decision.

• Learners do not participate in the voting phases.
• They learn the chosen value by being notified by Acceptors or Proposers.
• For efficiency, a single distinguished Learner may be elected to disseminate the result.
• In practical deployments, clients or other system components typically act as Learners to execute commands once they are known to be agreed upon.

Phase 1 (Prepare/Promise) is the discovery phase where a Proposer tests the water and seeks permission to propose a value.

1. Prepare: A Proposer selects a new, unique proposal number n and sends a prepare(n) request to a majority of Acceptors.
2. Promise: An Acceptor receives prepare(n). If n is higher than any proposal number it has previously responded to, it:
   • Promises not to accept any more proposals numbered less than n.
   • Returns the highest-numbered proposal it has already accepted (if any), along with its corresponding value.
   • This ensures a Proposer learns of any potentially already-chosen value.

Phase 2 (Accept/Accepted) is the decision phase where a Proposer attempts to get a value formally accepted by the majority.

1. Accept Request: If the Proposer receives promises from a majority of Acceptors, it can now send an accept request. The value it proposes is:
   • The value from the highest-numbered proposal reported by the Acceptors (if any existed).
   • Or, if no Acceptors reported a prior accepted value, the Proposer's own proposed value.
   • It sends an accept(n, value) message to the Acceptors.
2. Accepted: An Acceptor receives accept(n, value). It accepts this value only if it has not already promised (in Phase 1) to ignore proposals numbered n or lower. If it accepts, it informs the Proposer and Learners.

While Paxos guarantees safety (no two correct processes decide different values), it can suffer from liveness issues, specifically livelock. This occurs when multiple Proposers continuously interfere with each other.

• Scenario: Proposer P1 sends prepare(n1). Before it can complete Phase 2, Proposer P2 sends prepare(n2) where n2 > n1. Acceptors now promise to P2, breaking P1's quorum. P1 restarts with a higher number n3, which can then be interrupted by P4, and so on.
• Solution: Real-world implementations use techniques like:
  • Distinguished Leader: Electing a single Proposer for long periods.
  • Randomized Backoff: Proposers wait random intervals before retrying.
  • Epochs: Using time-based lease mechanisms to grant exclusive proposal rights.

Byzantine Fault Tolerance (BFT) is a property of a distributed system that allows it to reach consensus and continue operating correctly even when some of its components fail arbitrarily, including through malicious or Byzantine behavior. This is a stricter requirement than the crash-fault model assumed by classic Paxos.

• Classic Paxos assumes nodes may crash but are not malicious.
• BFT protocols (e.g., PBFT, Tendermint) must handle nodes that may lie, send conflicting messages, or otherwise act adversarially.
• BFT is essential for permissionless blockchains and high-security financial systems where participants are not fully trusted.

Raft is a consensus algorithm designed for managing a replicated log, providing a more understandable alternative to Paxos. It explicitly separates the key elements of consensus into leader election, log replication, and safety.

• Created to be more pedagogically accessible than the notoriously complex Paxos family of protocols.
• Uses a strong leader model; all client requests go through the elected leader, which simplifies log management.
• Like Paxos, it provides safety (log consistency) and liveness (progress) under crash-fault assumptions. It is widely used in systems like etcd and Consul.

State Machine Replication (SMR) is a fundamental technique in distributed systems where a deterministic service is replicated across multiple machines to provide fault tolerance. Consensus algorithms like Paxos and Raft are the engines that implement SMR.

• The core idea: ensure all replicas start in the same state and process the same sequence of commands in the same order.
• Paxos is often used to agree on the sequence (the replicated log).
• Once the log is agreed upon, each replica deterministically applies the commands to its local state machine, guaranteeing identical outputs.

Atomic Broadcast is a communication primitive in distributed systems that guarantees all correct processes deliver the same set of messages in the same order. Solving Atomic Broadcast is equivalent to solving consensus.

• This is the problem Paxos directly addresses for log entries.
• The "atomic" property ensures total order broadcast: if one correct process delivers message A before message B, then all correct processes do the same.
• It is the foundational building block for implementing replicated state machines and strongly consistent distributed databases.

A quorum is the minimum number of votes or participants required in a distributed system to approve an operation, make a decision, or achieve consensus. Paxos uses quorums to ensure safety despite node failures.

• In Paxos, a quorum is any majority of acceptors (e.g., 3 out of 5 nodes).
• The intersection property of majorities is critical: any two quorums must share at least one correct node. This prevents two different values from being decided.
• Quorum systems are a trade-off between fault tolerance (larger quorums can tolerate more failures) and latency (waiting for more responses).

These are the two fundamental guarantees provided by consensus algorithms like Paxos.

• Safety is the guarantee that nothing bad happens. For Paxos, this means all correct processes that decide a value decide the same value. A faulty process cannot cause the system to agree on an incorrect or conflicting value. Safety must never be violated.
• Liveness is the guarantee that something good eventually happens. For Paxos, this means the system will eventually decide on a value, provided a majority of nodes are non-faulty and can communicate. Liveness can be temporarily hindered by asynchrony or continuous leader failure.

Paxos prioritizes safety over liveness; it will not break consistency to make progress.