Brief Announcement: Towards Byzantine Broadcast in Generalized Communication and Adversarial Models
dc.contributor.author
Liu Zhang, Chen-Da
dc.contributor.author
Maram, Varun
dc.contributor.author
Maurer, Ueli
dc.contributor.editor
Suomela, Jukka
dc.date.accessioned
2019-11-15T12:01:10Z
dc.date.available
2019-11-14T03:40:17Z
dc.date.available
2019-11-15T12:00:18Z
dc.date.available
2019-11-15T12:01:10Z
dc.date.issued
2019-10
dc.identifier.isbn
978-3-95977-126-9
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.DISC.2019.47
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/377527
dc.identifier.doi
10.3929/ethz-b-000377527
dc.description.abstract
Byzantine 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 - w.r.t. 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 such that broadcast is achievable from a complete set of b-minicasts is shown. 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]. Our contributions include: 1) proposing a hierarchy over all possible general adversaries for a clean analysis of the broadcast problem in general networks, 2) showing the infeasibility of a prominent technique - used to achieve broadcast in general 3-minicast networks [Ravikant et al., 2004] - with regard to higher b-minicast networks, and 3) providing some necessary conditions on general networks for broadcast to be possible while tolerating general adversaries.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Broadcast
en_US
dc.subject
Partial broadcast
en_US
dc.subject
Minicast
en_US
dc.subject
General adversary
en_US
dc.subject
General network
en_US
dc.title
Brief Announcement: Towards Byzantine Broadcast in Generalized Communication and Adversarial Models
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
33rd International Symposium on Distributed Computing (DISC 2019)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
146
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
47
en_US
ethz.size
3 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
33rd International Symposium on Distributed Computing (DISC 2019)
en_US
ethz.event.location
Budapest, Hungary
ethz.event.date
October 14-18, 2019
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03338 - Maurer, Ueli / Maurer, Ueli
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03338 - Maurer, Ueli / Maurer, Ueli
ethz.date.deposited
2019-11-14T03:40:26Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2020-02-15T22:34:59Z
ethz.rosetta.lastUpdated
2024-02-02T09:49:47Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Brief%20Announcement:%20Towards%20Byzantine%20Broadcast%20in%20Generalized%20Communication%20and%20Adversarial%20Models&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2019-10&rft.volume=146&rft.spage=47&rft.issn=1868-8969&rft.au=Liu%20Zhang,%20Chen-Da&Maram,%20Varun&Maurer,%20Ueli&rft.isbn=978-3-95977-126-9&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.DISC.2019.47&rft.btitle=33rd%20International%20Symposium%20on%20Distributed%20Computing%20(DISC%202019)
Files in this item
Publication type
-
Conference Paper [36606]