<div class="csl-bib-body">
<div class="csl-entry">Winkler, K. (2013). <i>Easy impossibility proofs for k-set agreement</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2013.22720</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2013.22720
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/4225
-
dc.description
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
-
dc.description
Zsfassung in dt. Sprache
-
dc.description.abstract
This thesis is concerned with impossibility results, i.e., proofs of the fact that certain classes of algorithms cannot exist. The algorithms investigated are from the field of fault-tolerant distributed computing, which is devoted to the formal study of processing entities, modeled as communicating state machines, that may possibly fail and communicate with each other by either exchanging messages or via access to a shared memory. We investigate the problem of k-set agreement, a natural generalization of consensus. While consensus concerns itself with the task in which all processes eventually have to decide on a common value that was originally some process- input value, k-set agreement allows up to k different decision values. Hence, for k = 1, k-set agreement is equivalent to consensus. Although there exist impossibility results for deterministic consensus in systems prone to failures, relying solely on combinatoric arguments that might be considered classical today, the corresponding impossibility results for k-set agreement require complex arguments from algebraic topology. Nevertheless, there has been recent research on finding "easy" or non-topological impossibility proofs for k-set agreement, which may also provide a new handle on solving some long-standing open problems like the weakest failure detector for k-set agreement in message-passing systems. The focus of this thesis lies on such non-topological impossibilities for k-set agreement. We present and discuss existing approaches and results and provide rigorous proofs for new results regarding various models and scenarios, including the important class of dynamic systems that may evolve over time.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.title
Easy impossibility proofs for k-set agreement
en
dc.title.alternative
Easy Impossibility Proofs for k-Set Agreement
de
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.2013.22720
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Kyrill Winkler
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E182 - Institut für Technische Informatik
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC11180929
-
dc.description.numberOfPages
64
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-74024
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
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.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.languageiso639-1
en
-
item.openaccessfulltext
Open Access
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
crisitem.author.dept
E191-02 - Forschungsbereich Embedded Computing Systems