The Complexity Of Early Deciding Set Agreement

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.


Publié dans:
Siam Journal On Computing, 40, 63-78
Année
2011
Publisher:
Society for Industrial and Applied Mathematics
ISSN:
0097-5397
Mots-clefs:
Laboratoires:




 Notice créée le 2011-12-16, modifiée le 2019-03-16

Publisher's version:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)