Technical Reports
 

Document Type

Article

Publication Date

8-2008

Comments

TR08-007

Abstract

A k-local distributed algorithm (k is a natural number) is a distributed algorithm in which the computation at every point/device in the distributed system modeled as a graph depends solely on the initial states of the points that are at most k hops away from the point. A distributed algorithm is local if it is k-local for some fixed natural number k. Local distributed algorithms are very important, especially for applications in ad-hoc sensor and wireless networks, since such algorithms are naturally scalable, robust, and fault tolerant. Clearly, an essential component of any k-local distributed algorithm is computing the k-hop neighborhoods of the points in the graph.

In this paper we show that, given a wireless network modeled as a unit ball graph or as a quasi unit ball graph U on n points in the 3-dimensional (3-D) Euclidean space, and a natural number k, there exists a local distributed algorithm that computes the k-hop neighborhoods of the points in U such that the total number of messages sent by all the points in U at the end of the algorithm is O(n), and where each message has length O(lgn) bits. Clearly, this algorithm is optimal.

We note that the same results can be projected to unit disk graphs and quasi unit disk graphs in the Euclidean plane. Moreover, our techniques, and hence our results, can be generalized in a straightforward manner to unit ball graphs in l-dimensional spaces, where l > 3 is an integer.

Download

Share

COinS