SD9.4 · LESSON 4 OF 6

Quorums and progress

Explain consensus, logical ordering, leases and fencing under stated failure and timing assumptions.

THE IDEA

Quorums and progress

A group of n members needs a quorum of ⌊n/2⌋ + 1 to decide: 3 of 5, which tolerates 2 unavailable members. A 4-member group also needs 3 and so tolerates only 1: no better than 3 members. A minority that cannot reach the others must not elect itself, because the majority side could elect another leader and the two would diverge. Being safe (never two leaders) and being able to serve fresh operations are separate properties.

group size n5members that can talk to each other3

12345

quorum = ⌊5/2⌋ + 1 = 3 failures tolerated = 5 − 3 = 2 communicating members 3: a majority exists: progress is possible an even size such as 6 tolerates no more failures than 5

A group of 2f + 1 members survives f unavailable ones while the rest can still communicate. A smaller side must not elect itself, because two sides that both elect leaders would diverge. Safety (never two leaders) and the ability to serve fresh operations are different questions.

Change the group size and who can talk.

Predict first. Can a two-member minority safely elect itself as the only leader of a fixed five-member group?

Chapter context

Coordination lets multiple processes agree on selected shared decisions even though messages can be delayed or lost and participants can stop. Agreement is achieved by a protocol, not by adding a shared timestamp or an informal majority rule.

TRY IT YOURSELF

Part 1. Do it hands-on

Size quorums by hand, then write the rules and a split-brain check.

group size n5members that can talk to each other3

12345

quorum = ⌊5/2⌋ + 1 = 3 failures tolerated = 5 − 3 = 2 communicating members 3: a majority exists: progress is possible an even size such as 6 tolerates no more failures than 5

quorum of 5 failures tolerated by 5 quorum of 4 failures tolerated by 4 a 2-member minority of 5 may elect itself? (yes/no)

To do: Quorum size of a 5-member group (⌊n/2⌋ + 1)?
To do: Members of that group that can be unavailable while a communicating majority remains?
To do: Quorum size of a 4-member group?
To do: Failures a 4-member group can tolerate (no better than 3 members)?
To do: Can a two-member minority of a fixed five-member group safely elect itself as the only leader? Type yes or no

Part 2. Do it in code

quorum(n): ⌊n/2⌋ + 1. tolerated(n): n − quorum(n), the members that may be unavailable while a majority remains.
members_for(f): the smallest group that tolerates f failures: 2f + 1.
can_progress(n, reachable): a group makes progress only if the members that can communicate with each other are at least a quorum.
partition_outcome(n, groups): groups is a list of group sizes (a partition). Return a dict {"leader_possible": the index of the group that has a quorum (at most one), or None; "safe": True if no two groups could both elect a leader}.
unsafe_split_brain(n, group_a, group_b, sloppy_quorum): if every group elects when it holds at least `sloppy_quorum` members, return True when BOTH groups meet that threshold (two leaders = unsafe).

def quorum(n):
    pass

def tolerated(n):
    pass

def members_for(f):
    pass

def can_progress(n, reachable):
    pass

def partition_outcome(n, groups):
    pass

def unsafe_split_brain(n, group_a, group_b, sloppy_quorum):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can a two-member minority safely elect itself as the only leader of that fixed five-member group?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For a fixed n-member majority group, quorum size is $\lfloor n/2\rfloor+1$ . A 2f+1-member group can lose f members while retaining a majority, provided the remaining participants can communicate and the protocol's other assumptions hold. Fencing requires monotonically ordered tokens and enforcement at the resource.

Worked example

Five members require three votes, allowing two unavailable members while a communicating majority remains. Separately, a resource has already accepted token 8 from a new owner. An old owner's delayed operation bearing token 7 must be rejected, regardless of whether the old process still believes it owns the lease.

Reference code

The following example uses the Python standard library and does not call a remote service.

members=5
quorum=members//2+1
assert quorum == 3 and members-quorum == 2
highest=8
def accept(token):
    global highest
    if token < highest: return False
    highest=token
    return True
assert not accept(7)
assert accept(8)
assert accept(9)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A timeout cannot establish a remote process's state. Quorums require full protocol rules. Fencing is ineffective if the resource accepts stale tokens or an attacker can invent authorized tokens.