KCensus: Synthesizing Latency-Optimal Consensus Fast Paths (Extended Version)

1 Introduction

• Existing fast paths hard-code communication, quorum, and recovery choices, although the best choice depends on topology, proposer, and latency metric.Average-latency and tail-latency winners differ, and tail-latency winners also change across deployments.Source: §1 · p. 1
• Recoverability requires different committed values to remain distinguishable after failures, and fast paths satisfy this through quorums larger than f and surviving evidence across conflicting-quorum intersections.The paper proves these conditions necessary and sufficient.Source: §1 · p. 1
• KCensus encodes each proposer’s strategy as a knowledge requirement and selects compatible requirements that minimize the target latency.The design uses the network topology and proposer distribution.Source: §1 · pp. 1–2
• Up to 16% lower average latency: the geo-replicated store achieves the best targeted metric in contention-free experiments.Its fast path is optimized for network topology, proposer distribution, and target latency metric.Source: Figure 1 · p. 1, §1 · p. 2
• The paper formulates recoverability, derives necessary and sufficient fast-path knowledge conditions, and presents a framework that synthesizes optimal strategies for a given setting.It implements KCensus in a geo-distributed key-value store and evaluates it across AWS deployments.Source: §1 · p. 2

2.1 Replication and consensus

• State Machine Replication uses consensus to order deterministic commands so replicas provide clients a single fault-tolerant service with strong consistency.Processes propose values, no two decide differently, and correct processes eventually decide.Source: §2.1 · p. 2

2.2 Fast paths and adopt-commit

• An adopt-commit fast path either commits a value immediately or adopts it for fallback consensus, which preserves any decision that may already have occurred.KCensus synthesizes optimized adopt-commit protocols with per-proposer strategies.Source: §2.2 · p. 2

2.3 System model

• The system has n ≥ 2f + 1 processes, tolerates up to f crashes, and uses FIFO, lossless links between correct processes; adopt-commit and SMR protocols are safe under full asynchrony.Adopt-commit termination requires eventual crash suspicion, while deterministic SMR termination relies on partial synchrony; good performance requires no false suspicions during stable periods.Source: §2.3 · p. 2
• Optimization assumes stable periods long enough to estimate inter-process latencies and proposal rates and install new strategies; this assumption is not needed for safety.Source: §2.3 · p. 2

3.1 Recoverability

• Recoverability requires any two reachable states with different committed values to differ in the local states of at least f + 1 processes.Otherwise, after those processes fail, survivors may not be able to distinguish the commits.Source: §3.1 · pp. 2–3
• A knowledge requirement R_p records which processes must witness acceptances and which acceptors each witness must have recorded.In the normal form, the required witnesses are exactly the quorum whose acceptances must be recorded.Source: §3.1 · p. 3
• Validity requires every quorum to contain more than f processes; compatibility requires each pair of proposer requirements to ensure at least f + 1 witnesses of an acceptance in their quorum intersection.The requirements may contribute asymmetrically to the witnesses, and together validity and compatibility characterize correct fast paths under the model.Source: §3.1 · p. 3
• An intersection alone may not preserve evidence: after the intersection process and both proposers fail, survivors can have identical states despite conflicting commits.The Figure 2 example uses n = 7 and f = 3 with a single-process quorum intersection.Source: §3.1 · p. 3, Figure 2 · p. 3

3.2 Prior protocols and recoverable evidence

• Paxos, Pando, and Multi-Paxos induce valid, compatible requirements, so KCensus’s optimal fast path is no slower than their common-case paths.These familiar protocols achieve recoverability through different evidence patterns, which KCensus represents as per-proposer knowledge requirements.Source: §3.2 · p. 4
• Fast Paxos requires quorums larger than (n + f)/2 so their intersections directly provide enough recovery witnesses; SwiftPaxos also offers a shared quorum of size f + 1.With n = 7 and f = 3, Fast Paxos requires six acceptors; SwiftPaxos’s quorum intersections themselves suffice for recovery.Source: §3.2 · p. 4
• EPaxos can use smaller quorum intersections because proposers’ acceptances and replies provide witnesses outside the intersection within the same round trip.For n = 7 and f = 3, its five-process fast quorums may intersect in only three processes, with additional witnesses supplying recovery evidence.Source: §3.2 · p. 4

4.1 Overview

