---
title: "Consensus Without Clocks"
subtitle: "Reframing partial synchrony as a resource-allocation problem in modern distributed systems."
discipline: "Computer Science"
articleType: "Commentary"
authors: ["Lena Ostrowski", "Tomas Reidl", "Aiko Tanaka"]
affiliations: ["Institute for Distributed Systems, ETH Zürich", "Graduate School of Information Science, University of Tokyo"]
correspondence: "l.ostrowski@ethz.ch"
keywords: ["Distributed Systems"]
date: "2026-07-17T02:24:03.923Z"
---

# Consensus Without Clocks

*Reframing partial synchrony as a resource-allocation problem in modern distributed systems.*

## Abstract

Deterministic consensus is impossible in a fully asynchronous system with even one faulty process, yet practical systems routinely achieve agreement by relying on eventual timing assumptions. This commentary argues that partial synchrony is often easier to reason about operationally when timeout selection is treated as a budgeted trade between responsiveness and false suspicion rather than as a hidden constant. The goal is not to propose a new impossibility or liveness result, but to restate established theory in terms that connect more directly to implementation choices in modern distributed systems.

The Fischer-Lynch-Paterson impossibility result shows that no deterministic protocol can guarantee consensus in a fully asynchronous system if even a single process may fail [1]. Practical consensus systems nevertheless make progress because they do not operate under pure asynchrony forever. Instead, they rely on the eventual timing assumptions formalised by Dwork, Lynch, and Stockmeyer in the partial-synchrony model [2].

This commentary offers a narrow interpretive claim: in operational settings, partial synchrony is often easier to reason about when timeout choice is treated as a budgeted trade between responsiveness and false suspicion rather than as a fixed engineering constant. This does not replace the temporal definitions in the literature [2]. It is a way of explaining why implementation decisions around failure detection and leader replacement matter so much in deployed systems.

## Partial synchrony in practice

The classical partial-synchrony model still turns on time. Messages are not assumed to arrive within a known bound at all times, but after some unknown stabilization point the system behaves as though a finite delay bound exists [2]. Consensus protocols exploit that eventual regularity. Before the system stabilises, replicas may suspect a correct leader too early or wait too long to replace a failed one. After it stabilises, the same timeout logic can support liveness.

That distinction helps reconcile theory with practice. The impossibility result of Fischer, Lynch, and Paterson remains intact [1]. Systems do not evade it by discovering a magical timeout. They make progress because protocol designers are willing to assume a regime in which delays eventually become well behaved enough for retransmission, view change, or leader election rules to succeed [2].

## Timeout choice as an operational budget

From an implementation perspective, a timeout is not just a number in a configuration file. It expresses how much unnecessary coordination work a system is willing to pay in order to detect failure quickly. Aggressive timeout settings can shorten recovery after an actual failure, but they also raise the chance of false suspicion during transient delay spikes. Conservative settings reduce spurious churn but can lengthen failover.

Describing that choice as a budget is useful because it makes the trade legible. The budget is spent when replicas trigger view changes, restart leader election, or retransmit work that would have completed under a slightly more patient policy. In protocols such as PBFT, that cost appears in additional view-change activity [3]. In leader-based protocols such as Raft, it appears in avoidable elections and temporary loss of throughput while leadership is re-established [4].

This framing is explanatory rather than formal. It does not supersede the proofs in the underlying literature, and it should not be mistaken for a new theorem. Its value is that it connects the abstract eventual-bound assumption to concrete engineering choices that operators and implementers can observe directly.

## An illustrative heuristic

One way to reflect the budgeting intuition in code is to back off timeouts after repeated failed views. The following sketch is illustrative rather than normative:

```rust
fn next_timeout(base: Duration, view: u64, jitter: Duration) -> Duration {
    let exp = base.saturating_mul(1 << view.min(6));
    exp.saturating_add(jitter)
}
```

A heuristic like this does not prove liveness by itself, and it does not guarantee that a system will choose the right timeout under all workloads. What it does show is how implementations often translate eventual-synchrony assumptions into concrete retry policy. As views fail, the protocol becomes more patient. If the environment later behaves within a stable delay envelope, the larger timeout may allow progress where a more aggressive policy would keep thrashing.

## Why the framing matters

The main value of the budget interpretation is conceptual clarity. It discourages the common mistake of treating timeout tuning as an afterthought when it is actually entangled with liveness, failover behaviour, and coordination overhead. It also helps explain why two systems built on similar theoretical assumptions can behave very differently in production: they may be spending the timeout budget in different ways.

This is especially relevant when practitioners compare consensus families. PBFT-style protocols and Raft-style protocols differ in fault model and communication structure [3, 4], but both are sensitive to how suspicion and retry logic are calibrated relative to the network conditions they encounter. The eventual-bound model explains why progress is possible; the budget framing helps explain why progress can still be operationally expensive.

## Conclusion

Partial synchrony remains a temporal model in the formal sense given by Dwork, Lynch, and Stockmeyer [2]. The claim advanced here is narrower: when moving from proof obligations to deployed systems, timeout selection is often best understood as a budgeted trade between responsiveness and avoidable coordination work. That interpretive lens preserves the core theory while giving engineers a more practical language for reasoning about false suspicion, leader turnover, and the real cost of making consensus live under imperfect network conditions.

## References

[1] Fischer, M. J., Lynch, N. A. & Paterson, M. S. Impossibility of distributed consensus with one faulty process. *J. ACM* **32**, 374-382 (1985).
[2] Dwork, C., Lynch, N. & Stockmeyer, L. Consensus in the presence of partial synchrony. *J. ACM* **35**, 288-323 (1988).
[3] Castro, M. & Liskov, B. Practical Byzantine fault tolerance. *Proc. OSDI* 173-186 (1999).
[4] Ongaro, D. & Ousterhout, J. In search of an understandable consensus algorithm. *Proc. USENIX ATC* 305-319 (2014).