2012/07/03 by Tomasz Jurdziński, Jurdzinski, Tomasz, Dariusz R. Kowalski +1
Computer Science · #Cooperative Communication and Network Coding #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1207.0602
openalex publication_date 2012/07/03 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
The Signal-to-Interference-and-Noise-Ratio (SINR) physical model is one of\nthe legitimate models of wireless networks. Despite of the vast amount of study\ndone in design and analysis of centralized algorithms supporting wireless\ncommunication under the SINR physical model, little is known about distributed\nalgorithms in this model, especially deterministic ones. In this work we\nconstruct, in a deterministic distributed way, a backbone structure on the top\nof a given wireless network, which can be used for transforming many algorithms\ndesigned in a simpler model of ad hoc broadcast networks without interference\ninto the SINR physical model with uniform power of stations, without increasing\ntheir asymptotic time complexity. The time cost of the backbone data structure\nconstruction is only O(Delta polylog n) rounds, where Delta is roughly the\ninverse of network density and n is the number of nodes in the whole network.\nThe core of the construction is a novel combinatorial structure called\nSINR-selector, which is introduced and constructed in this paper. We\ndemonstrate the power of the backbone data structure by using it for obtaining\nefficient O(D+Delta polylog n)-round and O(D+k+Delta polylog n)-round\ndeterministic distributed solutions for leader election and multi-broadcast,\nrespectively, where D is the network diameter and k is the number of messages\nto be disseminated.\n