**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.

**Category / Keywords: **cryptographic protocols / Byzantine agreement

**Date: **received 29 Sep 2008

**Contact author: **buus at daimi au dk

**Available format(s): **PDF | BibTeX Citation

**Version: **20081002:013815 (All versions of this report)

**Short URL: **ia.cr/2008/414

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]