On the Locality of Bounded Growth
Fabian Kuhn Computer Engineering and Networks Laboratory ETH Zurich 8092 Zurich, Switzerland
Thomas Moscibroda Computer Engineering and Networks Laboratory ETH Zurich 8092 Zurich, Switzerland
Roger Wattenhofer Computer Engineering and Networks Laboratory ETH Zurich 8092 Zurich, Switzerland
Many large-scale networks such as ad hoc and sensor net- works, peer-to-peer networks, or the Internet have the prop- erty that the number of independent nodes does not grow arbitrarily when looking at neighborhoods of increasing size. Due to this bounded “volume growth,” one could expect that distributed algorithms are able to solve many problems more efficiently than on general graphs. The goal of this paper is to help understanding the distributed complexity of problems on “bounded growth” graphs. We show that on the widely used unit disk graph, covering and packing linear programs can be approximated by constant factors in con- stant time. For a more general network model which is based on the assumption that nodes are in a metric space of con- stant doubling dimension, we show that in O(log∗n) rounds it is possible to construct a (O(1), O(1))-network decompo- sition. This results in asymptotically optimal O(log∗n) time algorithms for many important problems.
Categories and Subject Descriptors
F.2.2 [Analysis of Algorithms and Problem Complex-
ity]: Nonnumerical Algorithms and Problems tions on discrete structures;
G.2.2 [Discrete Mathematics]: Graph Theory—graph al- gorithms; G.2.2 [Discrete Mathematics]: Graph Theory—network problems
bounded growth, covering, distributed algorithms, dominat- ing sets, doubling dimension, locality, maximal independent set, network decomposition, packing, unit disk graphs
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. PODC’05, July 17–20, 2005, Las Vegas, Nevada, USA. Copyright 2005 ACM 1-59593-994-2/05/0007 ...$5.00.
The advent of wireless multi-hop networks such as mo- bile ad hoc and sensor networks has brought about many new algorithmic challenges and paradigms, and it has cre- ated a flurry of research activity in this new field. Some of the specific challenges stemming from these network types are mobility and energy constraints. Yet, in spite of these new aspects, most of the algorithmic design principles have remained the same as in classical distributed systems. One important difference between wireless and classical networks is that wireless networks look different. While in classical systems, there often is no restriction on the network topol- ogy, in wireless networks, it is usually assumed that the network structure is defined by some geometric graph.
In the ad hoc and sensor networks community, the most important and most widely used graph model is the unit disk graph (UDG). It is assumed that all nodes are in the Euclidean plane. There is an edge between two nodes if and only if their distance is at most 1. The UDG model idealizes a real scenario where the radios of all wireless nodes have equal transmission ranges (normalized to 1) such that two nodes can communicate whenever they are within each others transmission range.
While on the one hand, issues such as mobility or en- ergy make ad hoc networks a theoretically interesting and tremendously challenging subject to study, the fact that UDGs are a lot simpler than general graphs should on the other hand make many problems easier than in the general case. In a non-distributed setting, it is indeed true that for many problems UDGs often allow constant approximations or even polynomial time approximation schemes (PTAS) whereas the same problems cannot be approximated well for general graphs. In a distributed scenario, often, the best known algorithms for UDGs are not faster than the best al- gorithms for general graphs. On general graphs, for many network coordination tasks such as the construction of small dominating sets, maximal independent sets, or graph color- ings, strong upper and lower bounds are known (e.g. [16, 17, 20, 22]). A lot less is known about the distributed complex- ity of the same problems on UDGs. In fact, to the best of our knowledge, the only non-trivial lower bound that applies to UDGs is Linial’s Ω(log∗n) for coloring the ring . With the exception of  (expected O(1) approximation for dom- inating set in O(log log n) rounds), time upper bounds are usually polylogarithmic. However, as the example of the minimum vertex cover problem shows, there are problems