• A proposer spreads evidence and commits once it knows enough to meet its requirement; a conflict or fault suspicion instead triggers recovery.The template checks requirements for validity and pairwise compatibility before use.Source: §4 · p. 4, §4.1 · p. 5

4.2 Disseminating evidence

• Processes accept the first value they receive, record witnessed acceptances, and broadcast updates as their evidence grows; evidence propagates from acceptances to witnesses’ knowledge and then to the proposer.A process that later sees evidence for a different value detects conflict and asks proposers to abandon the fast path.Source: §4.2 · p. 5

4.3 Committing a value

• A proposer meets its requirement when its view covers the required evidence for every witness; if a required witness is suspected, it abandons the fast path.A false suspicion is safe because it triggers recovery earlier.Source: §4.3 · pp. 5–6

4.4 Adopting a value

• Recovery freezes n−f processes and uses their replies to identify any value that could already have committed, adopting that value or otherwise its own proposal.A reply rules a candidate out if a required acceptor chose another value or a required witness lacks evidence demanded by that value’s requirement.Source: §4.1 · p. 5, §4.4 · p. 6
• If a value committed, every set of n−f Frozen replies preserves it and rules out every conflicting value.Validity and compatibility ensure each census contains the evidence needed to preserve the committed value and expose conflicting candidates.Source: §4.4 · p. 6

4.5 Non-voting processes

• Non-voting clients can propose and disseminate evidence without serving as required witnesses or acceptors, so their failures do not count toward the failure budget.This lets clients propose directly without adding them as regular voting processes.Source: §4.5 · p. 7

5 Synthesizing Optimal Fast Paths

• The synthesis process turns topology measurements into candidate requirements, selects a compatible combination for the target metric, and then reduces traffic without affecting latency.The optimizer can also exclude candidate requirements that depend on suspected processes.Source: §5 · p. 7, §5.2 · p. 8

5.1 From topology to requirements

• KCensus derives candidate requirements at evidence-arrival budgets by simulating evidence spread with measured latencies, replacing a search over arbitrary requirements with budgets where new evidence arrives.Extra evidence in a candidate requirement can later be trimmed without increasing its latency.Source: §5.1 · p. 7

5.2 Choosing optimal requirement combinations

• The optimizer selects one budget per proposer whose induced requirements are compatible, and changing only the objective lets it target mean, median, or tail latency.Different objectives can select different Pareto-optimal solutions; feasible solutions instantiate the same correct template.Source: §5.2 · p. 7
• Under fixed and known network latencies, permanent crashes with perfect failure detection, contention-free executions, and a fixed latency metric, KCensus yields latency-optimal fast paths.No deterministic fast path can achieve lower latency according to the target metric under these assumptions.Source: §5.2 · p. 8

5.3 Robustness with multiple requirements

• The presented template uses one requirement per proposer and abandons the fast path when a required witness is suspected; optimizing sets of requirements for robustness is left to future work.Adding a Paxos-like requirement for every n−f quorum bounds conflict-free latency by Paxos’s, at the cost of extra messages.Source: §5.3 · p. 8

5.4 Reducing network traffic

• After choosing requirements, KCensus builds a dissemination graph that uses latency shortcuts and removes redundant messages while preserving commit latency and safety.The graph changes evidence delivery, not the requirements, when they can be met, or the commit checks.Source: §5.4 · p. 8

6 Implementation: KCensus-Based SMR

• KSMR runs one consensus instance per log slot, using KCensus requirements for fast commits and safe adoption before fallback consensus when a conflict or fault occurs.A process that fails to commit in one slot re-proposes its command in the next.Source: §6 · pp. 8–9
• On conflicts, KSMR overlaps Paxos leader election with KCensus adoption, so the leader can complete adoption by the time a fast commit would complete.In practice, fast commits take one roundtrip in most deployments and only slightly more otherwise; conflicts are about as slow as Paxos.Source: §6 · p. 9
• KSMR shards non-interfering commands into independent logs and uses different requirements to account for proposer distributions in each shard.Updates to different keys in a key-value store do not conflict.Source: §6 · p. 9
• KSMR shares measured inter-process latencies and, after a crash, broken link, or proposal-rate shift, installs an updated table and derives new requirements.Processes run the same deterministic solver locally after consensus installs the table.Source: §6 · p. 9
• A non-voting client can delegate commitment to a nearby replica, which checks the requirement, commits and executes the command, then replies to the client.The client remains the logical proposer, and KSMR uses requirements synthesized for proposer–delegate pairs.Source: §6 · p. 9
• KSMR serves reads at one replica after a quorum check and waits for the highest relevant slot to execute; reads conflict with writes but never delay them.The quorum intersects every write quorum to discover any write that may have committed.Source: §6 · p. 9

