Quorum-based Systems

Quorum systems are fundamental to the functioning of many distributed applications, providing a mechanism for achieving consensus and ensuring data consistency in environments where nodes may fail or be unreliable. This blog post will look at the complexities of quorum systems, exploring their mechanisms, various types, and applications.

Understanding the Core Concept: Quorum

At its heart, a quorum system is a collection of subsets (quorums) of a larger set of nodes (e.g., servers, replicas). The defining characteristic is that any two quorums must have at least one node in common. This seemingly simple requirement is important because it guarantees that if a decision is reached by one quorum, it automatically involves at least one member of any other quorum, ensuring consistency.

Imagine a distributed database replicated across five servers (A, B, C, D, E). A simple quorum system might define quorums as any three servers. If a write operation obtains a quorum of (A, B, C), and a subsequent read operation obtains a quorum of (B, C, D), they share servers B and C, ensuring data consistency. If a quorum doesn’t overlap, it opens the possibility of conflicting data versions.

graph LR
    A[Server A] --> Q1((Quorum 1: A, B, C))
    B[Server B] --> Q1
    C[Server C] --> Q1
    B --> Q2((Quorum 2: B, C, D))
    C --> Q2
    D[Server D] --> Q2
    subgraph "Overlap"
        B;C
    end

Types of Quorum Systems

Several types of quorum systems exist, each with its strengths and weaknesses:

1. Simple Majority Quorum:

This is the simplest form, requiring a majority of the nodes to form a quorum. For example, with five nodes, any three or more nodes constitute a quorum. It’s easy to understand and implement but can be vulnerable if a significant number of nodes fail.

graph LR
    A[Server A] --> Q1((Quorum 1: A, B, C))
    B[Server B] --> Q1
    C[Server C] --> Q1
    D[Server D] --> Q2((Quorum 2: A, D, E))
    E[Server E] --> Q2
    A --> Q2

    subgraph "Overlap"
        A
    end

2. Weighted Voting Quorum:

This extends the simple majority approach by assigning weights to each node. A quorum is formed when the total weight of participating nodes exceeds a predefined threshold. This allows for handling situations where nodes have different capabilities or importance.

Example (Python):

nodes = {
    'A': 2,
    'B': 1,
    'C': 1,
    'D': 2,
    'E': 3
}

threshold = 4

def is_quorum(nodes_involved):
  total_weight = sum(nodes[node] for node in nodes_involved)
  return total_weight >= threshold

print(is_quorum(['A', 'B', 'E'])) # True (2 + 1 + 3 = 6 >= 4)
print(is_quorum(['A', 'B', 'C'])) # False (2 + 1 + 1 = 4 >= 4)

3. Path Quorum Systems:

These are especially useful in distributed systems with a hierarchical or network-like structure. A quorum is defined as a path connecting two specified nodes, ensuring connectivity and resilience.

graph TD
    subgraph "Successful Path Quorum"
        A1((Node A)) --- B1((Node B))
        B1 --- C1((Node C))
        C1 --- D1((Node D))
        A1 --- E1((Node E))
        E1 --- D1
        style A1 fill:#90EE90
        style D1 fill:#90EE90
        style B1 fill:#90EE90
        style C1 fill:#90EE90
        style E1 fill:#lightgrey
    end

    subgraph "Failed Path Quorum"
        A2((Node A)) --- B2((Node B))
        B2 -.- C2((Node C))
        C2 --- D2((Node D))
        A2 --- E2((Node E))
        E2 -.- D2
        style A2 fill:#FFB6C1
        style D2 fill:#FFB6C1
        style C2 fill:#lightgrey
        style B2 fill:#FFB6C1
        style E2 fill:#FFB6C1
    end

In this visualization:

Successful Path Quorum:

Failed Path Quorum:

The key aspects:

4. Grid Quorum Systems:

Suitable for distributed systems arranged in a grid topology, quorums are defined as subsets of nodes that form a connected component in the grid.

graph TD
    subgraph "Successful Grid Quorum"
        A1((1)) --- B1((2)) --- C1((3))
        A1 --- D1((4)) --- E1((5)) --- F1((6))
        D1 --- G1((7)) --- H1((8)) --- I1((9))
        
        style A1 fill:#90EE90
        style D1 fill:#90EE90
        style E1 fill:#90EE90
        style H1 fill:#90EE90
        style I1 fill:#90EE90
    end

    subgraph "Failed Grid Quorum"
        A2((1)) --- B2((2)) --- C2((3))
        A2 -.- D2((4))
        D2 --- E2((5)) --- F2((6))
        D2 --- G2((7)) --- H2((8)) -.- I2((9))
        
        style A2 fill:#FFB6C1
        style D2 fill:#FFB6C1
        style E2 fill:#FFB6C1
        style H2 fill:#FFB6C1
        style I2 fill:#FFB6C1
        style B2 fill:#lightgrey
        style C2 fill:#lightgrey
    end

Key aspects:

Successful Quorum:

Failed Quorum:

This structure ensures:

Applications of Quorum Systems

Quorum systems are ubiquitous in various distributed systems:

Trade-offs and Considerations

The choice of a quorum system involves trade-offs: