Read-Write Quorum Load under Known Crashes

We study how evenly a read–write quorum system can spread traffic when clients know which servers have crashed. The quorum families are fixed in advance, and clients choose among the surviving quorums. We minimize the contact probability of the busiest server in the worst case over failure sets. For systems that tolerate two crashes, we determine the exact optimum at small read fractions. Write the cluster size as n = 3k + r ≥ 9, with r in {0, 1, 2}. The optimum is (3 + (k − 1)α)/(n − 2) for read fractions 0 ≤ α ≤ (r + 1)/(k² + k + r − 1). For each cluster size, one fixed design with three-server writes attains this optimum throughout the interval. At every positive read fraction in the interval, voting designs with one fixed weight per server shared by both phases and thresholds whose sum exceeds the total vote weight have strictly higher worst-case load. Swapping reads and writes gives the corresponding result when writes are rare. For a general crash budget f, we give constant-factor bounds across all read fractions when n − f ≥ 16f². When min{α, 1 − α} · n/f² tends to infinity, the optimum is asymptotic to 2√(α(1 − α)/n). In the same regime, choosing contacts in advance that can withstand any f crashes raises the optimum by a factor asymptotic to √(2f + 1). Lean verifies the two-crash lower bound and the asymptotic comparison. The matching two-crash upper bound for every n ≥ 9 combines a written proof, a cyclic construction verified in Lean, and exact certificates for small cases.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-22
DOI
https://doi.org/10.5281/zenodo.24428084
Primary Topic
Distributed systems and fault tolerance
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Read-Write Quorum Load under Known Crashes

Denys Zhak
Zenodo (CERN European Organization for Nuclear Research)
Distributed systems and fault tolerance
preprint

Read-Write Quorum Load under Known Crashes

Denys Zhak
preprint en

Abstract

We study how evenly a read–write quorum system can spread traffic when clients know which servers have crashed. The quorum families are fixed in advance, and clients choose among the surviving quorums. We minimize the contact probability of the busiest server in the worst case over failure sets. For systems that tolerate two crashes, we determine the exact optimum at small read fractions. Write the cluster size as n = 3k + r ≥ 9, with r in {0, 1, 2}. The optimum is (3 + (k − 1)α)/(n − 2) for read fractions 0 ≤ α ≤ (r + 1)/(k² + k + r − 1). For each cluster size, one fixed design with three-server writes attains this optimum throughout the interval. At every positive read fraction in the interval, voting designs with one fixed weight per server shared by both phases and thresholds whose sum exceeds the total vote weight have strictly higher worst-case load. Swapping reads and writes gives the corresponding result when writes are rare. For a general crash budget f, we give constant-factor bounds across all read fractions when n − f ≥ 16f². When min{α, 1 − α} · n/f² tends to infinity, the optimum is asymptotic to 2√(α(1 − α)/n). In the same regime, choosing contacts in advance that can withstand any f crashes raises the optimum by a factor asymptotic to √(2f + 1). Lean verifies the two-crash lower bound and the asymptotic comparison. The matching two-crash upper bound for every n ≥ 9 combines a written proof, a cyclic construction verified in Lean, and exact certificates for small cases.

Zenodo (CERN European Organization for Nuclear Research)
Distributed systems and fault tolerance
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Read-Write Quorum Load under Known Crashes — Denys Zhak · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS