Memory Quorum

A quorum system is designed to tolerate node failures without halting the system. By requiring only a majority (or other defined subset) of nodes to be operational, it ensures high availability. For a cluster of N nodes, a typical write quorum might be W > N/2, allowing the system to remain writable even if N - W nodes fail. This is a core principle behind systems like Apache ZooKeeper and etcd.

Quorums enforce strong consistency models like linearizability. The rule R + W > N, where R is the read quorum, W is the write quorum, and N is the replication factor, guarantees that any read operation intersects with the set of nodes containing the most recent write. This prevents stale reads and is fundamental to CP (Consistency-Partition tolerance) systems in the CAP theorem.

The behavior of a quorum system is tuned by adjusting three key parameters:

• N (Replication Factor): Total number of copies.
• W (Write Quorum): Nodes that must acknowledge a write.
• R (Read Quorum): Nodes contacted for a read.

Configurations:

• High Read Performance: Set R=1, W=N. Reads are fast, writes are slow.
• High Write Performance: Set W=1, R=N. Writes are fast, reads are slow.
• Balanced: Set R=W=ceil((N+1)/2) for equal latency.

In production, clusters are not static. Quorum systems must handle nodes joining, leaving, or failing. Protocols like Raft and Paxos include membership change algorithms that safely transition the cluster from one configuration (e.g., 3 nodes) to another (e.g., 5 nodes) while maintaining the quorum property and preventing split-brain scenarios where two majorities could form independently.

The fundamental safety property of any quorum system is that quorums must intersect. Any two quorums (e.g., a read quorum and a write quorum) must share at least one node. This intersection ensures there is always a node that can act as a witness to the most recent state, enabling the system to agree on a single history of operations. This property is what distinguishes a quorum from a simple majority vote on independent proposals.

Quorum operations have inherent latency, as they require waiting for responses from multiple, potentially geographically distributed, nodes. During a network partition, a quorum may become unreachable. If a majority of nodes are on one side of the partition, that side can still form a quorum and remain operational. The minority side cannot form a quorum and will become unavailable, sacrificing availability (A) for consistency (C).

The process by which multiple nodes in a network agree on a single data value or state, despite the possibility of node failures or network partitions. It is the foundational problem that quorum-based protocols solve.

• Core Protocols: Includes Paxos, Raft, and Byzantine Fault Tolerance (BFT) variants.
• Purpose: Ensures all non-faulty nodes execute the same sequence of operations, maintaining a single system image.
• Relation to Quorum: A quorum is the minimum participating subset required for a consensus round to proceed and be considered valid.

A formal contract that defines the guarantees about the order and visibility of read and write operations across multiple nodes in a distributed system. It specifies the system's behavior from the perspective of clients.

• Strong Consistency: Guarantees that any read receives the most recent write. Requires strict quorum enforcement for all operations.
• Eventual Consistency: Guarantees that if no new updates are made, all reads will eventually return the last written value. Often uses looser quorum rules for writes.
• Causal Consistency: Preserves the order of causally related operations. Quorum mechanisms must track and respect causality.

A primary replication strategy where a single leader node coordinates all write operations, which are then replicated to one or more follower nodes. Quorum concepts are critical for leader election and commit safety.

• Write Acknowledgement: A write is often considered durable only after a write quorum of followers has acknowledged receipt.
• Leader Election: If a leader fails, a new leader is elected via a consensus protocol that requires a quorum of votes from the remaining nodes.
• Example: The Raft consensus algorithm uses leader-based replication with strict quorum requirements for log entry commitment.

The property of a distributed system to reach consensus and function correctly even when some components fail arbitrarily or behave maliciously (Byzantine faults). BFT protocols have stricter quorum requirements than crash-fault-tolerant protocols.

• Quorum Size: Typically requires that more than two-thirds of nodes are non-faulty. For N total nodes and f faulty nodes, N > 3f.
• Practical Byzantine Fault Tolerance (PBFT): A classic BFT algorithm where a client request is considered committed once the client receives f+1 matching replies from different nodes, which implies a correct quorum was achieved.
• Use Case: Critical for systems in adversarial environments, like blockchain networks and certain financial or defense systems.

A data structure designed for distributed systems that can be updated concurrently by multiple agents without coordination, and whose state can always be merged deterministically. CRDTs often operate under eventual consistency with minimal quorum requirements.

• Operation: Each replica applies operations locally and asynchronously propagates updates. Merging is commutative, associative, and idempotent.
• Quorum Relation: Because merges are deterministic, CRDTs can achieve consistency without requiring synchronous quorums for every operation, simplifying system design.
• Examples: G-Counters (grow-only counters), PN-Counters (positive-negative counters), and OR-Sets (observed-remove sets).

A distributed consensus protocol that coordinates all participating nodes to atomically commit or abort a transaction. It uses a quorum-like principle in its second phase.

• Phase 1 (Prepare): The coordinator asks all participants if they can commit. All must vote Yes to proceed.
• Phase 2 (Commit): If all participants voted Yes, the coordinator instructs all participants to commit. This is a unanimous quorum requirement.
• Contrast with Quorum: 2PC requires unanimity (N out of N), which is a strict form of quorum. It is blocking and can suffer from coordinator failure, unlike more flexible quorum-based consensus.