Please use this identifier to cite or link to this item: https://doi.org/10.1145/1993806.1993818
Title: Structuring unreliable radio networks
Authors: Censor-Hillel, K.
Gilbert, S. 
Kuhn, F.
Lynch, N.
Newport, C.
Keywords: connected dominating set
dual graphs
maximal independent set
unreliable networks
Issue Date: 2011
Source: Censor-Hillel, K.,Gilbert, S.,Kuhn, F.,Lynch, N.,Newport, C. (2011). Structuring unreliable radio networks. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing : 79-88. ScholarBank@NUS Repository. https://doi.org/10.1145/1993806.1993818
Abstract: In this paper we study the problem of building a connected dominating set with constant degree (CCDS) in the dual graph radio network model [4,9,10]. This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. Real networks compensate for this differing quality by deploying low-layer detection protocols to filter unreliable from reliable links. With this in mind, we begin by presenting an algorithm that solves the CCDS problem in the dual graph model under the assumption that every process u is provided a local link detector set consisting of every neighbor connected to u by a reliable link. The algorithm solves the CCDS problem in O(Δ\log 2 n/b + log 3 n) rounds, with high probability, where Δ is the maximum degree in the reliable link graph, n is the network size, and b is an upper bound in bits on the message size. The algorithm works by first building a Maximal Independent Set (MIS) in log 3 n time, and then leveraging the local topology knowledge to efficiently connect nearby MIS processes. A natural follow up question is whether the link detector must be perfectly reliable to solve the CCDS problem. With this in mind, we first describe an algorithm that builds a CCDS in O(Δpolylog(n)) time under the assumption of O(1) unreliable links included in each link detector set. We then prove this algorithm to be (almost) tight by showing that the possible inclusion of only a single unreliable link in each process's local link detector set is sufficient to require Ω(Δ) rounds to solve the CCDS problem, regardless of message size. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time. © 2011 ACM.
Source Title: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/40519
ISBN: 9781450307192
DOI: 10.1145/1993806.1993818
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

12
checked on Dec 13, 2017

Page view(s)

46
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.