Gafni, Eli
Guerraoui, Rachid
Pochon, Bastian
The Complexity Of Early Deciding Set Agreement
Siam Journal On Computing
Siam Journal On Computing
Siam Journal On Computing
Siam Journal On Computing
40
distributed algorithm
set agreement
lower bound
message passing system
shared memory system
simulation
Consensus
2011
2011
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.
Society for Industrial and Applied Mathematics
0097-5397
Siam Journal On Computing
Journal Articles
10.1137/050640746