X hits on this document





8 / 9

know the number of iterations. However because r grows exponentially by a factor of 2 in each iteration, we have a geometric series and can upper bound the sum by taking 2 times the maximum summand. Therefore, the whole while loop can be computed in O(logn + 24ρ) rounds. Together with Corallary 5.4, we get the required result.

Note that when collecting the whole neighborhood, it is not necessary that nodes know the minimum distance dmin between nodes. Because the radius grows exponentially, the locality of the problem is independent of the starting ra- dius. Each node can just use the smallest distance in the collected neighborhood in order to locally simulate the dis- tributed Algorithm 1. The complete algorithm to compute a (O(1), O(1))-decomposition in the given network model can be summarized as follows.

  • 1.

    exchange 1-hop distances with neighbors

  • 2.

    locally compute the while loop of Algorithm 1 for r O(1/(logn + 24ρ)) (up to the radius for which it suf- fices to know the 1-neighborhood).

3. collect O(logn + 24ρ)-neighborhood (it is sufficient to only collect data about nodes which are still in V)

  • 4.

    compute the remaining iterations of the while loop

  • 5.

    compute clusters and cluster coloring (lines 9,10 of Al-

gorithm 1)

Computing the solution for small radii first and then collect- ing the rest of the neighborhood is done in order to obtain reasonable message sizes. We are now ready to formulate our main theorem.

Theorem 5.6. In the unit ball graph model, the above al- gorithm computes a (2, 24ρ)-decomposition in time O(logn+ 28ρ) where ρ is the doubling dimension of the underlying metric. Given that all distances and node IDs can be repre- sented by K bits, the maximal message size is at most



logn + 24ρ





bits. Hence, for constant ρ, the time complexity is O(logn)

and largest message needs at most O(((logn)O(1) bits.



Proof The time complexity follows from Lemma 5.5. For the correctness of the algorithm, it remains to prove that only collecting information about nodes in V for r O(1/(logn + 24ρ)) (steps 3 and 4) is sufficient. Because all communication of Algorithm 1 is on G, this is however clear.

For the bound on the message size, we need to have a closer look at steps 1, 3, and 5 where messages are ex- changed. In step 1, all nodes send at most distances and node IDs to their neighbors. This requires messages of size O( ·K). In step 3, a message can at most contain the whole R-neighborhood of a node, where R := O(logn + 24ρ). Let N be the maximum number of nodes which such a R- neighborhood can contain. If r Θ(1/(logn+24ρ)) denotes the larges radius for which the while loop has been computed in step 2, we know that for all pairs of nodes u, v ∈ V, we have d(u, v) > r. Therefore, balls of radius at most r/2 contain at most 1 such node. By the definition of ρ, the

maximum number of nodes in a ball of radius R, therefore is

N ( 2 ρ ) ( l o g 2 ( R / r ) + 1 )


R r



The number of edges in the R-neighborhood is at most quadratic in N. By the definition of R and r, the theorem thus follows.

Remark 1: Theorem 5.6 even holds if the nodes only know approxi- mations of the distances to their neighbors or if the triangle inequality is not completely satisfied. If distances are known up to a constant factor and/or if the triangle inequality holds up to a constant factor, it is not hard to see that the results of this section remain true up to constant factors.

Remark 2: The results of this section can be extended to other situa- tions than the unit ball graph model. Assume for instance that we have given a doubling metric (X, d). All points in X have to provide their part of the solution of a global prob- lem. Thereby, each member x X has to base its decision the ball Br(x) for some radius r. Theorem 5.6 shows that chosing the radius r O(logn) suffices for many natural problems. As a particular example, we might wish to con- struct an -net, that is, we want to select a set of points S such that any two selected points have distance at least and such that any point has a point in S at distance less than . In algorithms for metric spaces, -nets are a widely used structure [13]. Theorem 5.6 shows that every node can decide about whether it is in S based on its O( logn)- neighborhood only.



The communication graphs typically encountered in wire- less networking, peer-to-peer networks, or in the Internet tend to contain structure, which remains uncaptured when modeling them as general graphs. Specifically, these commu- nication graphs often have the property of bounded volume growth.


























an algorithm that computes a (O(1), O(1))-network decom- position in time O(logn), based only on the assumption that nodes know the distances to their neighbors. Using this decomposition algorithm, it is straightforward to ob- tain O(logn) time algorithms for computing a maximal in- dependent set, a + 1 coloring, or a constant approxima- tion to the minimum dominating set problem in graphs with bounded growth. The frequently studied unit disk graph be- ing a growth-bounded graph, all these results directly carry over to unit disk graphs, thus greatly improving the fastest previously known algorithms for these problems in unit disk


Moreover, our result are asymptotically optimal due to a matching Ω(logn) time-lower bound for computing a MIS on a ring [20]. We find it intriguing that from the point of view of locality, a simple toy-network such as the ring is as hard as the vast family of growth-bounded graphs.

Document info
Document views19
Page views19
Page last viewedSat Oct 22 23:52:39 UTC 2016