Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement
verfasst von : Matthias Fitzi, Jesper Buus Nielsen
Erschienen in: Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Byzantine agreement is typically considered with respect to either a fully synchronous network or a fully asynchronous one. In the synchronous case,
t
+ 1 communication rounds are necessary for deterministic protocols whereas all known probabilistic protocols require an
expected
large number of rounds. In this paper we examine the question of how many initial synchronous rounds are required for Byzantine agreement in the
worst case
if we allow to switch to asynchronous operation afterward. 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 (aka authenticated Byzantine agreement),
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.