# Distributed Graph Diameter Approximation
## 5 Implementation in the MapReduce Model
Also, let \(\epsilon\in(0,1)\) be an arbitrarily fixed constant and define \(r_{\epsilon}^{*}\) as the minimum radius of any clustering of \(G\) with at most \(n^{\epsilon/2}/\log^{2}n\) clusters. With high probability, the above algorithm returns an estimate \(\Phi_{\text{approx}}(G)\) such that \(\Phi(G)\leq\Phi_{\text{approx}}(G)=O(\Phi(G)\log^{3}n)\), and can be implemented in the \(\text{MR}(M_{L},M_{A})\) model using_  
\[O\left(\ell_{4r_{\epsilon}^{*}}\log^{2}n\right)\]  
_rounds, with \(M_{L}=\Theta(n^{\epsilon})\) and \(M_{A}=\Theta(m)\)._  
Proof: Let \(\bar{r}\) be the first radius in the sequence \(\{w_{min}\cdot 2^{i}:i\geq 0\}\) such that \(\bar{r}\geq r_{\epsilon}^{*}\). Define \(k_{\epsilon}^{*}\) (resp., \(\bar{k}\)) as the minimum number of clusters in a clustering of \(G\) with radius \(r_{\epsilon}^{*}\) (resp., \(\bar{r}\)). It is straightforward to see that \(\bar{k}\leq k_{\epsilon}^{*}\). Since, by hypothesis, \(k_{\epsilon}^{*}\leq n^{\epsilon/2}/\log^{2}n\), we have that \(\bar{k}\leq n^{\epsilon/2}/\log^{2}n\). By Theorem 2, with high probability \(\textsc{RandCluster}(G,\bar{r})\) returns a clustering with \(O(\bar{k}\log^{2}n)=O(n^{\epsilon/2})\) clusters whose corresponding auxiliary graph has size \(O(n^{\epsilon})\). Therefore, with high probability, the MapReduce algorithm will complete the computation of the approximate diameter after an invocation of RandCluster with radius at most \(\bar{r}\). By Lemma 1, each invocation of RandCluster\((G,r)\) can be implemented in MapReduce using \(O(\ell_{2r}\log n)\) rounds with \(M_{L}=\Theta(n^{\epsilon})\) and \(M_{A}=\Theta(m)\). In particular, the round complexity of the last invocation (with radius at most \(\bar{r}\)) will upper bound the one of any previous invocation. Considering the fact that \(\bar{r}\leq 2r_{\epsilon}^{*}\), we have that the round complexity of each invocation is \(O(\ell_{4r_{\epsilon}^{*}}\log n)\). Note that \(r_{\epsilon}^{*}\leq\Phi(G)\), therefore the maximum number of values \(r\) for which RandCluster\((G,r)\) is executed is \(O(\log(\Phi(G)/w_{min}))\). Since \(\Phi(G)\leq n\cdot w_{max}\), where \(w_{max}\) is the maximum edge weight, and \(w_{max}/w_{min}\) is polynomial in \(n\), as we assumed at the beginning of Section 3, we have that the maximum number of invocations of RandCluster\((G,r)\) is \(O(\log n)\). Therefore, the aggregated round complexity of all the invocations of RandCluster up to the one finding a suitably small clustering is \(O(\ell_{4r_{\epsilon}^{*}}\log^{2}n)\). Moreover, it is easy to see that the computation of the auxiliary graph after each invocation of RandCluster and the computation of the diameter after the last invocation, which is performed on an auxiliay graph of size \(O(n^{\epsilon})\), does not affect neither the asymptotic round complexity nor the memory requirements. Finally, the bound on the approximation follows directly from Theorem 3, while the bounds on \(M_{L}\) and \(M_{A}\) derive from Lemma 1 and from the previous discussion. We observe that the term \(\ell_{4r_{\epsilon}^{*}}\) which appears in the round complexity of the algorithm stated in the above theorem, depends on the graph topology. In what follows, we will prove an upper bound to \(\ell_{4r_{\epsilon}^{*}}\), hence an upper bound to the round complexity, in terms of the _doubling dimension_ of \(G\), a topological notion which was reviewed in Section 2.2. To this purpose, we first need the following technical lemma. Lemma 2: _Let \(G\) be a graph with \(n\) nodes and maximum degree \(d\). If we remove each edge independently with probability at least \(1-1/d\), then, with high probability, the graph becomes disconnected and each connected component has size \(O(\ln n)\)._  
Proof: Let \(G^{\prime}=(V,E^{\prime})\) be a graph obtained from \(G=(V,E)\) by removing each edge in \(E\) with probability \(1-p>1-1/d\). Equivalently, each edge in \(E\) is included in \(E^{\prime}\) with probability \(p<1/d\), independent of other edges.