7.1 End-to-end latency

• KCensus lowers average latency versus the fastest baseline by 15% in NH, 15% in EA, 12% in EU, and 9% in NA.It also has the best 99th percentile in every deployment, and reduces latency by up to 37% across client locations.Source: Figure 7 · p. 10, §7.1 · p. 10

7.2 Impact of failures on latency

• With zero, one, and two failures, KCensus lowers average latency versus the fastest baseline by 15%, 13%, and 6%; with three, SwiftPaxos leads by 3%.At three failures, surviving configurations force all proposers onto the same quorum, and SwiftPaxos’s speculative execution provides its margin.Source: Figure 8 · p. 11, §7.2 · p. 11

7.3 Scalability of latency with replicas

• In Random deployments, KCensus beats the fastest baseline by 8% at 7 replicas and 16% at 21; latency depends on placement, not replica count.Latency is not monotonic in Random deployments because added regions can introduce distant clients as well as new quorum choices.Source: Figure 9 · p. 11, §7.3 · p. 11

7.4 Resource consumption

• At 31 replicas, KCensus sends 146 B/request/replica, 4% less than EPaxos, but uses 39.2 MiB peak memory/server, the largest footprint, though under 40 MiB.Its overall resource use remains within the range of existing fast-path protocols; it is several times cheaper than SwiftPaxos on networking and CPU.Source: §7.4 · pp. 11–12, Figure 11 · p. 12

7.5 Latency under contention

• Under Zipfian access, KCensus’s write median is 123 ms, within 3% of uniform, but its 99th percentile rises to 385 ms; SwiftPaxos averages 146 ms versus KCensus’s 158 ms.For Zipfian reads, KCensus averages 127 ms with a 213 ms 99th percentile; EPaxos reaches 157 ms and 433 ms, respectively.Source: Figure 12 · p. 12, §7.5 · p. 12

7.6 Latency under load

• Under uniform access, KCensus stays near 124 ms through 44k req/s and below 137 ms up to 50k saturation; under Zipfian access it stays below 170 ms up to 40k req/s.KCensus achieves the highest throughput at comparable latency under both distributions, without a throughput collapse under conflicts.Source: Figure 13 · p. 13, §7.6 · p. 13

7.7 Time to optimize requirements

• Optimization time ranges from 0.1 ms at 3 replicas to 144 ms at 31, orders of magnitude below the interval between significant topology changes.The measured optimization cost is therefore negligible relative to those changes.Source: Figure 14 · p. 13, §7.7 · p. 13

Strongly consistent wide-area replication

• KCensus reduces consensus-layer latency rather than weakening consistency in strongly consistent wide-area replication.Many wide-area systems reduce latency by relaxing consistency, whereas strongly consistent services tend to rely on consensus to order updates across regions.Source: §8 · p. 13

Low-latency consensus

• No fixed communication pattern, quorum rule, or coordinator placement is best across topologies, workloads, and latency objectives; KCensus synthesizes a recoverable ensemble for each deployment.Earlier approaches fix one of these design choices, while KCensus characterizes recoverability and optimizes for a given deployment.Source: §8 · p. 13
• KCensus assigns a specific strategy to each proposer, so prior fast-quorum bounds do not apply to its broader design space.Prior work addresses fast paths through quorum systems, while KCensus captures more than quorum choice alone.Source: §8 · p. 13
• Conflict-reduction techniques are orthogonal to KCensus: they reduce the probability of conflicting fast paths, while KCensus optimizes fast-path latency.The cited techniques exploit commutativity or use sequencing and timing assumptions to steer concurrent commands apart.Source: §8 · p. 13
• KCensus targets crash-fault consensus over ordinary WANs, unlike low-latency systems built for Byzantine settings or datacenter hardware.The passage contrasts its model with systems using Byzantine assumptions, RDMA, or programmable switches.Source: §8 · p. 14

Topology-aware communication

• KCensus’s dissemination graphs can resemble ring or tree structures, but they are derived to deliver the knowledge required by synthesized fast paths along low-latency routes.Earlier topology-aware protocols use such structures to distribute load, improve throughput, or reduce bandwidth bottlenecks.Source: §8 · p. 14

Knowledge-based protocols

