1 Search Results for "Camaioni, Martina"

Document
DOI: 10.4230/LIPIcs.DISC.2022.13
Oracular Byzantine Reliable Broadcast

Authors: Martina Camaioni, Rachid Guerraoui, Matteo Monti, and Manuel Vidigueira

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Byzantine Reliable Broadcast (BRB) is a fundamental distributed computing primitive, with applications ranging from notifications to asynchronous payment systems. Motivated by practical consideration, we study Client-Server Byzantine Reliable Broadcast (CSB), a multi-shot variant of BRB whose interface is split between broadcasting clients and delivering servers. We present Draft, an optimally resilient implementation of CSB. Like most implementations of BRB, Draft guarantees both liveness and safety in an asynchronous environment. Under good conditions, however, Draft achieves unparalleled efficiency. In a moment of synchrony, free from Byzantine misbehaviour, and at the limit of infinitely many broadcasting clients, a Draft server delivers a b-bits payload at an asymptotic amortized cost of 0 signature verifications, and (log₂(c) + b) bits exchanged, where c is the number of clients in the system. This is the information-theoretical minimum number of bits required to convey the payload (b bits, assuming it is compressed), along with an identifier for its sender (log₂(c) bits, necessary to enumerate any set of c elements, and optimal if broadcasting frequencies are uniform or unknown). These two achievements have profound practical implications. Real-world BRB implementations are often bottlenecked either by expensive signature verifications, or by communication overhead. For Draft, instead, the network is the limit: a server can deliver payloads as quickly as it would receive them from an infallible oracle.
Cite as

Martina Camaioni, Rachid Guerraoui, Matteo Monti, and Manuel Vidigueira. Oracular Byzantine Reliable Broadcast. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{camaioni_et_al:LIPIcs.DISC.2022.13,
  author =	{Camaioni, Martina and Guerraoui, Rachid and Monti, Matteo and Vidigueira, Manuel},
  title =	{{Oracular Byzantine Reliable Broadcast}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.13},
  URN =		{urn:nbn:de:0030-drops-172048},
  doi =		{10.4230/LIPIcs.DISC.2022.13},
  annote =	{Keywords: Byzantine reliable broadcast, Good-case complexity, Amortized complexity, Batching}
}
  • Refine by Author
  • 1 Camaioni, Martina
  • 1 Guerraoui, Rachid
  • 1 Monti, Matteo
  • 1 Vidigueira, Manuel

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 Amortized complexity
  • 1 Batching
  • 1 Byzantine reliable broadcast
  • 1 Good-case complexity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact