Quorum

The most fundamental quorum mechanism, where a decision is valid if more than half of the total members agree. This provides basic fault tolerance against non-malicious crashes.

• Formula: Q = floor(N/2) + 1
• Example: In a 5-node cluster, at least 3 nodes must agree.
• Fault Tolerance: Can tolerate up to floor((N-1)/2) failures. For 5 nodes, it tolerates 2 failures.
• Use Case: Common in leader election and basic consensus where Byzantine (malicious) faults are not a primary concern.

A stricter quorum required for systems where nodes may fail arbitrarily or maliciously (Byzantine faults). It ensures safety despite a subset of nodes acting adversarially.

• Formula: Q = floor(2N/3) + 1
• Rationale: Requires more than two-thirds agreement to overcome conflicting votes from faulty nodes.
• Fault Tolerance: Can tolerate up to floor((N-1)/3) Byzantine failures. A 4-node system tolerates 1 malicious node.
• Use Case: Critical for blockchain consensus (e.g., Tendermint) and secure multi-party computation where trust is not assumed.

Used in distributed databases like DynamoDB and Cassandra to tune consistency vs. availability. A read operation must contact a Read Quorum (R) of nodes; a write must contact a Write Quorum (W).

• Core Rule: To guarantee read-after-write consistency, the quorums must overlap: R + W > N.
• Tunable Consistency: Setting R=1, W=N provides strong consistency but low write availability. Setting R=1, W=1 provides high availability but eventual consistency.
• Example: In a 3-node system, a common configuration is R=2, W=2. This ensures at least one node has the latest data for any read.

The relationship between the total number of agents (N), the required quorum size (Q), and the number of failures (f) the system can withstand is defined by core inequalities.

• For Crash Faults (Simple Majority): N = 2f + 1. The system needs a majority of non-faulty nodes: Q = f + 1.
• For Byzantine Faults: N = 3f + 1. The system needs a supermajority of correct nodes: Q = 2f + 1.
• Implication: Tolerating Byzantine faults requires significantly more nodes. To tolerate 1 malicious node, you need at least 4 total nodes (N=4, f=1, Q=3).

In heterogeneous systems, not all agents have equal importance. Weighted voting assigns different voting power to agents based on criteria like compute capacity, stake, or reliability.

• Mechanism: A quorum is reached when the sum of voting weights from agreeing agents meets a predefined threshold (e.g., >50% of total weight).
• Use Case: Blockchain proof-of-stake systems, where a node's voting power is proportional to the cryptocurrency it has staked.
• Dynamic Adjustment: Weights can be adjusted automatically based on performance metrics or reputation scores, allowing the system to self-optimize and isolate unreliable agents.

A fundamental safety property for any quorum-based system: any two quorums must intersect in at least one correct node. This prevents the system from making contradictory decisions.

• Mathematical Guarantee: If Q1 and Q2 are quorums, then |Q1 ∩ Q2| ≥ 1 (for at least one correct node).
• Consequence: It is impossible for two disjoint groups to each believe they have a valid quorum, preventing split-brain scenarios.
• Enforcement: The formulas for Q (e.g., Q > N/2) are designed specifically to guarantee this intersection property.

A property of a distributed system that allows it to reach consensus and continue operating correctly even when some of its components fail arbitrarily, including by sending malicious or conflicting information. BFT protocols require stricter quorum calculations.

• Failure Model: Handles the most severe failure type, where nodes may behave maliciously ("Byzantine" failures).
• Quorum Requirement: Typically requires a quorum of more than two-thirds of nodes to agree to tolerate Byzantine faults. For N nodes tolerating f failures, the rule is often N > 3f.
• Contrast: Differs from crash-fault tolerance, which assumes nodes fail only by stopping.

A catastrophic failure condition in high-availability clusters where a network partition causes independent sub-clusters to believe they are the sole active group, leading to data corruption and conflicts. Proper quorum configuration is the primary defense.

• Cause: Occurs when communication links fail, splitting the cluster into isolated partitions.
• Risk: Each partition may elect its own leader and process conflicting writes, violating consistency.
• Prevention: Implemented by defining a quorum size greater than half the total nodes. Only the partition that can assemble a quorum is allowed to operate; the other partition is fenced off and becomes unavailable.

A core fault-tolerance technique where a deterministic service is replicated across multiple machines. Each replica processes the same sequence of requests in the same order to produce identical state transitions and outputs. Quorums are used to agree on the request sequence.

• Mechanism: A consensus protocol (like Raft) uses quorums to agree on a log of commands. Once a command is committed to the log by a quorum, it is applied to all replicas' state machines.
• Guarantee: Provides linearizability, ensuring all clients see a consistent, up-to-date view of the system state.
• Foundation: The primary method for building highly available, consistent services like distributed databases (e.g., etcd, Consul).

A fundamental theorem stating that a distributed data store can provide only two of the following three guarantees simultaneously: Consistency, Availability, and Partition tolerance. Quorum-based systems explicitly navigate these trade-offs.

• Consistency (C): Every read receives the most recent write.
• Availability (A): Every request receives a (non-error) response.
• Partition Tolerance (P): The system continues operating despite network partitions.
• Quorum's Role: A system using quorums for consistency (CP) may become unavailable if a partition prevents it from achieving a quorum. Conversely, a system prioritizing availability (AP) might use techniques like last-write-wins without quorums, sacrificing strong consistency.