Beyond Optimal Fault-Tolerance
Andrew Lewis-Pye, Tim Roughgarden · 2025
Read Beyond Optimal Fault-Tolerance by Andrew Lewis-Pye, Tim Roughgarden (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-06044.txt.
Introduction
Andrew Lewis-Pye and Tim Roughgarden ask how much fault tolerance a replicated system can buy by occasionally breaking its own rules, in a paper published in two thousand twenty-five. For state machine replication, the optimal trade-off between consistency and liveness against adversaries is a classic, settled formula.
They relax consistency: allow a bounded number of violations, called rollbacks, and see what becomes possible. Without extra timing assumptions, they prove bounded rollback is impossible to guarantee. With a bound on message delays around the time of an attack, even a generous one, protocols can tolerate attacks and recover from the violations. The analysis separates what timing buys from what it cannot. Distributed systems from databases to blockchains live on this trade-off curve. The paper maps the region just beyond the classical optimum and shows it is real but conditional.
Catalog record
| CREATOR | Andrew Lewis-Pye, Tim Roughgarden |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 102 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-06044
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Optimal Fault-Tolerance Andrew Lewis-Pye, Tim Roughgarden Abstract . One of the most basic properties of a consensus protocol is its fault-tolerance—the maximum fraction of faulty participants that the protocol can tolerate without losing fundamental guarantees such as safety and liveness. Because of its importance, the optimal fault-tolerance achievable by any protocol has been characterized in a wide range of settings. For example, for state machine replication (SMR) protocols operating in the partially synchronous setting, it is possible to simultaneously guarantee consistency against α \alpha -bounded adversaries (i.e., adversaries that control less than an α \alpha fraction of the participants) and liveness against β \beta -bounded adversaries if and only if α + 2 β ≤ 1 \alpha+2\beta\leq 1 . This paper characterizes to what extent “better-than-optimal” fault-tolerance guarantees are possible for SMR protocols when the standard consistency requirement is relaxed to allow a bounded number r r of consistency violations, each potentially leading to the rollback of recently finalized transactions. We prove that bounding rollback is impossible without additional timing assumptions and investigate protocols that tolerate and recover from consistency violations whenever message delays around the time of an attack are bounded by a parameter Δ ∗ \Delta^{*} (which may be arbitrarily larger than the parameter Δ \Delta that bounds post-GST message delays in the partially synchronous model). Here, a protocol’s fault-tolerance can be a non-constant function of r r , and we prove, for each r r , matching upper and lower bounds on the optimal “recoverable fault-tolerance” achievable by any SMR protocol. For example, for protocols that guarantee liveness against 1/3-bounded adversaries in the partially synchronous setting, a 5/9-bounded adversary can always cause one consistency violation but not two, and a 2/3-bounded adversary can always cause two consistency violations but not three. Our positive results are achieved through a generic “recovery procedure” that can be grafted on to any accountable SMR protocol and restores consistency following a violation while rolling back only transactions that were finalized in the previous 2 Δ ∗ 2\Delta^{*} timesteps. 1. Introduction We consider protocols for the state machine replication (SMR) problem, in which processes receive transactions from an environment and are responsible for finalizing a common sequence of transactions. We focus on the partially synchronous setting ( Dwork et al., 1988 ) , in which message delays are bounded by a known parameter \Delta following an unknown “global stabilization time” GST (and unbounded until that point). The two most basic requirements of an SMR protocol are consistency, meaning that no two processes should finalize incompatible sequences of transactions (one should be a prefix of the other), and liveness, which stipulates that valid transactions should eventually be finalized (ideally, following GST, within an amount of time proportional to \Delta ). Guaranteeing consistency and liveness becomes impossible if too many of the processes are faulty (i.e., deviate from the intended behavior of a protocol). For the SMR problem in partial synchrony, it is possible to simultaneously guarantee consistency against \alpha -bounded adversaries (i.e., adversaries that control less than an \alpha fraction of the participants) and liveness against \beta -bounded adversaries if and only if \alpha+2\beta\leq 1 ( Momose and Ren, 2021 ; Dwork et al., 1988 ) . The focus of this paper is consistency violations—the type of violation that enables, for example, double-spending a cryptocurrency native to a blockchain protocol. What can be said about a protocol when the adversary is large enough to cause a consistency violation? For example, is it already in a position to cause an unbounded number of consistency violations (as opposed to just one), or could the protocol “fight back” in some way? To make sense of this question and the idea of multiple consistency violations, we must formalize a sense in which a protocol might restore consistency following a violation, necessarily by rolling back transactions that had been viewed as finalized by some non-faulty processes. One key parameter is then the recovery time d , meaning the number of timesteps after a violation before a protocol returns to healthy operation. A second is the rollback h , meaning that the recovery process “unfinalizes” only transactions that have been finalized within the previous h time steps. The natural wishlist for an SMR protocol in partial synchrony would then be: (1) All of the “usual” guarantees, such as optimal fault-tolerance (i.e., consistency with respect to \alpha -bounded adversaries and liveness with respect to \beta -bounded adversaries for some \alpha,\beta>0 with \alpha+2\beta=1 ). (2) Automatic recovery from a consistency violation with the worst-case recovery time d and worst-case rollback h as small as possible (if nothing else, independent of the specific execution). (3) Never suffers more than r consistency violations overall, where r is as small as possible. To what extent are these properties simultaneously achievable? This paper provides a thorough investigation of this question. To expose the richness of the answer, we work with a timing model that can be viewed as an interpolation between the synchronous and partially synchronous settings. In addition to the usual parameters \Delta and GST (known and unknown, respectively) of the partially synchronous model, we allow for a known parameter \Delta^{*}\geq\Delta which may or may not bound message delays prior to GST. Canonically, \Delta^{*} should be thought of as orders of magnitude larger than \Delta , with \Delta indicating the speed of communication between processes when all is well (no network issues, no attacks) and \Delta^{*} a safe (and possibly large) upper-bound on the speed of (possibly out-of-band) communication around the time of an attack. 1 1 1 Indeed, for our positive results, message delays must be bounded by \Delta^{*} for the duration of our recovery procedure, but not otherwise. We will be interested in protocols that always satisfy all the “usual” guarantees (1) and that finalize transactions in time O(\Delta) (rather than O(\Delta^{*}) ) after GST, whether or not pre-GST message delays are bounded by \Delta^{*} , and also satisfy the additional recovery guarantees (2) and (3) in the event that pre-GST message delays are in fact bounded by \Delta^{*} . 2 2 2 In particular, a synchronous protocol with respect to the parameter \Delta^{*} will not generally satisfy consistency and liveness if message delays do not happen to bounded above by \Delta^{*} . Our main positive result, stated formally in Theorem 6.1 and proved in Section 7 , shows that such protocols do indeed exist. For example, we show that there is a protocol that satisfies: • \tfrac{1}{3} -resilience in partial synchrony (independent of whether \Delta^{*} bounds pre-GST message delays), with expected latency O(\Delta) after GST; • should pre-GST message delays be bounded by \Delta^{*} , recovers from consistency violations in expected time O(\Delta^{*}) and with rollback 2\Delta^{*} ; and • should pre-GST message delays be bounded by \Delta^{*} , never suffers from more than one consistency violation with a \tfrac{5}{9} -bounded attacker, and never suffers from more than two consistency violations with a \tfrac{2}{3} -bounded attacker. We achieve this result by designing a generic “recovery procedure” that can be grafted on to any accountable SMR protocol, including protocols with asymmetric fault-tolerance with respect to consistency and liveness attacks. Sections 4 and 5 give informal and formal, respectively, descriptions of