Round complexity in Byzantine Agreement is bounded from below. The new result clarifies the behavior of protocols under an adaptive adversary and full-information model.
In distributed systems, Byzantine Agreement (BA) is constrained not only by correctness but also by latency (round complexity). This is particularly evident in the full-information model and with an adaptive adversary, which can change strategies on the fly. It is here that the system begins to degrade: protocols that appear efficient against a static adversary lose predictability in convergence time. The problem is that the adversary observes the state of the system and randomness in each round and can selectively disrupt progress. Until now, the lower bound for randomized BA in such a model was significantly weaker than known upper bounds, leaving an architectural gap.
The solution presented in this work is formulated as a strict lower bound: any randomized Byzantine Agreement scheme in this model requires at least Ω(t² / n · log(n)) rounds in expectation. This closes the gap with upper bounds of the order O(min(t² log n / n, t / log n)) up to a logarithmic factor. From an engineering perspective, this is an important signal: accelerating BA in the presence of a strong adversary cannot be achieved merely through protocol optimization—there is a fundamental limit. This is not “bad design,” but a property of the model. The trade-off is straightforward: either limit the capabilities of the adversary or accept increased latency.
The key idea is the transition from local (round-by-round) analysis to global control of execution probabilities. Instead of analyzing each round separately, the author employs a “forcing” approach: a rare event (for example, that the protocol does not complete within R rounds) can be made practically guaranteed by controlling a sufficient number of participants. This is realized through a multi-round concentration lemma: an event with probability p can be “forced” on the system by controlling O(√(n log(1/p))) nodes. A classical crash schedule technique is then used, demonstrating that even a limited number of failures can keep the system in an incomplete state.
From the perspective of proof implementation, the transition to a “labelled transcript process” model is crucial. This is an abstraction where each step of the protocol is recorded as an observable prefix (transcript), and the adversary manages the labels of participants. Such a model allows for a formal description of how an adaptive adversary influences the system without exceeding permissible states. An attack is then constructed that sequentially “shifts” the execution of the protocol toward the desired event—a delay in completion. The limitation on the number of compromised nodes (t) is maintained through budgeted forcing: the attack is curtailed if it exceeds the limit.
An interesting engineering point is the use of a “termination synchronizer.” This is a wrapper around the protocol that aligns the completion moment among nodes. Without it, the analysis becomes complicated: different nodes may complete in different rounds, which blurs the definition of latency. The synchronizer adds a fixed delay but makes the system’s behavior more predictable and suitable for analysis. This is a typical trade-off: a small constant cost for stricter guarantees.
As a result, we obtain not just a theoretical estimate but an explanation of system behavior under adversary load. If the proportion of potentially compromised nodes (t) in the system increases, latency grows quadratically with respect to t and inversely proportional to n. This is important for high-load and blockchain-like systems, where BA underpins consensus. When scaling a cluster, one cannot expect linear improvement in convergence time—the adversarial model breaks this intuition.
Metrics are not explicitly provided, aside from asymptotic estimates. However, the boundary itself aligns with existing upper estimates, making the result practically “closing” for this model. This means that further improvements are only possible through changes in assumptions: for example, weakening the adversary or adding cryptographic primitives.
From an engineering perspective, this is an evolutionary refinement: it does not propose a new protocol but sets strict boundaries for all future architectures. If a system operates in full-information and allows for an adaptive adversary, its latency budget is already partially predetermined. This should be considered when designing SLAs and selecting failure models.
Information source
arXiv is the largest open preprint repository (since 1991, under the auspices of Cornell), where researchers quickly post working versions of papers; the materials are publicly accessible but do not undergo full peer review, so results should be considered preliminary and, where possible, checked against updated versions or peer‑reviewed journals. arxiv.org