Toward more localized local algorithms: removing assumptions concerning global knowledge

Amos Korman 1, 2 Jean-Sébastien Sereni 3 Laurent Viennot 1, 2, 4
1 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and (∆+1)-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [34], as well as the O(∆ 2)-coloring algorithm by Linial [28]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, local algorithms generally use good estimations of one or more global parameters of the network, e.g., the maximum degree ∆ or the number of nodes n. This paper provides a method for transforming a non-uniform local algorithm into a uniform one. Furthermore , the resulting algorithm enjoys the same asymp-totic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all state of the art non-uniform algorithms for MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called pruning algorithms, which we believe may be of independent interest.
Type de document :
Article dans une revue
Distributed Computing, Springer Verlag, 2013, 26 (5-6), <10.1007/s00446-012-0174-8>
Contributeur : Amos Korman <>
Soumis le : mercredi 9 décembre 2015 - 21:43:41
Dernière modification le : mardi 11 octobre 2016 - 14:02:52
Document(s) archivé(s) le : jeudi 10 mars 2016 - 16:29:52


Fichiers produits par l'(les) auteur(s)





Amos Korman, Jean-Sébastien Sereni, Laurent Viennot. Toward more localized local algorithms: removing assumptions concerning global knowledge. Distributed Computing, Springer Verlag, 2013, 26 (5-6), <10.1007/s00446-012-0174-8>. <hal-01241086>



Consultations de
la notice


Téléchargements du document