Security

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

Date Added: Mar 2011
Format: PDF

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