DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2026.41

Strong Efficiency Lower Bounds for Byzantine Agreement

Authors: Clément Ducros, Julian Loss, and Matthieu Rambaud

Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)

Abstract

Understanding the complexity of Byzantine agreement (BA) is a fundamental problem in distributed computing and cryptography. Existing round- or communication lower bounds either restrict the class of protocols they apply to in terms of communication, setup assumptions, or determinism. Another class of lower bounds holds only with respect to a very powerful (arguably unrealistic) adaptive adversary that can delete undelivered messages sent by a newly corrupted party while it was still honest. On the other hand, many popular BA protocols including the consensus protocol underlying the Algorand cryptocurrency assume only a standard adaptive adversary which cannot perform after-the-fact message removals. In this work, we aim to further narrow the gap between existing upper and lower bounds. We first show that unauthenticated BA has Ω(t²) messages complexity under an adaptive adversary even assuming randomization. This removes the restriction to multicast-based protocols in Abraham et al PODC'19. We then consider the restricted model of Dolev-Reischuk (J. ACM'85) where each signature counts as one and where signatures cannot be aggregated nor thresholdized. In this model, we show that partially synchronous consensus under an adaptive adversary requires that honest players send Ω(nt) signatures. We allow randomization, whereas Dolev-Reischuk proved an analogous bound under synchrony for deterministic protocols only. As a technical contribution, we present a cryptographic formalization of the restricted model of Dolev-Reischuk, which may be of independent interest. We finally turn to the round complexity of randomized BA protocols in which only a subset of parties may speak. We show that such protocols must either rely on erasures or allow a party’s decision whether to speak for the first time to depend on its input. We discuss in detail how both of these design paradigms have been used in prior work and how they lead to efficiency and design-related issues for practical BA protocols.

Cite as

Clément Ducros, Julian Loss, and Matthieu Rambaud. Strong Efficiency Lower Bounds for Byzantine Agreement. In 40th International Symposium on Distributed Computing (DISC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 397, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ducros_et_al:LIPIcs.DISC.2026.41,
  author =	{Ducros, Cl\'{e}ment and Loss, Julian and Rambaud, Matthieu},
  title =	{{Strong Efficiency Lower Bounds for Byzantine Agreement}},
  booktitle =	{40th International Symposium on Distributed Computing (DISC 2026)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-454-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{397},
  editor =	{Moses Jr., William K. and Censor-Hillel, Keren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2026.41},
  URN =		{urn:nbn:de:0030-drops-281478},
  doi =		{10.4230/LIPIcs.DISC.2026.41},
  annote =	{Keywords: Byzantine agreement, Byzantine broadcast, communication complexity}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.15

Asynchronous Latency and Fast Atomic Snapshot

Authors: João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

This paper introduces a novel, fast atomic-snapshot protocol for asynchronous message-passing systems. In the process of defining what "fast" means exactly, we spot a few interesting issues that arise when conventional time metrics are applied to long-lived asynchronous algorithms. We reveal some gaps in latency claims made in earlier work on snapshot algorithms, which hamper their comparative time-complexity analysis. We then come up with a new unifying time-complexity metric that captures the latency of an operation in an asynchronous, long-lived implementation. This allows us to formally grasp latency improvements of our atomic-snapshot algorithm with respect to the state-of-the-art protocols: optimal latency in fault-free runs without contention, short constant latency in fault-free runs with contention, the worst-case latency proportional to the number of active concurrent failures, and constant amortized latency.

Cite as

João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud. Asynchronous Latency and Fast Atomic Snapshot. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bezerra_et_al:LIPIcs.DISC.2025.15,
  author =	{Bezerra, Jo\~{a}o Paulo and Freitas, Luciano and Kuznetsov, Petr and Rambaud, Matthieu},
  title =	{{Asynchronous Latency and Fast Atomic Snapshot}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.15},
  URN =		{urn:nbn:de:0030-drops-248326},
  doi =		{10.4230/LIPIcs.DISC.2025.15},
  annote =	{Keywords: Asynchronous systems, time complexity, atomic snapshot, crash faults}
}

Search Results

Documents authored by Rambaud, Matthieu

Strong Efficiency Lower Bounds for Byzantine Agreement

Abstract

Cite as

Asynchronous Latency and Fast Atomic Snapshot

Abstract

Cite as

Thanks for your feedback!

Could not send message