Paper 2008/414

On the Number of Synchronous Rounds Required for Byzantine Agreement

Matthias Fitzi and Jesper Buus Nielsen

Abstract

Byzantine agreement is typically considered with respect to either a fully synchronous network or a fully asynchronous one. In the synchronous case, either $t+1$ deterministic rounds are necessary in order to achieve Byzantine agreement or at least some expected large constant number of rounds. In this paper we examine the question of how many initial synchronous rounds are required for Byzantine agreement if we allow to switch to asynchronous operation afterwards. Let $n=h+t$ be the number of parties where $h$ are honest and $t$ are corrupted. As the main result we show that, in the model with a public-key infrastructure and signatures, $d+O(1)$ deterministic synchronous rounds are sufficient where $d$ is the minimal integer such that $n-d>3(t-d)$. This improves over the $t+1$ necessary deterministic rounds for almost all cases, and over the exact expected number of rounds in the non-deterministic case for many cases.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Byzantine agreement
Contact author(s)
buus @ daimi au dk
History
2008-10-02: received
Short URL
https://ia.cr/2008/414
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/414,
      author = {Matthias Fitzi and Jesper Buus Nielsen},
      title = {On the Number of Synchronous Rounds Required for Byzantine Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2008/414},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/414}},
      url = {https://eprint.iacr.org/2008/414}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.