Quorum

A quorum is mathematically defined as a majority of nodes in a cluster. For a cluster with N nodes, the quorum size Q is typically Q = floor(N/2) + 1. This ensures that any two quorums must intersect in at least one node, preventing split-brain scenarios where two separate groups of nodes could accept conflicting writes. For example, in a 5-node cluster, a quorum is 3 nodes.

The primary role of a quorum is to enforce strong consistency in distributed systems like vector databases. For a write operation to be acknowledged to the client, it must be durably recorded on a quorum of replica nodes. Similarly, a read operation must consult a quorum to guarantee it retrieves the most recent written value. This mechanism is the basis for consensus protocols like Raft and Paxos.

A quorum-based system is explicitly designed to tolerate node failures while remaining available for writes. The system can sustain F failures and still achieve a quorum, where F = floor((N-1)/2). This defines the system's fault tolerance. For instance, a 5-node cluster (quorum of 3) can tolerate up to 2 simultaneous node failures and still accept writes, as 3 live nodes can form a quorum.

In configurable systems, quorums can be tuned separately for read (R) and write (W) operations, governed by the formula R + W > N. This allows architects to optimize for their workload:

• Write-heavy: Set a high W for strong durability, lower R for faster reads.
• Read-heavy: Set a high R for strongly consistent reads, lower W for faster writes. Choosing W as a majority ensures strong consistency.

Quorums are the atomic unit of agreement in distributed consensus protocols. In Raft, a leader must replicate log entries to a quorum of followers before committing them. In Paxos, a proposer must receive promises from a quorum of acceptors to proceed. These protocols use quorums to ensure that only one value can be agreed upon for a given log index, even during network partitions.

A quorum system is a practical implementation of the trade-offs in the CAP Theorem. By requiring a majority of nodes to agree, the system prioritizes Consistency and Partition Tolerance (CP). During a network partition, if a majority of nodes (a quorum) cannot communicate, the system will become unavailable for writes to prevent inconsistency, formally sacrificing Availability to maintain the consistency guarantee.

In protocols for distributed transactions, such as Paxos Commit or its variants, a quorum is used to reach agreement on whether to commit or abort a transaction across multiple database shards.

• Two-Phase Commit (2PC) Coordinator: The coordinator decides the transaction's fate based on votes from all participants (requires unanimity, not a quorum).
• Paxos-Based Commit: Improves fault tolerance by requiring only a quorum of participants to agree, allowing the transaction to proceed even if some nodes fail.
• Use Case: Critical for maintaining ACID properties across a sharded vector database during updates that span multiple partitions.

A consistency model defines the contract that specifies how and when a write to a distributed data store becomes visible to subsequent read operations. Quorum is a specific implementation used to enforce a particular consistency level.

• Strong Consistency: Guarantees any read returns the most recent write. Quorum reads/writes are often used to achieve this.
• Eventual Consistency: Guarantees replicas will converge to the same state eventually, but reads may be stale. This often uses a lower quorum or none.
• Linearizability: The strongest model, combining real-time order with single-operation atomicity. A correctly configured quorum system can provide linearizability.

The replication factor is a configuration parameter that defines how many copies (replicas) of each data item are maintained across different nodes. It directly determines the possible quorum configurations.

• A common setup is a replication factor of 3.
• With 3 replicas, a write quorum might be 2 (a majority) and a read quorum might be 2. This ensures every read intersects with every write.
• The formula for a fault-tolerant majority quorum is: Q = floor(N / 2) + 1, where N is the replication factor.
• A higher replication factor increases durability but also increases the cost of achieving a quorum.

Leader election is the process in distributed systems where nodes collectively choose one node to act as the coordinator (leader) for managing writes and often for coordinating quorum decisions.

• The leader is responsible for proposing write operations and ensuring they achieve quorum across follower replicas.
• Protocols like Raft and Paxos integrate leader election with log replication and quorum consensus.
• If a leader fails, the system must elect a new one to continue processing writes that require quorum, ensuring high availability.
• This prevents split-brain scenarios where two nodes could believe they are leader and create conflicting quorums.

The CAP theorem is a fundamental principle stating a distributed data system can provide at most two out of three guarantees: Consistency, Availability, and Partition tolerance. Quorum-based systems explicitly navigate this trade-off.

• Consistency (C): Achieved by requiring read/write quorums to overlap.
• Availability (A): Compromised during a partition if the required quorum size cannot be reached on one side of the network split.
• Partition Tolerance (P): The system must be designed to withstand network partitions.
• A quorum system typically chooses CP (Consistency & Partition Tolerance): it remains consistent during a partition but may become unavailable for writes if the quorum is lost.

These are two methods for updating replicas, defining when a write operation is acknowledged to the client. Quorum is closely tied to synchronous replication.

• Synchronous Replication: The write is only acknowledged after data has been successfully written to a quorum of replicas (e.g., 2 out of 3). This ensures strong consistency but increases client latency.
• Asynchronous Replication: The write is acknowledged after the primary node writes it locally. Replicas are updated in the background. This favors low latency and high availability but risks data loss if the primary fails before replicas are updated.
• Vector databases prioritizing semantic search accuracy often use synchronous replication with quorum to guarantee readers see the latest ingested embeddings.

The Dynamo-style quorum model, often expressed as NWR, provides tunable consistency. N is the replication factor, W is the write quorum size, and R is the read quorum size.

• The rule for strong consistency is: W + R > N. This guarantees that the set of nodes read from and written to must overlap.
• Example: With N=3, setting W=2 and R=2 ensures strong consistency. Setting W=1, R=1 favors speed but allows stale reads.
• This model allows system architects to dynamically tune the consistency vs. latency trade-off based on the specific vector operation (e.g., strong consistency for writes, eventual for some background similarity searches).