License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.57
URN: urn:nbn:de:0030-drops-148596
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14859/
Goren, Guy ;
Moses, Yoram ;
Spiegelman, Alexander
Brief Announcement: Probabilistic Indistinguishability and The Quality of Validity in Byzantine Agreement
Abstract
Lower bounds and impossibility results in distributed computing are both intellectually challenging and practically important. Hundreds if not thousands of proofs appear in the literature, but surprisingly, the vast majority of them apply to deterministic algorithms only. Probabilistic protocols have been around for at least four decades and are receiving a lot of attention with the emergence of blockchain systems. Nonetheless, we are aware of only a handful of randomized lower bounds.
In this work we provide a formal framework for reasoning about randomized distributed algorithms. We generalize the notion of indistinguishability, the most useful tool in deterministic lower bounds, to apply to a probabilistic setting. We apply this framework to prove a result of independent interest. Namely, we completely characterize the quality of decisions that protocols for a randomized multi-valued Consensus problem can guarantee in an asynchronous environment with Byzantine faults. We use the new notion to prove a lower bound on the guaranteed probability that honest parties will not decide on a possibly bogus value proposed by a malicious party. Finally, we show that the bound is tight by providing a protocol that matches it.
This brief announcement consists of an introduction to the full paper [Guy Goren et al., 2020] by the same title. The interested reader is advised to consult the full paper for a detailed exposition.
BibTeX - Entry
@InProceedings{goren_et_al:LIPIcs.DISC.2021.57,
author = {Goren, Guy and Moses, Yoram and Spiegelman, Alexander},
title = {{Brief Announcement: Probabilistic Indistinguishability and The Quality of Validity in Byzantine Agreement}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {57:1--57:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-210-5},
ISSN = {1868-8969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14859},
URN = {urn:nbn:de:0030-drops-148596},
doi = {10.4230/LIPIcs.DISC.2021.57},
annote = {Keywords: Indistinguishability, probabilistic lower bounds, Byzantine agreement}
}
|
Keywords: |
|
Indistinguishability, probabilistic lower bounds, Byzantine agreement |
|
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.10.2021 |
