# Distributed Graph Diameter Approximation
## 3 Clustering Algorithm
We can finally bound the number of centers selected during the execution of the algorithm. We do so by partitioning the iterations into three groups based on the iteration index \(j\), and by reasoning on each group as follows:  
* Iterations \(j\), with \(1\leq j\leq h\): since, at the beginning of each such iteration \(j\), the number of uncovered nodes is clearly \(\leq n\) and the selection probability for each uncovered node is \(2^{j}/n\), by the Chernoff bound we can easily show that \(O(2^{j}\log n)\) centers are selected, with probability at least \(1-1/n^{2}\). * Iterations \(j\), with \(h<j<\log n\): by conditioning on the event \(\cap_{i=0}^{t-1}E_{i}\), we have that at the beginning of each such iteration \(j\) the number of uncovered nodes does not exceed \(n/2^{j-h-1}\) and the selection probability for an uncovered node is \(2^{j}/n\). Since \(2^{h}=\Theta(k^{*}\log n)\), by the Chernoff bound we can easily show that in iteration \(j\), \(O(2^{h})\) centers are selected, with probability at least \(1-1/n^{2}\). * Iteration \(\log n\): by conditioning on the event \(\cap_{i=0}^{t-1}E_{i}\) we have that at the beginning of iteration \(\log n\) the number of uncovered nodes is \(O(2^{h})\), and since in this iteration the selection probability is \(1\), all uncovered nodes will be selected as centers. Putting it all together we have that, by conditioning on \(\cap_{i=0}^{t-1}E_{i}\) and by [PERSON]'s inequality, with probability at least \(1-1/n\) the total number of centers selected by the algorithm is  
\[O\left(\sum_{j=1}^{h}2^{j}\log n+\sum_{j=h}^{\log n-1}2^{h}+2^{h}\right)=O \left(2^{h}\log n\right)=O\left(k^{*}\log^{2}n\right).\]  
The theorem follows. Algorithm RandCluster exhibits the following important property, which will be needed in proving the diameter approximation. Define the _light distance_ between two nodes \(u\) and \(v\) of \(G\) as the weight of the shortest path from \(u\) to \(v\) consisting only of light edges, that is, edges of weight at most \(2r\) (note that this distance is not necessarily defined for every pair of nodes). We have the following. **Observation 1**. : _For a specific execution of RandCluster\((G=(V,E,w),r)\), given a center \(c\in V\) selected at iteration \(i\), and a node \(v\in V\) at light distance \(d\) from \(c\), \(v\) cannot be covered by \(c\) (i.e., \(c_{v}\) cannot be set to \(c\) by the algorithm) in less than \(\lceil d/2r\rceil\) iterations. Also, by the end of iteration \(i+\lceil d/2r\rceil-1\), \(v\) will be covered by some cluster center (possibly \(c\))._Proof. : Let \(\pi\) be a path of light edges of total weight \(d\) between \(c\) and \(v\). In each iteration of the algorithm, the cluster centered at \(c\) is allowed to grow for a length at most \(2\tau\) along \(\pi\). Also, an easy induction suffices to show that any node at light distance at most \(2\tau s\) from \(c\) on the path will surely be covered (by \(c\) or another center) by the end of iteration \(s\). An immediate consequence of the above observation is the following. Let \(c\in V\) be a center selected at iteration \(i\), and \(v\in V\) a node at light distance \(d\) from \(c\). No center \(c^{\prime}\) selected at an iteration \(j>i\) and at distance at least \(d\) from \(v\) is able to cover \(v\). The reason is that any such center \(c^{\prime}\) would require the same number of iterations to reach \(v\) as \(c\), and by the time it is able to reach \(v\), \(v\) would have already been reached by \(c\) (or some other center) and marked as stable, which would prevent the reassignment to other centers.