Consensus Algorithm

The non-negotiable guarantee that a consensus algorithm must provide. It ensures that if a value is decided, it is the same value decided by all correct processes (Agreement) and that the decided value was proposed by some process (Validity). This property prevents system divergence and is paramount for applications like financial ledgers or state machine replication. Violating safety means the system has reached an irrecoverably incorrect state.

The guarantee that the system eventually makes progress. A live consensus algorithm ensures that every correct process will eventually decide on some value, provided the system is not permanently partitioned. This property is often in tension with safety, as described by the FLP impossibility result, which states that in an asynchronous network with even one crash failure, no deterministic algorithm can guarantee both safety and liveness. Practical algorithms circumvent this by using timeouts or failure detectors.

The maximum number of faulty processes an algorithm can withstand while maintaining its safety and liveness guarantees. This is a critical design parameter:

• Crash Fault Tolerance (CFT): Algorithms like Raft and Paxos can tolerate f crash failures in a cluster of N = 2f + 1 nodes.
• Byzantine Fault Tolerance (BFT): Algorithms like PBFT or Tendermint can tolerate f arbitrary (malicious) failures in a cluster of N = 3f + 1 nodes. This higher threshold reflects the increased complexity of defending against adversarial behavior.

A fundamental architectural distinction.

• Leader-Based (e.g., Raft, Paxos): A single leader coordinates the consensus process, proposing values and managing log replication to followers. This simplifies the protocol but creates a single point of contention; if the leader fails, the system must execute a leader election sub-protocol, incurring latency.
• Leaderless (e.g., Paxos Synod, some BFT variants): Any node can propose a value, and agreement is reached through a quorum of votes. This avoids a single bottleneck but often requires more communication rounds (O(N²) messages) to resolve conflicts between concurrent proposers.

The network timing model an algorithm assumes, which directly impacts its provable guarantees.

• Synchronous Model: Assumes known, bounded message delays and processing times. Simplifies algorithm design and allows strong guarantees but is unrealistic for wide-area networks like the internet.
• Partially Synchronous Model: Assumes the system is eventually synchronous—there are unknown bounds that eventually hold. This is the most common and practical model for algorithms like Paxos and Raft.
• Asynchronous Model: Makes no timing assumptions. The FLP Impossibility proves that deterministic consensus is impossible in a purely asynchronous system with even one crash failure.

The resource cost of reaching consensus, measured in:

• Message Complexity: The number of messages exchanged per consensus decision (e.g., O(N) for leader-based, O(N²) for some leaderless BFT).
• Latency (Time-to-Finality): The number of sequential communication rounds required (e.g., 2 rounds in normal-case Paxos, 1 round in a stable Raft leadership).
• Throughput: The rate of decisions per second, often limited by leader network bandwidth or the need for global serialization. BFT algorithms typically have higher overhead than CFT algorithms due to the need for cryptographic signatures and more verification steps.

A foundational family of protocols for achieving distributed consensus in a network of unreliable processors. Paxos provides a mathematically proven, fault-tolerant mechanism for a group of agents to agree on a single value. Its core innovation is the use of quorums and multi-phase proposals to ensure safety (no two correct processes decide different values) even with message loss and node failures. While powerful, its complexity led to the development of more understandable alternatives like Raft.

A consensus algorithm designed explicitly for understandability while providing equivalent fault tolerance to Paxos. Raft separates consensus into three key sub-problems:

• Leader election: A stable leader is chosen to manage the log.
• Log replication: The leader replicates commands to follower nodes.
• Safety: Mechanisms ensure state machine safety across leader changes. Its clear separation of concerns and detailed specification have made it a popular choice for building reliable, replicated systems like distributed key-value stores and orchestration controllers.

A property of a distributed system that can achieve consensus despite the presence of Byzantine faults, where components may fail in arbitrary and potentially malicious ways (e.g., sending conflicting messages). Standard consensus algorithms like Paxos and Raft assume crash-stop faults. BFT protocols, such as Practical Byzantine Fault Tolerance (PBFT), are required in adversarial environments like blockchain networks or high-security multi-agent systems where agents or nodes cannot be fully trusted. They are significantly more complex due to the need to handle deception.

A fundamental technique for ensuring consistency in distributed reads and writes, often used within broader consensus algorithms. It requires that an operation (read or write) must receive acknowledgments from a majority or other defined subset of replicas—a quorum—before being considered successful. The key rule is that any two quorums must intersect. This intersection property guarantees that a subsequent read will see the most recent write. It's a building block for implementing linearizable or sequential consistency in replicated data stores.

A communication primitive that is equivalent to the consensus problem. It guarantees that all correct processes in a distributed system deliver the same set of messages in the same total order. This is precisely what is needed for State Machine Replication, where each replica must process identical commands in an identical sequence to maintain consistent state. Algorithms like Paxos and Raft can be viewed as implementations of atomic broadcast. It is a stricter guarantee than reliable broadcast, which only ensures all processes receive the same messages, but not necessarily in the same order.

A fundamental trade-off principle for distributed data systems, formalized by Eric Brewer. It states that it is impossible for a distributed system to simultaneously provide all three of the following guarantees:

• Consistency (C): Every read receives the most recent write.
• Availability (A): Every request receives a response.
• Partition Tolerance (P): The system continues operating despite network partitions. Consensus algorithms like Paxos and Raft are designed for CP systems—they prioritize consistency and partition tolerance, potentially sacrificing availability during a partition until a majority can communicate.