TY - GEN
T1 - Easy impossibility proofs for k-set agreement in message passing systems
AU - Biely, Martin
AU - Robinson, Peter
AU - Schmid, Ulrich
N1 - Funding Information:
This work has been supported by the Austrian Science Foundation (FWF) project P20529. Peter Robinson has also been supported by the Nanyang Technological University grant M58110000.
PY - 2011
Y1 - 2011
N2 - 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. 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, most importantly, (iii) asynchronous systems augmented with failure detectors. In (i), (ii), and (iii), the impossibility part is 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 reveals the exact border for the parameter k where k-set agreement is solvable with the failure detector class (∑k, Ωk) 1≤k≤n-1 of Bonnet and Raynal. As ∑k was shown to be necessary for solving k-set agreement, this result yields new insights on the quest for the weakest failure detector.
AB - 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. 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, most importantly, (iii) asynchronous systems augmented with failure detectors. In (i), (ii), and (iii), the impossibility part is 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 reveals the exact border for the parameter k where k-set agreement is solvable with the failure detector class (∑k, Ωk) 1≤k≤n-1 of Bonnet and Raynal. As ∑k was shown to be necessary for solving k-set agreement, this result yields new insights on the quest for the weakest failure detector.
KW - consensus
KW - failure detectors
KW - impossibility proofs
KW - k-set agreement
UR - http://www.scopus.com/inward/record.url?scp=84055218412&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84055218412&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-25873-2_21
DO - 10.1007/978-3-642-25873-2_21
M3 - Conference contribution
AN - SCOPUS:84055218412
SN - 9783642258725
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 299
EP - 312
BT - Principles of Distributed Systems - 15th International Conference, OPODIS 2011, Proceedings
T2 - 15th International Conference on Principles of Distributed Systems, OPODIS 2011
Y2 - 13 December 2011 through 16 December 2011
ER -