Multi-Paxos and Flexible Paxos — The Freedom in Quorum Design TODO
Concept
Basic Paxos agrees on a single value through two phases, prepare and accept, each requiring a majority quorum's response. Multi-Paxos, when agreeing on a sequence of instances, has a stable leader secure the prepare phase once up front rather than repeating it per instance, so in the steady state a value is decided in a single accept round. It was traditionally believed that all quorums had to pairwise intersect, but Flexible Paxos showed the condition actually required for safety is only that the phase-1 quorum and the phase-2 quorum intersect — that is, only |Q1| + |Q2| > N is needed, with no requirement that Q1's intersect each other or Q2's intersect each other. This freedom makes it possible to shrink the write quorum to lower steady-state latency while enlarging the leader-election quorum instead, turning quorum size into a dial that trades off steady-state performance against failure-recovery availability.
The latency and fault tolerance of a consensus system are mostly decided by quorum-size choices, and holding onto the "always a majority" intuition alone means missing that room to tune. It's also where the "why is the normal path 1 RTT" answer for leader-based protocols comes from.
Code & Formula
# Multi-Paxos·Flexible Paxos — 정족수 설계의 자유도.
# 안전성 조건은 |Q1| + |Q2| > N 뿐이며, Q1(prepare)과 Q2(accept)가 같은 크기일 필요는 없다.
from itertools import combinations
N = 5 # 전체 노드 수
def quorums_intersect_safely(q1_size, q2_size, n=N):
"""모든 가능한 Q1, Q2 조합이 항상 겹치는지 직접 확인 (|Q1|+|Q2|>N과 동치)"""
nodes = set(range(n))
for q1 in combinations(nodes, q1_size):
for q2 in combinations(nodes, q2_size):
if not (set(q1) & set(q2)):
return False
return True
print(f"N={N} 노드 클러스터에서 (Q1=prepare 정족수, Q2=accept 정족수) 조합별 안전성:\n")
for q1_size, q2_size in [(3, 3), (4, 2), (2, 4), (2, 2), (3, 2)]:
condition_holds = q1_size + q2_size > N
actually_safe = quorums_intersect_safely(q1_size, q2_size)
assert condition_holds == actually_safe, "조건식과 실제 검증이 불일치"
label = "SAFE" if actually_safe else "UNSAFE (충돌 가능)"
print(f" Q1={q1_size}, Q2={q2_size}: |Q1|+|Q2|={q1_size+q2_size} > N={N} ? "
f"{condition_holds} -> {label}")
print("\n(4,2): accept 정족수를 2로 줄이면 정상 경로 지연은 낮아지지만")
print(" prepare(리더 선출) 정족수를 4로 키워야 안전성이 유지된다 — 트레이드오프의 손잡이.")
docs/code/algorithms/algorithms-55.py
Exercise
With N=5 nodes, set (Q1, Q2) to (3,3), (4,2), and (2,4), and tabulate the steady-state latency, how many simultaneous failures each tolerates, and whether leader replacement is possible for each, to find where the safety condition breaks.
Practical Connection
Blockchain consensus and sequencer HA setups also have their confirmation latency and availability jointly decided by "how many node responses do we wait for," so this quorum-design intuition transfers directly.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.