Radio Network Distributed Algorithms in ...
Type de document :
Rapport de recherche
Titre :
Radio Network Distributed Algorithms in the Unknown Neighborhood Model
Auteur(s) :
Derbel, Bilel [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Institution :
INRIA
Date de publication :
2008
Mot(s)-clé(s) en anglais :
Distributed algorithms
time complexity
Radio networks.
Radio networks
time complexity
Radio networks.
Radio networks
Discipline(s) HAL :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]/Réseaux et télécommunications [cs.NI]
Informatique [cs]/Informatique ubiquitaire
Informatique [cs]/Réseaux et télécommunications [cs.NI]
Informatique [cs]/Informatique ubiquitaire
Résumé en anglais : [en]
The paper deals with radio network distributed algorithms where nodes are not aware of their one hop neighborhood. Given an n-node graph modeling a multihop network of radio devices, we give a O(log^2 n) time distributed ...
Lire la suite >The paper deals with radio network distributed algorithms where nodes are not aware of their one hop neighborhood. Given an n-node graph modeling a multihop network of radio devices, we give a O(log^2 n) time distributed algorithm that computes w.h.p., a constant approximation value of the degree of each node. We also provide a O( \Delta log n + log^2 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 \Delta of the graph is not known. Using our algorithms as a plug-and-play procedure, we show that many existing distributed algorithms requiring the knowledge of to execute efficiently can be run with essentially the same time complexity by using the local maximum degree instead of . In other words, using the local maximum degree is sufficient to break the symmetry in a local and efficient manner. We illustrate this claim by investigating the complexity of some basic problems. First, we investigate the generic problem of simulating any classical message passing algorithm in the radio network model. Then, we study the fundamental edge/node coloring problem in the special case of unit disk graphs. The obtained results show that knowing the local maximum degree allows to coordinate the nodes locally and avoid interferences in radio networks.Lire moins >
Lire la suite >The paper deals with radio network distributed algorithms where nodes are not aware of their one hop neighborhood. Given an n-node graph modeling a multihop network of radio devices, we give a O(log^2 n) time distributed algorithm that computes w.h.p., a constant approximation value of the degree of each node. We also provide a O( \Delta log n + log^2 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 \Delta of the graph is not known. Using our algorithms as a plug-and-play procedure, we show that many existing distributed algorithms requiring the knowledge of to execute efficiently can be run with essentially the same time complexity by using the local maximum degree instead of . In other words, using the local maximum degree is sufficient to break the symmetry in a local and efficient manner. We illustrate this claim by investigating the complexity of some basic problems. First, we investigate the generic problem of simulating any classical message passing algorithm in the radio network model. Then, we study the fundamental edge/node coloring problem in the special case of unit disk graphs. The obtained results show that knowing the local maximum degree allows to coordinate the nodes locally and avoid interferences in radio networks.Lire moins >
Langue :
Anglais
Collections :
Source :
Fichiers
- https://hal.inria.fr/inria-00292155v3/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/inria-00292155v3/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/inria-00292155v3/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- RR-6581.pdf
- Accès libre
- Accéder au document