Talks and Poster Presentations (without Proceedings-Entry):
U. Schmid:
"Easy Impossibility Proofs for k-Set Agreement";
Talk: Dagstuhl Seminar #16282 Topological Methods in Distributed Computing,
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik (invited);
2016-07-10
- 2016-07-15.
English 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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/DagRep.6.7.31