EUVIMEDEUVIMED entdecken
Crossref

Expected Constant Round Byzantine Broadcast under Dishonest Majority

Jun Wan, Hanshen Xiao, Elaine Shi, Srinivas Devadas

Journal of the ACM · 31.08.2025 · 72 (4) · 1-39

DOI: 10.1145/3748254 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 08.08.2025. Verfasst von Jun Wan und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 36 Literaturangaben. Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Byzantine Broadcast (BB) is a central question in distributed systems, and an important challenge is to understand its round complexity. Under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant rounds, regardless of the number of nodes n . However, whether we can match the expected constant round complexity in the corrupt majority setting —or more precisely, when \(f \ge n/2 + \omega (1)\) —remains unknown, where f denotes the number of corrupt nodes. In this article, we are the first to resolve this long-standing question. We show how to achieve BB in expected \(O((n/(n-f))^2)\) rounds. Our results hold under a weakly adaptive adversary who cannot perform “after-the-fact removal” of messages already sent by a node before it becomes corrupt. We also assume trusted setup and the Decision Linear (DLIN) assumption in bilinear groups.

Förderung

  • NSF

Zitieren

APA

Wan, J., Xiao, H., Shi, E., & Devadas, S. (2025). Expected Constant Round Byzantine Broadcast under Dishonest Majority. Journal of the ACM, 72(4), 1-39. https://doi.org/10.1145/3748254

Vancouver

Wan J, Xiao H, Shi E, Devadas S. Expected Constant Round Byzantine Broadcast under Dishonest Majority. Journal of the ACM. 2025;72(4):1-39. doi:10.1145/3748254

BibTeX
@article{Wan2025,
  author = {Wan, Jun and Xiao, Hanshen and Shi, Elaine and Devadas, Srinivas},
  title = {Expected Constant Round Byzantine Broadcast under Dishonest Majority},
  journal = {Journal of the ACM},
  year = {2025},
  volume = {72},
  number = {4},
  pages = {1--39},
  doi = {10.1145/3748254}
}
Kostenlos starten →