2/2011 : Easy Impossibility Proofs for k-Set Agreement in Message Passing Systems

RR Number

2/2011

Conference

Proceedings 15th International Conference on Principles of Distributed Systems (OPODIS'11); Springer LNCS 7109

Author(s)

Martin Biely, Peter Robinson, Ulrich Schmid

Abstract

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, we show that there is no need for such involved techniques in case of message-passing systems: We present a simple 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. We demonstrate the broad applicability of our result by exploring the possibility/impossibility border of k-set agreement in several message-passing system models: (i) asynchronous systems with crash failures, (ii) partially synchronous processes with (initial) crash failures, and (iii) asynchronous systems augmented with failure detectors. In (i) and (ii), the impossibility part is just an instantiation of our main theorem, whereas the possibility of achieving k-set agreement in (ii) follows by generalizing the consensus algorithm for initial crashes by Fisher, Lynch and Patterson. In (iii), applying our technique yields the exact border for the parameter k where k-set agreement is solvable with the failure detector class (Sigma_k,Omega_k) of Bonnet and Raynal.

Bibtex

@techreport{BRS11:easy
  author =       "Martin Biely and Peter Robinson and Ulrich Schmid",
  title =        "Easy Impossibility Proofs for k-Set Agreement in Message Passing Systems",
  institution =  "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  address =      "Treitlstr. 1-3/182-1, 1040 Vienna, Austria",
  type =         "Research Report",
  year =         "2011",
  number =       "2/2011"
}

Download

Get paper.pdf - Adobe PDF-format, (220.86 KB; posted at March 10 2011)