License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.25
URN: urn:nbn:de:0030-drops-135108
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13510/
Liu-Zhang, Chen-Da ;
Maram, Varun ;
Maurer, Ueli
On Broadcast in Generalized Network and Adversarial Models
Abstract
Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [Pease et al., 1980] shows that broadcast is achievable if and only if t < n/3. There are two generalizations suggested for the broadcast problem - with respect to the adversarial model and the communication model. Fitzi and Maurer [Fitzi and Maurer, 1998] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties. On the other hand, Considine et al. [Considine et al., 2005] extend the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < (b-1)/(b+1)n. These generalizations are unified in the work by Raykov [Raykov P., 2015], where a tight condition on the possible corrupted sets is presented such that broadcast is achievable from a complete set of b-minicasts.
This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [Jaffe et al., 2012; Raykov P., 2015]. To that end, we propose a hierarchy over all possible general adversaries, and identify for each class of general adversaries 1) a set of minicast channels that are necessary to achieve broadcast and 2) a set of minicast channels that are sufficient to achieve broadcast. In particular, this allows us to derive bounds on the amount of b-minicasts that are necessary and that suffice towards constructing broadcast in general b-minicast networks.
BibTeX - Entry
@InProceedings{liuzhang_et_al:LIPIcs:2021:13510,
author = {Chen-Da Liu-Zhang and Varun Maram and Ueli Maurer},
title = {{On Broadcast in Generalized Network and Adversarial Models}},
booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
pages = {25:1--25:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-176-4},
ISSN = {1868-8969},
year = {2021},
volume = {184},
editor = {Quentin Bramas and Rotem Oshman and Paolo Romano},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13510},
URN = {urn:nbn:de:0030-drops-135108},
doi = {10.4230/LIPIcs.OPODIS.2020.25},
annote = {Keywords: broadcast, partial broadcast, minicast, general adversary, general network}
}
|
Keywords: |
|
broadcast, partial broadcast, minicast, general adversary, general network |
|
Collection: |
|
24th International Conference on Principles of Distributed Systems (OPODIS 2020) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
25.01.2021 |
