171702
20190316235241.0
doi
10.1137/050640746
0097-5397
ISI
000287697400003
ARTICLE
The Complexity Of Early Deciding Set Agreement
2011
Society for Industrial and Applied Mathematics
2011
Journal Articles
In the k-set agreement problem, each processor starts with a private input value and eventually decides on an output value. At most k distinct output values may be chosen, and every processor's output value must be one of the proposed values. We consider a synchronous message passing system, and we prove a tight bound of [f/k] + 2 rounds of communication for all processors to decide in every run in which at most f processors fail. The lower bound proof proceeds through a simulation of a synchronous solution to k-set agreement in message passing, in an asynchronous shared memory system in which k - 1 processors may fail, and which was proven to be impossible using topological approaches. In contrast to past complexity results on set agreement, our lower bound proof is purely algorithmic. It does not use any direct topological argument but uses instead the impossibility of asynchronous set agreement to encapsulate the needed topology. We thus derive an adaptive complexity lower bound for a message passing system from a static impossibility in a shared memory system.
distributed algorithm
set agreement
lower bound
message passing system
shared memory system
simulation
Consensus
Gafni, Eli
240335
Guerraoui, Rachid
105326
Pochon, Bastian
40
63-78
Siam Journal On Computing
199988
http://infoscience.epfl.ch/record/171702/files/the_compl_of_ear_decid_set_ag_50640746.pdf
Publisher's version
Publisher's version
252114
DCL
U10407
oai:infoscience.tind.io:171702
IC
article
GLOBAL_SET
166927
166927
EPFL-ARTICLE-171702
EPFL
REVIEWED
PUBLISHED
ARTICLE