• KCensus addresses asynchronous crash-fault fast paths with non-uniform latencies, a different model from the synchronous knowledge-based protocols discussed here.The passage notes that this model changes both the problem and the solution.Source: §8 · p. 14

9 Conclusion

• KCensus characterizes the evidence needed for safe recovery and turns fast-path design into a checkable optimization problem.Its synthesized fast paths adapt to network topology, proposer distribution, and the target latency objective.Source: §9 · p. 14
• In the evaluation, KCensus achieves the lowest latency across deployments, cutting average latency by up to 16%.The conclusion reports this as the outcome of the synthesized fast paths.Source: §9 · p. 14
• Future work includes mechanically checking KCensus and extending it to dependency tracking, Byzantine faults, speculative execution, and erasure coding.Source: §9 · p. 14

A KCensus Correctness

• The adopt-commit protocol requires termination, validity, and agreement: correct proposers adopt or commit, only proposed values are used, and a committed value excludes conflicting adoption or commitment.Not all correct processes need to propose in this formulation.Source: A KCensus Correctness · p. 18
• Consensus requires correct callers to decide, restricts decisions to proposed values, and permits only a single value to be decided.Source: A KCensus Correctness · p. 18
• The construction decides immediately when adopt-commit commits; when it adopts, it sends the value to fallback consensus and decides on that protocol’s result.The appendix states that this construction satisfies the three required consensus properties.Source: A KCensus Correctness · p. 18

A.1 KCensus’s Adopt-Commit Correctness

• Accept&Spread messages carry only proposed values, and a correct process accepts at most one non-⊥ value.On first receipt, a correct process forwards the value unless it previously received Freeze; without Freeze, a proposer’s message eventually reaches every correct process.Source: §A.1 · pp. 18–19
• Knowledge in known_acceptors never decreases, and knowledge recorded at another process remains a subset of its final value at the recorded process.This containment supports the protocol’s reasoning from observed knowledge to eventual knowledge.Source: §A.1 · p. 19
• A process that commits a value has evidence that every process in its requirement keys accepted that same value.The proof connects satisfied requirements to known_acceptors, whose entries represent processes that accepted the process’s value.Source: §A.1 · pp. 19–20
• If a value is committed, an adopter cannot deem a distinct proposed value potentially committable.Requirement overlap and Frozen replies expose knowledge that makes the distinct value’s requirements fail.Source: §A.1 · p. 20
• If all correct processes first receive the same value and none receives Freeze, a proposer of that value eventually reaches a state where can_commit returns True.Dissemination grows knowledge until the proposer’s requirements are contained in known_acceptors.Source: §A.1 · pp. 21–22
• Every correct process that calls Propose eventually adopts or commits.The proof shows the relevant waits eventually end, including when a correct process receives DoAdopt.Source: §A.1 · p. 22
• The termination proof covers Freeze delivery and, without Freeze, Accept&Spread cases that lead each correct proposer to return.A received Freeze prompts DoAdopt to all; otherwise, conflicting first values trigger DoAdopt, while matching values lead either to DoAdopt for a divergent proposal or to can_commit succeeding for a matching one.Source: §A.1 · pp. 22–23
• Validity holds: every returned adoption or commitment is a value proposed by some Propose call.A committed input is proposed; an adopted value comes from either a proposed value or a Frozen reply carrying an accepted proposed value.Source: §A.1 · p. 23
• Agreement holds: if a proposer commits v, every returning Propose call adopts or commits v.For two commits, compatible requirements overlap and a process accepts at most one value; an adopter’s potential_commit returns the committed value.Source: §A.1 · p. 23

A.2 KCensus’s Correctness

• Algorithm 7 satisfies termination, validity, and agreement, deriving correctness from adopt-commit and fallback consensus.Source: §A.2 · p. 23
• Termination follows because adopt-commit either commits, allowing a decision, or adopts, invoking fallback consensus, which is guaranteed to decide.Source: §A.2 · p. 23
• Validity is preserved because adopt-commit receives only proposed values, and fallback consensus decides a value proposed to it.When adopt-commit commits, the protocol decides that value directly; when it adopts, the adopted value is passed to fallback consensus.Source: §A.2 · p. 23
• Agreement holds whether all processes fall back or some process commits: decisions through either path resolve to the same value.If no process commits, fallback consensus provides agreement; otherwise adopt-commit agreement constrains adopted or committed values, and fallback validity preserves that value.Source: §A.2 · pp. 23–24

