Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Oracular Byzantine Reliable Broadcast
 
conference paper

Oracular Byzantine Reliable Broadcast

Camaioni, Martina  
•
Guerraoui, Rachid  
•
Monti, Matteo  
Show more
2022
LIPIcs–Leibniz International Proceedings in Informatic
36th International Symposium on Distributed Computing (DISC 2022)

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. LIPIcs, Vol. 246, 36th International Symposium on Distributed Computing (DISC 2022), pages 13:1-13:19

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.4230/lipics.disc.2022.13
Author(s)
Camaioni, Martina  
Guerraoui, Rachid  
Monti, Matteo  
Vidigueira, Manuel  
Date Issued

2022

Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Publisher place

Hannover

Published in
LIPIcs–Leibniz International Proceedings in Informatic
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent placeEvent date
36th International Symposium on Distributed Computing (DISC 2022)

Augusta, Georgia, USA

October 25-27, 2022

Available on Infoscience
January 23, 2023
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/194203
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés