[Zurück]

U. Schmid:
"Easy Impossibility Proofs for k-Set Agreement";
Vortrag: Dagstuhl Seminar #16282 Topological Methods in Distributed Computing, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik (eingeladen); 10.07.2016 - 15.07.2016.

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.

http://dx.doi.org/10.4230/DagRep.6.7.31