Parallel Exhaustive Search without Coordination

Abstract : We analyze parallel algorithms in the context of exhaustive search over totally ordered sets. Imagine an infinite list of " boxes " , with a " treasure " hidden in one of them, where the boxes' order reflects the importance of finding the treasure in a given box. At each time step, a search protocol executed by a searcher has the ability to peek into one box, and see whether the treasure is present or not. Clearly, the best strategy of a single searcher would be to open the boxes one by one, in increasing order. Moreover, by equally dividing the workload between them, k searchers can trivially find the treasure k times faster than one searcher. However, this straightforward strategy is very sensitive to failures (e.g., crashes of processors), and overcoming this issue seems to require a large amount of communication. We therefore address the question of designing parallel search algorithms maximizing their speed-up and maintaining high levels of robustness, while minimizing the amount of resources for coordination. Based on the observation that algorithms that avoid communication are inherently robust, we focus our attention on identifying the best running time performance of non-coordinating algorithms. Specifically, we devise non-coordinating algorithms that achieve a speed-up of 9/8 for two searchers, a speed-up of 4/3 for three searchers, and in general, a speed-up of k 4 (1 + 1/k) 2 for any k ≥ 1 searchers. Thus, asymptotically, the speed-up is only four times worse compared to the case of full-coordination. Moreover, these bounds are tight in a strong sense as no non-coordinating search algorithm can achieve better speed-ups. Furthermore , our algorithms are surprisingly simple and hence applicable. Overall, we highlight that, in faulty contexts in which coordination between the searchers is technically difficult to implement, intrusive with respect to privacy, and/or costly in term of resources, it might well be worth giving up on coordination, and simply run our non-coordinating exhaustive search algorithms.
Type de document :
Communication dans un congrès
STOC 2016: 48th Annual Symposium on the Theory of Computing, Jun 2016, Cambridge, MA, United States. 〈10.1145/2897518.2897541〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01393646
Contributeur : Amos Korman <>
Soumis le : lundi 7 novembre 2016 - 18:54:05
Dernière modification le : jeudi 15 novembre 2018 - 20:27:45
Document(s) archivé(s) le : mardi 14 mars 2017 - 23:25:08

Fichiers

Treasure-submitted-STOC.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Fraigniaud, Amos Korman, Yoav Rodeh. Parallel Exhaustive Search without Coordination. STOC 2016: 48th Annual Symposium on the Theory of Computing, Jun 2016, Cambridge, MA, United States. 〈10.1145/2897518.2897541〉. 〈hal-01393646〉

Partager

Métriques

Consultations de la notice

478

Téléchargements de fichiers

36