Quorum Consensus

The quorum size is the minimum number of participating nodes required for an operation. The most common rule is a simple majority (N/2 + 1), where N is the total number of replicas. This ensures that any two quorums intersect, guaranteeing that at least one node has seen the most recent update. For higher fault tolerance, systems may use a super-majority (e.g., 2N/3 + 1) to tolerate more simultaneous failures while maintaining the intersection property.

In quorum-based replicated systems, operations are governed by two configurable parameters:

• Write Quorum (W): The number of nodes that must acknowledge a write for it to be successful.
• Read Quorum (R): The number of nodes that must be contacted to read a value. To guarantee strong consistency, these values must satisfy the rule R + W > N, where N is the total replica count. This ensures that every read contacts at least one node with the latest written value. For example, with N=3, a common configuration is W=2, R=2.

The fundamental guarantee of any quorum system is the intersection property: any two quorums (sets of nodes) must overlap by at least one node. For read/write quorums, this means a read quorum and a write quorum always intersect, ensuring a reader can find the latest written data. This property is what prevents stale reads and maintains linearizability. It is mathematically enforced by the R+W>N rule and is the core reason quorums provide consistency without requiring all nodes to respond to every operation.

Many quorum-based consensus algorithms like Raft and Paxos incorporate a leader election mechanism. A leader is a node elected by a quorum of peers to coordinate all write operations, simplifying the replication log management. The system remains available as long as a quorum of nodes (a majority) is alive and can communicate. This provides fault tolerance for up to f crash failures in a cluster of 2f + 1 nodes. If a leader fails, a new election is held among the remaining nodes to elect a new leader, ensuring liveness.

To order events and detect conflicts in quorum systems, nodes use logical timestamps. Lamport timestamps provide a partial causal order. Version vectors (or vector clocks) are used in systems with multi-leader replication to track the update history per replica. When a read quorum gathers data, it compares version vectors from each node. If vectors are concurrent, a conflict is detected, requiring resolution (e.g., application-specific merge or Last-Writer-Wins). This mechanism is crucial for understanding causality in eventually consistent quorum systems.

Quorum systems directly interact with the CAP theorem. A strict majority quorum prioritizes Consistency and Partition tolerance (CP) but may sacrifice Availability during a network partition if a quorum cannot be formed. By adjusting the R and W values, engineers can tune the consistency-availability trade-off:

• Strong Consistency: High W and R (e.g., W=N, R=1).
• High Availability: Low W or R (e.g., W=1, R=1), but risks stale reads. This tunability allows systems to be optimized for specific workload patterns, such as read-heavy or write-heavy applications.

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. Quorum Consensus is one specific type of consensus algorithm.

• Core Purpose: Achieves agreement in the presence of faults (crash or Byzantine).
• Key Examples: Paxos, Raft, and Practical Byzantine Fault Tolerance (PBFT).
• Relation to Quorum: Many consensus algorithms, including Raft, use a quorum (majority of nodes) to safely commit log entries and elect leaders.

A foundational family of protocols for solving consensus in a network of unreliable processors. It provides a fault-tolerant mechanism for a distributed system to agree on a single value, even if some nodes fail.

• Core Components: Proposers, Acceptors, and Learners.
• Quorum Role: Requires a majority (quorum) of Acceptors to promise and accept a proposal for it to be chosen.
• Legacy: The theoretical basis for many practical distributed systems and a direct precursor to algorithms like Raft.

A consensus algorithm designed for understandability, which manages a replicated log and elects a leader to coordinate updates across a cluster of machines. It is a modern, widely implemented alternative to Paxos.

• Leader-Based: A single elected leader handles all client requests and log replication to followers.
• Quorum Mechanism: Relies on a majority quorum for both leader election and log commitment, ensuring safety during network partitions.
• Practical Use: The underlying consensus algorithm for systems like etcd and Consul.

The property of a distributed system to resist Byzantine faults, where components may fail in arbitrary ways, including sending malicious or conflicting information to different parts of the system.

• Challenge: More severe than simple crash failures; requires more complex protocols.
• Quorum Requirements: BFT algorithms like PBFT often require a larger quorum (e.g., 2/3 of nodes) to tolerate a certain number of faulty nodes.
• Application: Critical for blockchain networks and high-security multi-agent systems where agents cannot be fully trusted.

A consistency model where any read operation on a data item returns a value corresponding to the result of the most recent write operation, as perceived by all nodes. It provides a linearizable view of the system.

• Guarantee: Preserves the illusion of a single, up-to-date copy of data.
• Implementation: Often achieved using consensus protocols like Raft or Paxos with quorum reads and writes.
• Trade-off: Typically comes at the cost of higher latency compared to weaker models like eventual consistency.

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 stronger guarantee than regular broadcast.

• Equivalence: Solving Atomic Broadcast is equivalent to solving Consensus.
• Quorum Use: Implementations often use a leader and quorum acknowledgments to establish the final delivery order.
• Purpose: Fundamental for implementing State Machine Replication, where all replicas must execute commands identically.