E191-02 - Forschungsbereich Embedded Computing Systems
-
Date (published):
2016
-
Event name:
Dagstuhl Seminar #16282 Topological Methods in Distributed Computing
-
Event date:
10-Jul-2016 - 15-Jul-2016
-
Event place:
Wadern, Germany
-
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.
