Easy Impossibility Proofs for k-Set Agreement in Message Passing Systems

Despite of being quite similar (agreement) problems, 1-set agreement (consensus) and general k-set agreement require surprisingly different techniques for proving the impossibility in asynchronous systems with crash failures: Rather than the relatively simple bivalence arguments as in the impossibility proof for consensus in the presence of a single crash failure, known proofs for the impossibility of k-set agreement in shared memory systems with f >= k > 1 crash failures use algebraic topology or a variant of Sperner's Lemma. In this paper, we present a generic theorem for proving the impossibility of k-set agreement in various message passing settings, which is based on a reduction to the consensus impossibility in a certain subsystem resulting from a partitioning argument.


Editor(s):
Fernandez Anta, Antonio
Lipari, Guiseppe
Roy, Mathieu
Published in:
Principles Of Distributed Systems, 7109, 299-312
Presented at:
15th International Conference on Principles of Distributed Systems (OPODIS 2011), Toulouse, FRANCE, Dec 13-16, 2011
Year:
2011
Publisher:
Berlin / Heidelberg, Springer
ISBN:
978-3-642-25872-5
Keywords:
Laboratories:




 Record created 2012-06-25, last modified 2018-10-01

Postprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)