Paxos

The non-negotiable correctness guarantees of Paxos. Safety ensures that:

• Agreement: No two correct nodes ever decide on different values. Once a value is chosen, it is final.
• Validity: Only a value that was proposed by some node can be chosen. These properties hold even in the presence of fail-stop node failures and message delays, preventing split-brain scenarios and guaranteeing system consistency.

The guarantee that the protocol will eventually make progress and choose a value, provided certain system conditions are met. In purely asynchronous networks (where messages can be delayed indefinitely), Paxos, like any consensus algorithm, cannot guarantee liveness—this is the FLP impossibility result. In practice, liveness is achieved by:

• Using failure detectors or timeouts.
• Ensuring a quorum of non-faulty nodes can communicate.
• Having a distinguished proposer (leader) to drive progress, a pattern used in derived protocols like Multi-Paxos.

Paxos is designed to tolerate fail-stop (crash) faults. The protocol can make progress as long as a quorum of nodes is alive and can communicate. A quorum is typically a majority of nodes (e.g., floor(N/2) + 1 out of N). This means Paxos can tolerate F failures out of N nodes, where N = 2F + 1. For example, a 5-node cluster can tolerate 2 simultaneous node failures. It is not natively designed for Byzantine faults (malicious behavior), though Byzantine Paxos variants exist.

Paxos defines three logical roles, which may be colocated on the same physical nodes:

• Proposers: Receive client requests and drive the protocol by proposing values.
• Acceptors: Form the core consensus group. They vote on proposals and store the agreed-upon state. A quorum of acceptors is required for any decision.
• Learners: Learn the chosen value once consensus is reached and act upon it (e.g., execute a state machine command). This role separation provides flexibility in system architecture and allows for optimizations like having multiple learners for scalability.

The classic Paxos protocol operates in two distinct phases to ensure safety despite concurrency and failures:

• Phase 1 (Prepare/Promise): A proposer sends a prepare request with a unique, monotonically increasing proposal number to a quorum of acceptors. An acceptor promises not to accept any proposal with a number less than this and replies with the highest-numbered proposal it has already accepted (if any).
• Phase 2 (Accept/Accepted): If the proposer receives promises from a quorum, it sends an accept request for a value. The value must be the one from the highest-numbered proposal reported in the promises, or its own if none were reported. A quorum of acceptors must accept it for the value to be chosen. This structure ensures that only one value can be chosen per instance, even with multiple competing proposers.

Paxos is designed for an asynchronous network model, meaning it makes no timing assumptions. Messages can be arbitrarily delayed, duplicated, or delivered out of order (though not corrupted). This makes Paxos highly robust for real-world networks like data centers or WANs. The trade-off is that, as per the FLP result, it cannot guarantee liveness (progress) without additional mechanisms like timeouts. This model is why Paxos provides safety under the worst-case network conditions, a critical property for building reliable distributed systems.

The property of a system to reach correct consensus despite arbitrary (potentially malicious) component failures. While classic Paxos assumes non-Byzantine (crash-stop) faults, Practical Byzantine Fault Tolerance (PBFT) and its variants extend the consensus problem. Key distinctions:

• Adversarial Model: Handles nodes that may lie, delay, or send conflicting messages.
• Complexity: Requires more message exchanges and cryptographic signatures (e.g., digital signatures).
• Use Case: Critical for blockchain networks (e.g., Tendermint) and high-security multi-agent systems where agents cannot be fully trusted.

A protocol for achieving atomicity across distributed nodes in a database transaction, not general consensus. It coordinates participants to either all commit or all abort. Process:

1. Prepare Phase: The coordinator asks all participants if they can commit.
2. Commit Phase: If all vote 'yes', the coordinator instructs a commit; otherwise, it instructs an abort. Contrast with Paxos: 2PC is a blocking protocol (vulnerable to coordinator failure) and requires a stable coordinator, whereas Paxos is leaderless and fault-tolerant. 2PC is used for ACID transactions across shards, not for agreeing on a sequence of values.

A consistency model where, if no new updates are made, all reads will eventually return the last written value. It does not guarantee immediate uniformity. This is a weaker guarantee than the strong consistency provided by Paxos. Common in:

• DNS: Updates propagate slowly.
• Multi-leader replication: Conflicts are resolved asynchronously. Paxos is used to implement stronger models (like linearizability) for critical state, while eventual consistency is often sufficient for cached data or non-critical agent state in large-scale systems.

A fundamental technique in distributed systems where an operation must receive successful responses from a minimum subset of nodes to be considered valid. Paxos uses quorums to ensure safety and liveness despite node failures.

• Write Quorum (W): Number of nodes that must acknowledge a write.
• Read Quorum (R): Number of nodes queried for a read. Setting R + W > N (where N is replication factor) guarantees strong consistency. This is a building block for replicated state machines and distributed locks, which are key for coordinating access to shared agent memory.