Randomized Local Network Computing

Abstract : In this paper, we carry on investigating the line of research questioning the power of randomization for the design of distributed algorithms. In their seminal paper, Naor and Stockmeyer [STOC 1993] established that, in the context of network computing, in which all nodes execute the same algorithm in parallel, any construction task that can be solved locally by a randomized Monte-Carlo algorithm can also be solved locally by a deterministic algorithm. This result however holds in a specific context. In particular, it holds only for distributed tasks whose solutions that can be locally checked by a deterministic algorithm. In this paper, we extend the result of Naor and Stockmeyer to a wider class of tasks. Specifically, we prove that the same derandomization result holds for every task whose solutions can be locally checked using a 2-sided error randomized Monte-Carlo algorithm. This extension finds applications to, e.g., the design of lower bounds for construction tasks which tolerate that some nodes compute incorrect values. In a nutshell, we show that randomization does not help for solving such resilient tasks.
Type de document :
Communication dans un congrès
27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Jun 2015, Portland, United States. ACM, pp.340-349, 2015, 〈10.1145/2755573.2755596〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01247357
Contributeur : Pierre Fraigniaud <>
Soumis le : lundi 21 décembre 2015 - 17:47:56
Dernière modification le : jeudi 11 janvier 2018 - 06:21:34
Document(s) archivé(s) le : samedi 29 avril 2017 - 23:27:37

Fichier

de-rand-BPLD.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Laurent Feuilloley, Pierre Fraigniaud. Randomized Local Network Computing. 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Jun 2015, Portland, United States. ACM, pp.340-349, 2015, 〈10.1145/2755573.2755596〉. 〈hal-01247357〉

Partager

Métriques

Consultations de la notice

262

Téléchargements de fichiers

77