2011 | OriginalPaper | Buchkapitel
Communication Optimal Multi-valued Asynchronous Byzantine Agreement with Optimal Resilience
verfasst von : Arpita Patra, C. Pandu Rangan
Erschienen in: Information Theoretic Security
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 (BA) and Broadcast (BC) are considered to be the most fundamental primitives for fault-tolerant distributed computing and cryptographic protocols. An important variant of BA and BC is Asynchronous Byzantine Agreement (ABA) and Asynchronous Broadcast (called as
A-cast
) respectively. Most often in the literature, protocols for ABA and
A-cast
were designed for a single bit message. But in many applications, these protocols may be invoked on
long message
rather than on single bit. Therefore, it is important to design efficient
multi-valued
protocols (i.e. protocols with
long message
) which extract advantage of directly dealing with long messages and are far better than multiple invocations to existing protocols for single bit. In synchronous network settings, this line of research was initiated by Turpin and Coan [27] and later it is culminated in the result of Fitzi et al. [15] who presented the first ever
communication optimal
(
i.e. the communication complexity is minimal in asymptotic sense
) multi-valued BA and BC protocols with the help of BA and BC protocols for short message. It was left open in [15] to achieve the same in asynchronous settings.
In [21], the authors presented a communication optimal multi-valued
A-cast
using existing
A-cast
[6] for small message. Here we achieve the same for ABA which is known to be harder problem than
A-cast
. Specifically, we design a
communication optimal
, optimally resilient (
allows maximum fault tolerance
) multi-valued ABA protocol, based on the existing ABA protocol for short message.