Radio Network Distributed Algorithms in the Unknown Neighborhood Model
Résumé
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.