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.
Where it lands in Jayverse
- Devnet: set the sequencer's quorum explicitly for the OP-Stack L2. When the OP-Stack stage happens, choose Q1/Q2 deliberately (not just "majority") using the size(Q1)+size(Q2)>N condition, and document the latency/failure-tolerance tradeoff the way the exercise's (3,3)/(4,2)/(2,4) table does.
- Verex: apply the same rule if resolution ever becomes multi-source. Should market resolution move from a single oracle to a committee, use size(Q1)+size(Q2)>N for propose vs confirm quorums instead of assuming a plain majority in both.
- Bridge: tune the relayer's confirmation quorum on purpose. Decide explicitly how many relayer/attester signatures gate a mint, trading steady-state latency against failure recovery, rather than defaulting to "majority" without stating the tradeoff.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| steady state | 정상 상태(시스템이 안정적으로 반복 운용되는 구간) · 매 라운드 준비 단계를 생략할 수 있는 조건 · "in the steady state a value is decided" |
| quorum | 정족수(의사결정에 필요한 최소 응답 수) · 합의 프로토콜에서 다수결 기준을 가리킬 때 · "each requiring a majority quorum's response" |
| turning quorum size into a dial | 정족수 크기를 조절 가능한 손잡이로 바꾸다 · 트레이드오프 조절 변수로 만들 때 · "turning quorum size into a dial" |
| pairwise intersect | 쌍마다 서로 겹치다(교집합을 가지다) · 기존 정족수 조건이 요구하던 성질을 말할 때 · "all quorums had to pairwise intersect" |
| leader replacement | 리더 교체(장애 시 새 리더 선출) · 정족수 조합별로 가능 여부가 달라질 때 · "whether leader replacement is possible for each" |
| shrink the write quorum | 쓰기 정족수를 줄이다 · 정상 상태의 지연을 낮추기 위한 조치 · "shrink the write quorum to lower steady-state latency" |
| enlarging the leader-election quorum | 리더 선출용 정족수를 키우다 · 장애 복구용 정족수를 대신 늘릴 때 · "enlarging the leader-election quorum instead" |
| RTT | 왕복 시간(Round-Trip Time) · 리더 기반 프로토콜에서 정상 경로가 왜 1회 왕복인지 설명할 때 · "why is the normal path 1 RTT" |
| HA | 고가용성(High Availability) · 시퀀서 등 인프라가 장애에도 계속 동작하도록 설계된 구성 · "Blockchain consensus and sequencer HA setups" |
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/.