Paxos

The non-negotiable guarantee that Paxos provides. It ensures that if a value is chosen, it is the only value that can be chosen, and all correct learners (processes learning the outcome) eventually learn that chosen value. This prevents the system from agreeing on contradictory decisions, which is critical for maintaining a single source of truth in a distributed ledger or replicated state machine.

• Key Mechanism: Relies on a majority quorum (acceptors) to guarantee that only one proposal with a given proposal number can be accepted.

The guarantee that the protocol will eventually make progress and choose a value, provided certain system conditions are met. Paxos guarantees safety even under arbitrary failure conditions, but liveness depends on eventual system stability.

• Requires: A distinguished proposer (often called the leader) that can communicate with a majority of acceptors. In practice, a leader election mechanism is needed to ensure liveness in the face of proposer failures or network partitions.

Paxos is designed to tolerate crash-stop failures of processes. It can make progress as long as a majority of acceptor processes remain operational and can communicate with a proposer. The protocol's phases are structured so that any participant can fail at any time without violating safety.

• Tolerance Level: Can tolerate f failures with a cluster size of 2f + 1 acceptors. For example, a Paxos group of 5 acceptors can tolerate 2 simultaneous failures.

Paxos defines three distinct roles for processes, which may be collocated on the same physical nodes:

• Proposers: Initiate proposals for a value.
• Acceptors: Form a quorum to vote on and accept proposals.
• Learners: Learn the chosen value once consensus is reached.

The protocol operates in two key phases to ensure safety despite message loss and retransmission:

1. Prepare/Promise Phase: A proposer sends a prepare request with a unique, monotonically increasing proposal number. Acceptors promise not to accept any older proposals.
2. Accept/Accepted Phase: The proposer, having received promises from a majority, sends an accept request with a value. Acceptors write the value to persistent storage if they haven't promised a higher-numbered proposal.

In the basic Paxos protocol, multiple proposers can cause contention, leading to repeated collisions and reduced performance. Multi-Paxos is a common optimization where a stable leader is elected to act as the sole proposer for a sequence of consensus instances (e.g., a replicated log).

• Efficiency Gain: The prepare phase can be skipped for all instances after the first one, as the leader's authority is established, reducing the typical consensus round from two message delays to one.

Paxos is the foundational algorithm for implementing a replicated state machine, a core technique for building fault-tolerant services. Each command to the state machine is agreed upon as a value in a sequence of Paxos instances, forming a consistent, ordered log.

• Practical Use: This is how systems like Google's Chubby lock service and many distributed databases (e.g., etcd's Raft, which is Paxos-inspired) achieve strong consistency. It ensures all replicas execute the same commands in the same order.

A distributed algorithm that enables a group of processes or agents to agree on a single data value or sequence of actions despite the possibility of failures. Paxos is a canonical example. Key characteristics include:

• Agreement: All correct processes decide on the same value.
• Validity: The decided value must have been proposed by some process.
• Termination: Every correct process eventually decides a value.
• Fault Tolerance: The algorithm must progress despite a bounded number of process failures (e.g., crash failures).

The property of a distributed system to resist Byzantine faults, where components may fail in arbitrary and malicious ways, including sending conflicting information to different parts of the system. This contrasts with the crash-fault model assumed by classic Paxos.

• Practical Byzantine Fault Tolerance (PBFT): A seminal algorithm that tolerates up to f faulty nodes in a system of 3f + 1 nodes.
• Applications: Critical for blockchain networks (e.g., Tendermint) and high-security financial or military systems where participants cannot be fully trusted.

A fundamental technique for implementing a fault-tolerant service by replicating a deterministic state machine across multiple nodes. The core guarantee is that all replicas start in the same state and process the same sequence of commands in the same order, resulting in identical state transitions.

• Implementation: Typically built on top of a consensus algorithm like Paxos or Raft to agree on the command sequence.
• Use Case: The backbone of highly available distributed databases (e.g., Google Spanner, CockroachDB) and coordination services (e.g., Apache ZooKeeper).

A communication primitive that guarantees all correct processes in a distributed system deliver the same set of messages in the same total order. It is a stricter guarantee than regular broadcast.

• Relationship to Consensus: Solving Atomic Broadcast is equivalent to solving Consensus. Paxos can be (and often is) used to implement Atomic Broadcast.
• Total Order Broadcast: Another name for this primitive. It is essential for implementing State Machine Replication, as it provides the ordered command stream.

A technique for ensuring consistency in distributed systems by requiring a majority (or other defined subset) of replicas to participate in read and write operations. Paxos uses quorums to ensure progress despite failures.

• Quorum Intersection: Any two quorums must have at least one correct node in common. This property prevents conflicting decisions.
• Flexibility: Quorum sizes can be tuned for latency vs. durability trade-offs (e.g., requiring only a majority of replicas to acknowledge a write vs. all replicas).