<div class="csl-bib-body">
<div class="csl-entry">Winkler, K. (2019). <i>Characterization of consensus solvability under message adversaries</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2019.72069</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2019.72069
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/4462
-
dc.description.abstract
We study characterizations of consensus solvability in dynamic networks controlled by an omniscient message adversary. This model assumes a system of n distributed agents, called processes, that execute a distributed algorithm and communicate by message passing in lockstep synchronous rounds. Communication in each round is subject to a message adversary, which determines which messages are successfully delivered and which are lost, encoded via a directed communication graph. In its most general form, the message adversary can be represented by the set of infinite sequences of communication graphs, one for each round, that it may generate. Perhaps our most important theoretical result are a precise topological characterization of consensus solvability for general message adversaries and a considerably less abstract combinatorial characterization for the important class of closed message adversaries, which encompasses most of the message adversary classes for which consensus solvability characterizations existed so far. Thanks to this, we are able to state for the first time in a precise and rigorous way exactly what is the crucial property of an arbitrary message adversary that permits a consensus solution algorithm. Our arguably most important practical result is an optimal algorithm for dynamic networks that guarantee only brief stability phases along with its correctness and optimality proof. This algorithm is relatively simple and might be used as a template for solving consensus in real systems that exhibit massive transient message loss.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
distributed computing
en
dc.subject
distributed algorithms
en
dc.subject
dynamic networks
en
dc.subject
message adversary
en
dc.subject
agreement problems
en
dc.subject
consensus
en
dc.subject
impossibility results
en
dc.subject
solvability characterization
en
dc.title
Characterization of consensus solvability under message adversaries
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2019.72069
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Kyrill Winkler
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E191 - Institut für Computer Engineering
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC15506161
-
dc.description.numberOfPages
175
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-130832
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
tuw.author.orcid
0000-0002-7310-1748
-
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.advisor.orcid
0000-0001-9831-8583
-
item.openaccessfulltext
Open Access
-
item.grantfulltext
open
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.languageiso639-1
en
-
item.openairetype
doctoral thesis
-
item.fulltext
with Fulltext
-
crisitem.author.dept
E191-02 - Forschungsbereich Embedded Computing Systems