KIT | KIT-Bibliothek | Impressum | Datenschutz

On the number of authenticated rounds in Byzantine agreement

Borcherding, Malte


Byzantine Agreement requires a set of nodes in a distributed
system to agree on the message of a sender despite the presence
of arbitrarily faulty nodes. Solutions for this problem are
generally divided into two classes: authenticated protocols and
non-authenticated protocols. In the former class, all messages
are (digitally) signed and can be assigned to their respective
signers, while in the latter no messages are signed.
Authenticated protocols can tolerate an arbitrary number of
faults, while non-authenticated protocols require more than two
thirds of the nodes to be correct.

In this paper, we investigate the fault tolerance of protocols
that require signatures in a certain number of communication
rounds only. We show that a protocol that is to tolerate one
half of the nodes as faulty needs only few authenticated rounds
(logarithmic in the number of nodes), while tolerating more
faults requires about two authenticated rounds per additional
faulty node.

Volltext §
DOI: 10.5445/IR/325895
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Informatik – Institut für Rechnerentwurf und Fehlertoleranz (IRF)
Publikationstyp Buchaufsatz
Publikationsjahr 1995
Sprache Englisch
Identifikator urn:nbn:de:swb:90-AAA3258953
KITopen-ID: 325895
Erscheinungsvermerk In: Distributed algorithms. WDAG '95. Ed.: J.-M. Helary. Berlin 1995. S. 230-241. (Lecture notes in computer science. 972.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page