# Distributed Graph Diameter Approximation
## 3 Clustering Algorithm
In a growing step, for each edge \((u,v)\) of weight \(w(u,v)\leq 2r\) (referred to as a _light edge_) such that \(c_{u}\) is defined (line 7), the algorithm checks two conditions: whether \(v\) is not stable and whether assigning \(v\) to the cluster centered at \(c_{u}\) would result in a radius compatible with the one stipulated for \(c_{u}\) at the current iteration, calculated using the _generation_ variable \(g_{u}\) (line 8). If both checks succeed, and if \(d_{u}+w(u,v)<d_{v}\), then the state of \(v\) is updated, assigning it to the cluster centered at \(c_{u}\), updating the distance, and setting \(g_{u}\) to the generation of \(c_{u}\) (line 10). In case two edges \(\{u,v\}\) and \(\{u^{\prime},v\}\) trigger a concurrent state update for \(v\), we let an arbitrary one succeed. When a growing step does not update any state, then all the covered nodes are marked as stable (line 13) and the algorithm proceeds to the next iteration. An example of one execution of RandCluster is described pictorially in Figure 2.  
```
1 foreach\(u\in V\)paralleldo\(\triangleright\) initialize the state of each node
2\((c_{u},d_{u},g_{u},s_{u})\leftarrow(nil,\infty,nil,false)\)
3 for\(i\gets 1\)to\(\log n\)do
4 foreach\(u\in V:c_{u}=nil\)paralleldo\(\triangleright\) for each uncovered node
5 With probability\(2^{i}/n\)do\((c_{u},d_{u},g_{u},s_{u})\leftarrow(u,0,i,true)\)\(\triangleright\) select as a new center
6 repeat\(\triangleright\) perform the growing steps
7 foreach\(\{u,v\}\in E:c_{u}\
eq nil\wedge w(u,v)\leq 2r\)paralleldo
8 if\(\
eg s_{0}\wedge d_{u}+w(u,v)\leq(i-g_{u}+1)\cdot 2r\)then\(\triangleright\) check if we should use this edge
9 if\(d_{u}+w(u,v)<d_{v}\)then\(\triangleright\) check if we should update the node
10\((c_{v},\,d_{v},\,g_{v},\,s_{v})\leftarrow(c_{u},\,d_{u}+w(u,v),\,g_{u},false)\)
11
12 untilNo state is updated
13 foreach\(u\in V\)paralleldo\(\triangleright\) mark all covered nodes as stable
14 if\(c_{u}\
eq nil\)then
15\(s_{u}\gets true\)
16
17 return\(\{(u,c_{u},d_{u}):u\in V\}\)
```  
**Algorithm 1**RandCluster(\(G=(V,E,w),r\))  
For a weighted graph \(G=(V,E,w)\) and a positive integer \(x\), define \(\ell_{x}\) as the maximum number of edges in any path in \(G\) of total weight at most \(x\). We have:  
Theorem 2: _Let \(G=(V,E,w)\) be a weighted graph, \(r\) be a parameter, and let \(k^{*}\) be the minimum integer such that there exists a \(k^{*}\)-clustering of \(G\) of radius at most \(r\). Then, with high probability, Algorithm \(\textsc{RandCluster}(G,r)\) performs \(O(\ell_{2r}\log n)\) growing steps and returns an \(O(k^{*}\log^{2}n)\)-clustering of \(G\) of radius at most \(2r\log n\)._  
Proof: The bounds on the number of growing steps and on the radius of the clustering follows straightforwardly from the fact that in each of the \(\log n\) iterations of the for loop, the radius of the current (partial) clustering can grow by at most an additive term \(2r\), hence the growth is attained along paths of distance at most \(2r\) which are covered by traversing at most \(\ell_{2r}\) edges in consecutive growing steps. We now bound the number of centers selected by the algorithm. We need to consider only the case \(k^{*}\leq n/\log^{2}n\) since, for larger values of \(k^{*}\), the claimed bound is trivial. The argument is structured as follows. We divide the iterations of the for loop into two groups based on a suitable index \(h\) (determined below as a function of \(k^{*}\) and \(n\)). The first group comprises iterations with index \(i\leq h\), where the low selection probability ensures that few nodes are selected as centers. The second group comprises iterations with \(i>h\), where, as we will prove, the number of uncovered nodes decreases geometrically in such a way to counterbalance the increase in the selection probability, so that, again, not too many centers are selected.