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
- Denys Zhak (ORCID: https://orcid.org/0009-0003-6426-0952)
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