Radio Network Distributed Algorithms in the Unknown Neighborhood Model

Bilel Derbel 1, 2 El-Ghazali Talbi 1, 2
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : The paper deals with radio network distributed algorithms where initially no information about node degrees is available. We show that the lack of such an information affects the time complexity of existing fundamental algorithms by only a polylogarithmic factor. More precisely, given an n-node graph modeling a multi-hop radio network, we provide a O(log2 n) time distributed algorithm that computes w.h.p., a constant approximation value of the degree of each node. We also provide a O(Δlogn + log2 n) time distributed algorithm that computes w.h.p., a constant approximation value of the local maximum degree of each node, where the global maximum degree Δ of the graph is not known. Using our algorithm as a plug-and-play procedure, we show that the local maximum degree can be used instead of Δ to break the symmetry efficiently. We illustrate this claim by revisiting some fundamental algorithms that use Δ as a key parameter. First, we investigate the generic problem of simulating any point-to-point interference-free message passing algorithm in the radio network model. Then, we study the fundamental coloring problem in unit disk graphs. The obtained results show that the local maximum degree allows nodes to self-organize in a local manner and to avoid the radio interferences from being a communication bottleneck.
Type de document :
Communication dans un congrès
ICDN 2010 - 11th International Conference on Distributed Computing and Networking, Jan 2010, Calcutta, India. Springer, LNCS, 5935, pp.155-166, 2010, ICDCN 2010: Distributed Computing and Networking. 〈10.1007/978-3-642-11322-2_18〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00524143
Contributeur : Bilel Derbel <>
Soumis le : jeudi 7 octobre 2010 - 09:46:42
Dernière modification le : lundi 23 avril 2018 - 14:10:46

Lien texte intégral

Identifiants

Citation

Bilel Derbel, El-Ghazali Talbi. Radio Network Distributed Algorithms in the Unknown Neighborhood Model. ICDN 2010 - 11th International Conference on Distributed Computing and Networking, Jan 2010, Calcutta, India. Springer, LNCS, 5935, pp.155-166, 2010, ICDCN 2010: Distributed Computing and Networking. 〈10.1007/978-3-642-11322-2_18〉. 〈inria-00524143〉

Partager

Métriques

Consultations de la notice

238