• Weighted objective latency measures proposal-to-decision time across single-correct-proposer executions, weighted by proposer probability, under a stable network.The objective may be expected latency or a percentile such as tail or median latency; stability assumes known stable inter-process latencies and accurate suspicion of faulty processes.Source: B KCensus Optimality · p. 24
• KCensus achieves optimal weighted objective latency among deterministic consensus protocols in stable networks, assuming some proposal happens before any message is sent.The proof concludes that no deterministic protocol has better weighted objective latency than KCensus.Source: B KCensus Optimality · pp. 25–26
• For each correct proposer, the proof derives a KCensus requirement by running Alg with that sole proposer and processing the messages known at its decision.The known messages are processed in reception order using Algorithm 8 to compute the requirement.Source: B KCensus Optimality · p. 25
• The derived requirements have KCensus’s required normal form and are valid and pairwise compatible, so KCensus can use them.The proof establishes the dictionary properties, validity, and compatibility in Claims B.2–B.4.Source: B KCensus Optimality · pp. 25–27

B KCensus Optimality

• In the constructed execution f2, r decides v_r while processes outside K decide v_r′, contradicting consensus agreement.The proof uses indistinguishability between executions to establish these decisions.Source: B KCensus Optimality · p. 29
• Alg’s weighted objective latency is not smaller than KCensusAlgReqs’ weighted objective latency.The proof compares proposer-specific executions and then takes the weighted objective latency over executions for each correct process as proposer.Source: B KCensus Optimality · p. 29
• Only processes in K_r send or receive messages known by r at t_r, and Algorithm 8’s propagated acceptor records are bounded by AlgReqs[r].For each such message, the recorded keys belong to K_r and the recorded acceptors are subsets of the corresponding AlgReqs[r] entries.Source: B KCensus Optimality · pp. 29–30
• Every process in K_r receives a message known by r at t_r, and r belongs to AlgReqs[r][p] for each p in K_r.The proof derives the request-set inclusion from the received-message property and the acceptor-knowledge lemmas.Source: B KCensus Optimality · p. 32
• For the processes r and r′ chosen in Claim B.4’s proof, neither belongs to the other’s K-set, and both belong to K.These membership properties are used to establish the contradiction in that claim’s proof.Source: B KCensus Optimality · pp. 28, 32, 33

• Processes outside K cannot distinguish f1 from f2 through t_d, because they remain up and message transmission follows L* in both executions.The proof says these executions remain indistinguishable to such processes at all times.Source: B KCensus Optimality · p. 34
• In e*_r, no DoAdopt or Freeze message is sent: each sending path requires a prior DoAdopt or Freeze message, preventing the first such send.The proof rules out DoAdopt sends on lines 26 and 50, then rules out the first DoAdopt or Freeze send on the remaining paths.Source: B KCensus Optimality · p. 34
• Each correct process p receives its first Accept&Spread message in e*_r by its shortest weighted distance from r, no later than its first message in e_r, if any.The proof uses induction along a shortest path in L from r to p.Source: B KCensus Optimality · p. 35
• The proof compares KCensus and Algorithm 8 known_acceptors states by induction on receipt times of messages known by r at t_r.It focuses on the receipt times of those messages because they are the times relevant to the sets being compared.Source: B KCensus Optimality · p. 35
• At r, accepted is set to v_r, and Algorithm 8's requirements for r are contained in KCensus's corresponding known_acceptors state at t_r.The proof applies the state-containment result to r and each process in Algorithm 8's requirements for r.Source: B KCensus Optimality · p. 36

• Validity and compatibility are necessary and sufficient for a fast path to admit a recovery rule that preserves fast decisions.Source: C Fast-Path Correctness · p. 36
• KCensus derives per-process requirements from messages known at decision time, then uses Alg’s single-proposer communication pattern to preserve fast decisions.The construction processes each correct process’s single-proposer execution to derive requirements; KCensus uses those requirements and communication patterns to obtain an adoption rule.Source: C Fast-Path Correctness · p. 36
• For sufficiency, the derived requirements have the required normal form, and validity and compatibility follow from the corresponding fast-path conditions.Source: C Fast-Path Correctness · p. 36
• For necessity, each valid derived requirement corresponds to a fast-path quorum larger than f, while compatibility requires at least f + 1 processes to receive qualifying message chains for each proposer pair.Source: C Fast-Path Correctness · pp. 36–37