KCensus: Synthesizing Latency-Optimal Consensus Fast Paths (Extended Version)
In the authors' words
Strongly consistent geo-replication often relies on fast paths to reduce latency in the common case of no failures or contention. Existing fast-path schemes, however, are ad hoc and restrictive: each corresponds to a point in a broad design space shaped by network topology, workload, and latency objective, so no single scheme works best across settings. This paper looks at fast-path schemes from a new perspective, as mechanisms that spread knowledge about proposals. With this view, we identify a fundamental condition on the spread of knowledge for a fast-path scheme to work. We then introduce KCensus, a framework that turns this condition into an optimization problem, synthesizing new fast-path schemes that are optimal for a given setting. We use KCensus to build a geo-replicated key-value store and evaluate it across AWS regions. Our system outperforms competing protocols, with up to 16% lower average latency.
Appeared: Monday, September 28. arXiv. Preprint with a published version.
Published version: 10.1145/3842654.3848528
Authors' comment: 38 pages, 15 figures. Extended version of the paper to appear in the 22nd European Conference on Computer Systems (EuroSys '27), Rabat, Morocco. Includes appendices with full correctness and optimality proofs