<div class="csl-bib-body">
<div class="csl-entry">Schmid, U. (2016). <i>Easy Impossibility Proofs for k-Set Agreement</i>. Dagstuhl Seminar #16282 Topological Methods in Distributed Computing, Wadern, Germany. https://doi.org/10.4230/DagRep.6.7.31</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/86398
-
dc.description.abstract
Despite of being quite similar agreement problems, distributed consensus (1-set agreement) and general k-set agreement require surprisingly different techniques for proving impossibilities. In particular, the relatively simple bivalence arguments used in the impossibility proof for consensus in the presence of a single crash failure are superseded by a reasoning based on algebraic topology resp. variants of Sperner's Lemma in the case of k-set agreement for f≥k>1 crash failures. In this talk, we provide an overview of a generic theorem for proving the impossibility of k-set agreement in various message passing settings, which has been published at OPODIS'11. Our BRS Theorem is based on a reduction to the consensus impossibility in a certain subsystem resulting from a partitioning argument, which facilitates easy impossibility proofs for k-set agreement. Its broad applicability is demonstrated in several message passing models.
en
dc.title
Easy Impossibility Proofs for k-Set Agreement
-
dc.type
Präsentation
de
dc.type
Presentation
en
dc.type.category
Conference Presentation
-
tuw.peerreviewed
false
-
tuw.publication.invited
invited
-
tuw.publication.orgunit
E191-02 - Forschungsbereich Embedded Computing Systems
-
tuw.publisher.doi
10.4230/DagRep.6.7.31
-
tuw.event.name
Dagstuhl Seminar #16282 Topological Methods in Distributed Computing
-
tuw.event.startdate
10-07-2016
-
tuw.event.enddate
15-07-2016
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Wadern
-
tuw.event.country
DE
-
tuw.event.presenter
Schmid, Ulrich
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.facultyfocus
Computer Engineering (CE)
de
wb.facultyfocus
Computer Engineering (CE)
en
wb.facultyfocus.faculty
E180
-
item.openairetype
conference paper not in proceedings
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cp
-
crisitem.author.dept
E191-02 - Forschungsbereich Embedded Computing Systems
