# Distributed Graph Diameter Approximation
## 5 Implementation in the MapReduce Model  
In this section we describe an algorithm for diameter approximation in MapReduce, which uses sublinear local memory and linear aggregate memory and, for an important class of graphs which includes well-known instances, features a round complexity asymptotically smaller than the one required to obtain a 2-approximation through the state-of-the-art SSSP algorithm by [20]. The algorithm runs the clustering-based strategy presented in the previous section for geometrically increasing guesses of the parameter \(r\), until a suitable guess is identified which ensures that the computation can be. carried out within a given local memory budget. Recall that the diameter-approximation strategy presented in the previous section is based on the use of Algorithm RandCluster to compute a clustering of the graph, and that, in turn, RandCluster entails the execution of sequences of growing steps. A growing step (lines 7\(\div\)10 of Algorithm 1) can be implemented in MapReduce as follows. We represent each node by the key-value pair \(((u,0),(c_{u},d_{u},g_{u},s_{u}))\) and each edge \((u,v)\in E\) by the two key-value pairs \(((u,1),(v,w(u,v)))\) and \(((v,1),(u,w(u,v)))\). We then sort all key-value pairs by key so that for every node \(u\) there will be a segment in the sorted sequence starting from \(((u,0),(c_{u},d_{u},g_{u},s_{u}))\) and followed by the pairs associated to its incident edges \(u\). At this point, a segmented prefix operation can be used to create, for each edge \((u,v)\) two pairs \(((u,v);(w(u,v),c_{u},d_{u},g_{u},s_{u}))\) and \(((u,v);(w(u,v),c_{v},d_{v},g_{v},s_{v}))\), which are then gathered by a single reducer to perform the possible update of \((c_{u},d_{u},g_{u},s_{u})\) or \((c_{v},d_{v},g_{v},s_{v})\) as specified by lines 8\(\div\)10 of Algorithm 1. A final prefix operation can be employed to determine the final value of each 4-tuple \((c_{u},d_{u},g_{u},s_{u})\), by selecting the update with minimum \(d_{u}\). By Theorem 1, each sorting and prefix operation can be implemented in \(\text{MR}(M_{L},M_{A})\) with \(O(\log_{M_{L}}n)\) rounds and linear aggregate memory. The MapReduce implementation of all other operations specified by Algorithm 1 is simple and can be accomplished within the same memory and round complexity bounds as those required by the growing steps. Recall that for a weighted graph \(G\), we defined \(\ell_{x}\) to be the maximum number of edges in any path of total weight at most \(x\). By combining the above discussion with the results of Theorems 1 and 2, we have:  
Lemma 1: _Let \(G\) be a connected weighted graph with \(n\) nodes and \(m\) edges. On the \(\text{MR}(M_{L},M_{A})\) model algorithm \(\textsc{RandCluster}(G,r)\) can be implemented in_  
\[O\left(\ell_{2r}\ \cdot\ \log n\ \cdot\ \log_{M_{L}}n\right)\]  
_rounds, with \(M_{A}=\Theta(m)\). In particular, if \(M_{L}=\Omega\left(n^{\epsilon}\right)\), for some constant \(\epsilon>0\), the number of rounds becomes \(O(\ell_{2r}\log n)\)._  
We are now ready to describe in detail our MapReduce algorithm for diameter approximation. Consider an \(n\)-node connected weighted graph \(G\), and let \(w_{min}\) be the minimum edge weight. For a fixed parameter \(\epsilon\in(0,1)\), the algorihm runs \(\textsc{RandCluster}(G,r)\) for geometrically increasing values of \(r\), namely \(r=w_{min}\cdot 2^{i}\), with \(i=0,1,\ldots\), until the returned clustering \(\mathcal{C}\) is such that the corresponding auxiliary graph \(G_{\mathcal{C}}\) has size (i.e., number of nodes plus number of edges) \(O(n^{\epsilon})\). At this point, the diameter \(\Phi(G_{\mathcal{C}})\) of \(G_{\mathcal{C}}\) is computed using a single reducer, and the value \(\Phi_{\text{approx}}(G)=\Phi(G_{\mathcal{C}})+2\cdot r_{\mathcal{C}}\), where \(r_{\mathcal{C}}\) is the radius of \(\mathcal{C}\), is returned as an approximation to the true diameter \(\Phi(G)\). We have:  
Theorem 4: _Let \(G\) be connected weighted graph with \(n\) nodes, \(m\) edges, and weighted diameter \(\Phi(G)\).