1 Search Results for "Pavlovic, Matej"


Document
Scalable Byzantine Reliable Broadcast

Authors: Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


Abstract
Byzantine reliable broadcast is a powerful primitive that allows a set of processes to agree on a message from a designated sender, even if some processes (including the sender) are Byzantine. Existing broadcast protocols for this setting scale poorly, as they typically build on quorum systems with strong intersection guarantees, which results in linear per-process communication and computation complexity. We generalize the Byzantine reliable broadcast abstraction to the probabilistic setting, allowing each of its properties to be violated with a fixed, arbitrarily small probability. We leverage these relaxed guarantees in a protocol where we replace quorums with stochastic samples. Compared to quorums, samples are significantly smaller in size, leading to a more scalable design. We obtain the first Byzantine reliable broadcast protocol with logarithmic per-process communication and computation complexity. We conduct a complete and thorough analysis of our protocol, deriving bounds on the probability of each of its properties being compromised. During our analysis, we introduce a novel general technique that we call adversary decorators. Adversary decorators allow us to make claims about the optimal strategy of the Byzantine adversary without imposing any additional assumptions. We also introduce Threshold Contagion, a model of message propagation through a system with Byzantine processes. To the best of our knowledge, this is the first formal analysis of a probabilistic broadcast protocol in the Byzantine fault model. We show numerically that practically negligible failure probabilities can be achieved with realistic security parameters.

Cite as

Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. Scalable Byzantine Reliable Broadcast. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{guerraoui_et_al:LIPIcs.DISC.2019.22,
  author =	{Guerraoui, Rachid and Kuznetsov, Petr and Monti, Matteo and Pavlovic, Matej and Seredinschi, Dragos-Adrian},
  title =	{{Scalable Byzantine Reliable Broadcast}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.22},
  URN =		{urn:nbn:de:0030-drops-113293},
  doi =		{10.4230/LIPIcs.DISC.2019.22},
  annote =	{Keywords: Byzantine reliable broadcast, probabilistic distributed algorithms, scalable distributed systems, stochastic processes}
}
  • Refine by Author
  • 1 Guerraoui, Rachid
  • 1 Kuznetsov, Petr
  • 1 Monti, Matteo
  • 1 Pavlovic, Matej
  • 1 Seredinschi, Dragos-Adrian

  • Refine by Classification
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Stochastic processes
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Distributed computing models

  • Refine by Keyword
  • 1 Byzantine reliable broadcast
  • 1 probabilistic distributed algorithms
  • 1 scalable distributed systems
  • 1 stochastic processes

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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