We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set $X \subset \mathbb{R}^d$ of $n$ points, the goal is to produce a spanning tree for $X$ with weight within a small factor of optimal. Euclidean MST is one of the most fundamental hierarchical geometric clustering algorithms, and with the proliferation of enormous high-dimensional data sets, such as massive transformer-based embeddings, there is now a critical demand for efficient distributed algorithms to cluster such data sets.

In low-dimensional space, where $d = O(1)$, Andoni, Nikolov, Onak, and Yaroslavtsev [STOC '14] gave a constant round MPC algorithm that obtains a high accuracy $(1+\epsilon)$-approximate solution. However, the situation is much more challenging for high-dimensional spaces: the best-known algorithm to obtain a constant approximation requires $O(\log n)$ rounds. Recently Chen, Jayaram, Levi, and Waingarten [STOC '22] gave a $\tilde{O}(\log n)$ approximation algorithm in a constant number of rounds based on embeddings into tree metrics. However, to date, no known algorithm achieves both a constant number of rounds and approximation.

In this paper, we make strong progress on this front by giving a constant factor approximation in $\tilde{O}(\log \log n)$ rounds of the MPC model. In contrast to tree-embedding-based approaches, which necessarily must pay $\Omega(\log n)$-distortion, our algorithm is based on a new combination of graph-based distributed MST algorithms and geometric space partitions. Additionally, although the approximate MST we return can have a large depth, we show that it can be modified to obtain a $\tilde{O}(\log \log n)$-round constant factor approximation to the Euclidean Traveling Salesman Problem (TSP) in the MPC model. Previously, only a $O(\log n)$ round was known for the problem.

§ INTRODUCTION

The minimum spanning tree (MST) problem is one of the most
fundamental problems in combinatorial optimization, whose
algorithmic study dates back to the work of Boruvka in 1926 [13]. Given a set of points and distances between the points, the goal is to compute a tree over the points of minimum total weight. The MST problem has received a tremendous amount of attention from the algorithm design community, leading to a large toolbox of methods for the problem [17, 40, 39, 30, 35, 5, 2, 9, 24, 18, 23, 19, 22].

In the offline setting, where the input graph $G = (V,E)$ is known in advance, an exact randomized algorithm running in time $O(|V| + |E|)$ is known. The version of the problem where the input lies in Euclidean space has also been extensively
studied, see [29] for a survey. In this setting,
the vertices of the graph are points in $\R^d$, and the
set of weighted edges is (implicitly given by) the set of all ${n \choose 2}$ pairs of vertices and the pairwise Euclidean distances. Despite the implicit representation, the best known runtime bound for computing an Euclidean MST exactly is $n^2$, even for low-dimensional inputs. For approximations, the best known runtime bound is $O(n^{2-2/(\lceil d/2\rceil +1) +\eps})$ for obtaining a $(1+\eps)$-approximate solution [3],  and is $n^{1+1/c^2 }$ for an $O(c)$-approximation [34].

The Euclidean variant of the MST problem is particularly important in light of the tremendous success of modern embedding models in machine learning [47, 49, 36, 25]. Such models encode a data point, such as an image, video, or text, into a vector in high-dimensional space, so that the semantic similarity between two data points is accurately represented by the Euclidean distance between the corresponding embedding vectors.
In this setting, computing an MST is a well-known and successful technique for clustering data [46, 51, 54, 33, 10], which is a core component of many ML pipelines for large embedding datasets.

To deal with the sheer size of these modern embedding datasets, the typical approach is to implement algorithms in massively parallel computation systems such as MapReduce [26, 27], Spark [53], Hadoop [50], Dryad [37] and others. The Massively Parallel Computation (MPC) model [43, 32, 12, 5] is a computational model for these systems that balances accurate modeling with theoretical elegance. The MST problem in particular has been extensively studied in this model [5, 43, 6, 44, 1, 20]. For the non-Euclidean case, when the input is a graph with $n$ vertices and $m$ edges, and each machine only has $n^{\varepsilon}$ space for some constant $\varepsilon<1$, algorithms that obtain a constant approximation in $O(\log n)$ rounds and linear $O(m)$ total space are known using connected components algorithms [43, 6, 11, 15]. However, improving the round complexity is unlikely, as such an algorithm would refute the longstanding 1-Cycle vs. 2-Cycle conjecture [52, 48, 45, 7].

The Euclidean MST problem, on the other hand, is not as well understood in the MPC model as its graph-based counterpart. For low-dimensional Euclidean space, where $d$ is a constant, [5] gave a $(1+\varepsilon)$ approximate algorithm using only $O(1)$ MPC rounds. However, the landscape becomes much more mysterious and challenging in the high dimensional-setting.

One prevalent approach for the high-dimensional setting is the spanner method: one first constructs a $c$-approximate Euclidean spanner (i.e., a sparse graph over the points whose shortest path distance approximates the Euclidean distance to a factor of $c$) for some constant $c \geq 1$. Such spanners can be constructed with $O(n^{1+1/c})$ edges in $O(1)$ MPC rounds [28, 14]. With the spanner in hand, one can simply run the aforementioned graph-based MST algorithm to obtain a constant approximation in $O(\log n)$ rounds. However, in the Euclidean variant we have the benefit of the metric-space structure, and the one-cycle two-cycle lower bound does not apply. Thus, settling for $O(\log n)$ rounds for Euclidean MST is undesirable and perhaps unnecessary.

To date, the only known method for obtaining MPC algorithms with a $o(\log n)$ round complexity for high-dimensional MST is the tree-embedding method [8]. In this method, one probabilistically embeds the Euclidean points $X \subset \R^d$ into a (log-depth) tree-metric and then computes the optimal MST in the tree metric. The latter is a simple object that can be computed in the MPC model in $O(1)$ rounds and $\tilde{O}(n)$ total space. Indyk [39] gave a tree embedding that obtains a $O(d \log n)$ approximation and can be computed in the MPC model in $O(1)$ rounds and $\tilde{O}(n)$ total space. This was later improved by [20] to a $\tilde{O}(\log n)$ approximation, resulting in a $O(1)$ round $\tilde{O}(\log n)$ approximation algorithm. However, it is known that the tree-embedding method must suffer a $\Omega(\log n)$ approximation in the worst case [8].

In summary, one can obtain constant approximations in $O(\log n)$ rounds via the spanner method, or a $\tilde{O}(\log n)$ approximation in constant rounds via the tree embedding method. However, both methods individually face hard barriers to removing the $O(\log n)$ factor from their round complexity or approximation (respectively). A natural question is whether this trade-off is intrinsic: namely if any algorithm for high-dimensional Euclidean MST must always use at least $\Omega(\log n)$ rounds or pay a $\Omega(\log n)$ approximation. Specifically, in this work we address the following question:

Is it possible to compute an $o(\log n)$-approximate Euclidean minimum spanning tree in $o(\log n)$ rounds of the MPC model?

An even stronger question is whether a $O(1)$ approximation is possible in $O(1)$ rounds.
As a positive signal in this direction, a recent result [16] demonstrated that the cost of the MST can be estimated to a constant factor in $O(1)$ MPC rounds. However, their algorithm is a sampling-based estimator that is far removed from a procedure that can actually compute an approximate MST. Moreover, separations between the complexity of estimating the cost of a solution and producing that solution are ubiquitous in high-dimensional geometry (e.g. for metric MST in the sublinear query model [38, 24]). For computing the MST in a distributed setting, such a result was only known in the more powerful Congested Clique [42] model, however implementing this algorithm in the MPC model would require $\Omega(n)$ space per machine.

In this work, we provide a positive resolution to the above question by designing a fully scalable[Meaning that each machine has only $n^{\eps}$ space for a constant $\eps < 1$, see Preliminaries <ref>.] MPC algorithm in $\tilde{O}(\log\log n)$ rounds for a constant approximation of the Euclidean MST. In addition, the total space required by our algorithm is at most $O(n^{1+\varepsilon}+nd)$ where $\varepsilon>0$ can be an arbitrarily small constant. Our result makes substantial progress towards the stronger goal of a $O(1)$ approximation in $O(1)$ rounds. Specifically, our main result is:

Given a set $X \subset \mathbb{R}^d$ of $n$ points, there is a MPC algorithm which outputs an $O(1)$-approximate MST of $X$ with probability at least $0.99$ in at most $O(\log\log(n)\cdot \log\log\log(n))$ rounds.
The total space required is at most $O(nd+n^{1+\varepsilon})$ and the per-machine space is $O((nd)^\varepsilon)$, where $\varepsilon>0$ is an arbitrarily small constant.

At a high-level, our algorithm bypasses the $\Omega(\log n)$ barriers intrinsic to the spanner and tree-embedding methods by combining the two approaches.
Specifically, our algorithm builds a spanner and attempts to compute the MST of that spanner. However, while doing so we do not forget about the original metric structure.
Specifically, our algorithm will exploit the metric structure by generating a spanning forest using both the edges of the spanner and geometric space partitions (which underpin tree-embedding methods).

Eucledian TSP. We leverage our algorithm for MST to develop the first $O(1)$-approximation to the Euclidean traveling salesman problem (TSP) in $o(\log n)$ rounds.
At a first glance, one may think that  $O(1)$-approximate TSP should directly follow from a $O(1)$-approximate MST since any shortcutted traverse of the $O(1)$-approximate MST gives an $O(1)$-approximate TSP.
However, the approximate MST that we computed may have diameter $\Theta(n)$, and all existing fully scalable MPC algorithms require at least $\Omega(\log(\text{diameter}))=\Omega(\log n)$ rounds to compute a traversal of the tree.
To resolve this issue, we develop a new $O(\log\log(n))$-round fully scalable MPC algorithm to compute a traverse of our approximate MST by utilizing the information of a hierarchical decomposition of the point set that we generate while computing the approximate MST. This results in the following:

Given a set $X \subset \mathbb{R}^d$ of $n$ points, there is a TSP algorithm which outputs an $O(1)$-approximate TSP of $X$ with probability at least $0.99$ in at most $O(\log\log(n)\cdot \log\log\log(n))$ rounds.
The total space required is at most $O(nd+n^{1+\varepsilon})$ and the per-machine space is $O((nd)^\varepsilon)$, where $\varepsilon>0$ is an arbitrarily small constant.

§.§ Preliminaries

MPC Model. In the Massively Parallel Computation (MPC) model, there are $p$ machines and each machine has local memory $s$; thus the total space available in the system is $p\cdot s$.
The space is measured in words where each word has $O(\log(p s))$ bits.
The input data has size $N$ and is distributed arbitrarily on $O(N/s)$ machines at the beginning of the computation.
If the total space satisfies $p\cdot s = O(N^{1+\gamma})$ for some $\gamma \geq 0$, and the local space satisfies $s = O(N^{\eps})$ for some constant $\eps \in (0,1)$, then the model is called the $(\gamma,\eps)$-MPC model [6].

The computation in the MPC model proceeds in rounds.
In every round, each machine performs arbitrary local computation on the data stored in its memory.
At the end of each round, each machine sends some messages to the other machines.
Since each machine only has local memory $s$, the total size of messages sent or received by a machine in one round can not be larger than $s$.
For example, a machine can send a single message with size $s$ to an arbitrary machine, or it can send a size $1$ message to other $s$ machines, but it cannot send a size $s$ message to every machine in one round.
In the next round, each machine only holds received messages in its local memory.
At the end of the computation, the output is stored in a distributed way on the machines.
The parallel running time (number of rounds) of an MPC algorithm is the number of above computation rounds needed to finish the computation.

We consider $\eps\in(0,1)$ to be an arbitrary constant in this paper, i.e., our algorithms can work when the memory of each machine is $s=O(N^{\eps})$ for any constant $\eps\in(0,1)$.
Such algorithms are called fully scalable algorithms [6].
Our goal is to develop fully scalable algorithms which only require a small number of rounds and a small total space.

Basic Notation. In the remainder of the paper, we use $X$ to denote a dataset of points that we wish to solve either Minimum Spanning Tree or Traveling Salesman Problem over. We use $n$ to denote the size of $X$ and $d$ to denote the dimensionality of $X$ (i.e., $n = |X|$ and $X \subset \R^d$). Additional notation is defined in the relevant sections.

Euclidean Minimum Spanning Tree (MST) and  Travelling Salesman Problem (TSP) In the Euclidean MST problem, the input is a set of $n$ points $X \subset \R^d$, where we assume that each coordinate $x_i$ of a point $x \in \R^d$ can be stored in a single word of space (i.e., $O(\log ps)$ bits). The points $X$ implicitly define a complete graph, where the vertices are $X$, and for any $x,y \in X$ the weight of the edge $(x,y)$ is $\|x-y\|_2$. Our goal will be to produce a spanning tree $T$ of this complete graph such that the weight of $T$, defined as $\sum_{(x_i, x_j) \in T} \| x_i - x_j \|_2$ is within a constant factor of the minimum spanning tree weight. We write $\MST(X)$ to denote the optimal MST weight.

In the Euclidean TSP problem, the input is the same as the MST problem.
But instead of outputting a spanning tree, we want to output a Hamiltonian cycle $C$ of $X$, i.e., each point appears on the cycle exactly once, such that the total length of the cycle $\sum_{(x_i,x_{j})\in C}\|x_i-x_{j}\|_2$ is minimized up to a constant factor.

§.§ Technical Overview

§.§ Other Related Work

The MST problem has been studied extensively in multiple models of sublinear computation, including streaming, distributed algorithms, and the sublinear query model.
In the sublinear query model, the implicit input is the set of $\binom{n}{2}$ distances and the goal is to estimate
the weight of the MST while making a sublinear number of queries to the distances. It is known that any algorithm which actually computes an approximate MST requires $\Omega(n^2)$ queries [38], hence the focus on estimating the cost. To this end, Chazelle, Rubinfeld, and Trevisan [22] gave an algorithm based on estimating connected components, that gives a $(1+\epsilon)$-factor approximation for arbitrary graphs of maximum degree $D$ and edge weights in $[1,W]$ using
at most $O(D W \epsilon^{-3})$ queries.
This result was improved by Czumaj and Sohler [24] for metric (e.g., Euclidean) MST, who
gave a $(1+\eps)$ approximation with $\tilde{O}(n \eps^{-8})$ queries.

In the streaming model, the points $X \subset \R^d$ arrive in a stream, possibly with deletions, and the goal is to estimate the cost of the MST in small space (as outputting the MST would require $\Omega(n)$ space). The first algorithm for streaming Eucledian MST was due to Indyk [39], who gave a $O(\log^2 n)$ approximation in $\polylog(n)$ space.  This was later improved by [20] to a $\tilde{O}(\log n)$ approximation in $\polylog(n)$ space, and then a $\tilde{O}(1/\eps^2)$ approximation in $O(n^\eps)$ space by [16]. The first two works employed tree embedding based approaches, whereas [16] used a connected component-based estimator similar to those used in [22, 24]. For low-dimensional space, [30] gives a $(1+\eps)$ approximation with space exponential in the dimension, although the techniques in this paper rely heavily on the construction of exponentially sized $\eps$-nets.

The above streaming algorithms are linear sketches and therefore can be used in the MPC model to obtain constant round approximations of the cost of the MST (see e.g. [5] for a reduction from lienar sketching to the MPC). However, there is a substantial gap between estimating the cost of the MST and producing the MST. For instance, the estimators in the papers [22, 24, 16] are based on sampling vertices and computing the size of their connected components, thus no edges or approximate tree structure can be derived from this approach. As described in Section <ref>, substantial challenges arise when attempting to construct a tree in a consistent (i.e., no cycles) and cost-effective way.

§ DESCRIPTION OF THE MST ALGORITHM IN THE OFFLINE SETTING

In this section, we give a description for generating an $O(1)$-approximate MST, that can be implemented in the MPC model. However, we defer the details of the MPC implementation to Section <ref>.

We first assume WLOG that $d = \Theta(\log n)$, using the Johnson-Lindenstrauss lemma [41].
We will define two parameters $\alpha, \beta$ such that both $\alpha/\beta$ and $\beta$ are at least $(\log n)^C$ for some sufficiently large constant $C$. We also assume WLOG $\alpha = 2^{2^g}$ for some integer $g$ (which can always be done by replacing $\alpha$ with some $\alpha' \in [\alpha, \alpha^2]$).
Define $G$ to be the complete weighted graph on $X$, where $(x, y) \in X$ have an edge of weight $d(x, y)$. Define the threshold graph $G_t$ to connect two points $x, y$ if $d(x, y) \le t$. We also define $\cP_t$ to be the partition of $X$ based on the connected components of $G_t$.

Finally, since we are only hoping for a constant-factor approximation, by Standard discretization methods (see, e.g., Proposition 1 in [16]), we may assume the aspect ratio is at most $\tilde{O}(n)$. More precisely, we may assume that the minimum distance between any two points is at least $\alpha^{100} = (\log n)^{O(1)}$, and the maximum distance between any two points is at most $O(n \cdot \alpha^{101}) \le n^2$ (for $n$ sufficiently large).
We shift the point set such that each coordinate of each point has value in $[0,\Delta]$ where $\Delta$ is a sufficiently large power of $2$ and $\Delta = O(n^2)$.

We also note a few definitions.

Given a dataset $X$, a partition of $X$ is a split of $X$ into one or more pairwise disjoint subsets of $X$, such that every element $x \in X$ is in exactly one of the subsets.

Given two partitions $\cP, \cQ$ of $X$, we say that $\cP$ refines $\cQ$ (or equivalently, $\cQ$ is refined by $\cP$) if every partition component in $\cP$ is a subset of some partition component in $\cQ$. We use the notation $\cP \sqsupseteq \cQ$ (or $\cQ \sqsubseteq \cP$).

For a positive integer $n$, we define the 2-adic valuation $v_2(n)$ to be the largest nonnegative integer $k$ such that $2^k|n$.

High level approach: First, we will approximately generate $\cP_t$, the connected components of $G_t$, for $t = 1, \alpha, \alpha^2, \dots, \alpha^{H}$, for $H = \Theta(\log n/\log\log n)$. We will approximately compute each of these partitions $\cP_t$ in parallel, using $h = O(\log \log n)$ rounds. Next, given the approximate connected components for $G_{\alpha^k}$ and $G_{\alpha^{k+1}}$, we attempt to generate approximate connected components for $G_{2 \alpha^k}, G_{4 \alpha^k}, \dots, G_{\alpha^{k+1}/2}, G_{\alpha^{k+1}}$. Finally, we generate edges to form an approximately minimal spanning tree.

Quadtree and Spanner:
We start off knowing a randomly shifted quadtree $Q$. We recall the definition of a quadtree, along with some relevant notation.

A randomly shifted Quadtree is constructed as follows.
First, we choose a random vector $a = (a_1,a_2,\dots,a_d)\in\mathbb{R}^{d}$, where each coordinate $a_i$ is drawn uniformly from $[0,\Delta]$.
For each $t$ that is a power of $2$ between $1$ and $2 \Delta$ (where $\Delta = \Theta(n^2)$ is a power of $2$), we use $a$ to generate a grid of side length $t$, which we call the grid at level $t$. Specifically, there is a one-to-one correspondence between each grid cell in level $t$ and each vector $(c_1,c_2,\dots,c_d)\in\mathbb{Z}^d$, i.e., the corresponding cell denotes the set of points:
\{(x_1,x_2,\dots,x_d)\in\mathbb{R}^d \mid \forall i\in [d], x_i\in[c_i\cdot t-a_i,(c_{i}+1)\cdot t-a_i)\}\subset \mathbb{R}^d.
Finally, for any cell $c$ at level $t$, define $X_c$ to be the set of points in $X$ contained in the cell $c$.

Note that the grids are nested, i.e., for every $t$, every cell of side length $t$ in the Quadtree is contained in a cell of side length $2t$.
Finally, for the largest grid length $2\Delta$, it is easy to see that there is a unique cell $c$ in level $\Delta$ such that $X_c = X$. This is because every $a_i \in [0, \Delta]$ and because we assume all data points have coordinates in $[0, \Delta]$.

Next, we will also assume we have a series of $2$-hop Euclidean spanners. We recall the definition of a $2$-hop Euclidean spanner.

Given a dataset $Y \in \R^d$, a $C$-approximate $2$-hop Euclidean spanner of length $t$ is a graph on $Y$ with edge set $E$, with the following two properties.

* For any $p, q \in X$ such that $\|p-q\|_2 \le t$, either $(p, q) \in E$ or there exists $r \in X$ such that $(p, r), (r, q) \in E$.

* For any two points $p, q \in Y$ with $\|p-q\|_2 > t$, we must have $(p, q) \not\in E$.

In other words, any two points within distance at most $t$ are connected by a path of length at most $2$, but any two points of distance more than $t$ cannot be directly connected in the graph.

We will use the fact that for any dataset $Y$, any level $t$, and any constant $0 < \eps < 1$, there exists a $O(1/\eps)$-approximate $2$-hop Euclidean spanner of $Y$ with at most $O(|Y|^{1+\eps})$ edges.
More specifically, for each $t$ a power of $2$, let $k$ be such that $\alpha^{k-1} < t \le \alpha^k$. We generate $\tilde{G}_t(X_c)$ to be a $2$-hop Euclidean spanner of length $t$ generated on $X_c$, where $c$ is a cell at level $\alpha^{k+1}/\beta$ in the quadtree, where $\tilde{G}_t(X_c)$ has at most $O(|X_c|^{1+\eps})$ edges. In addition, let $\tilde{G}_t$ be the union of $\tilde{G}_t(X_c)$ across all cells $c$ at level $\alpha^{k+1}/\beta$.
We also make sure that $\tilde{G}_t \subseteq \tilde{G}_{2t}$ for all $t$, simply by adding $\tilde{G}_t$ to $\tilde{G}_{2t}, \tilde{G}_{4t}, \dots$: it is clear that this does not violate the definition of an $O(1/\eps)$-approximate spanner.
Since there are at most $O(\log n)$ such levels, and since $\sum |X_c|^{1+\eps} \le (\sum |X_c|)^{1+\eps} = n^{1+\eps}$, every $\tilde{G}_t$ has at most $O(n^{1+\eps})$ edges.
Finally, we let $\tilde{\cP}_t$ be the partitioning of $X$ based on the connected components of $\tilde{G}_t$. Note that $\tilde{\cP}_t \sqsupseteq \tilde{\cP}_{2t}$ for all $t$, since $\tilde{G}_t \subseteq \tilde{G}_{2t}$.

We note that the assumptions on dimensionality reduction, aspect ratio, and our assumption that we have a Quadtree $Q$ and $2$-hop $O(1/\eps)$-approximate Euclidean spanners $\tilde{G}_t$ can all be achieved using $O(1)$ rounds of MPC. We discuss this in Section <ref>.

Leader Compression Algorithm

We need to first explain the leader compression algorithm. We assume that we start out with some starting partition $\cP$ of a dataset $X$, and are given some graph $H$ on $X$. The goal is to connect components that have edges between them in $H$, to form larger connected components.

Formally, we will define a single round of leader compression on $\cP$ with respect to $H$ as follows.

For each connected component $C \in \cP,$ we assign every $x \in C$ some leader, which is a vertex $x^* \in C$. A round of leader compression works as follows.
First, each leader will generate a random bit (uniformly 0 or 1), and will broadcast the value to all of its descendants (i.e., the rest of the vertices in $C$). So, every $x_i$ now has a value of 0 or 1, matching that of its leader.
Next, every $x_i$ with a value of 1 will send a message to all of its neighbors in the graph $H$. Importantly, after these messages, every $x_j$ that has value 0 knows the set of $x_i$ that have value 1 (which means they do not have the same leader, since $x_j$ has value 0) and are connected to $x_j$ in $H$. For the purpose of MPC implementation, it will suffice for each such $x_j$ to know a single such $x_i$ (if one exists).
Simultaneously, every $x_j$ that has value 0 will choose such an $x_i$ (assuming such an $x_i$ exists), and $x_j$ then sends the $x_i$ value to its current leader $x_k$, in $O(1)$ rounds of MPC. Each leader $x_k$ with value 0 will choose a single descendant $x_j$ with such a $x_i$ (if such an $x_j$ exists: note $j$ could equal $k$). Then, $x_k$ will update its leader (as well as the leader of all of $x_k$'s descendants) to be the leader of $x_i$.

Finally, we can define $h$ rounds of leader compression on $\cP$ with respect to $H$ as follows. For the first round, we run a round of leader compression on $\cP$ with respect to $H$. We now have a potentially coarser partition of connected components, and for the second round we run leader compression on this new partition with respect to $H$. We repeat this for $h$ rounds, and at each round we use the updated partition and assignments of leaders.

We include pseudocode for a round of leader compression in Algorithm <ref>.

Part 1: Approximately generating $\cP_t$, $t = \alpha^k$.
We start with a randomly shifted grid from $Q$ of level $t/\beta$. We will automatically connect all points that are in the same cell. (Note that all such points must have distance at most $t \sqrt{d}/\beta$ from each other, so they should be in the same connected component at this level anyway). This forms an initial partitioning $\cP_t^{(0)}$ of $X$.

Now, each (nonempty) component $\cP_t^{(0)}$ starts with a “leader” point.
We now perform $h = O(\log \log n)$ rounds of leader compression on $\cP_t^{(0)}$ with respect to $\tilde{G}_t$. At the end of these rounds, we will have connected components and thus have $\bar{\cP}_t$, our preliminary estimate for $\cP_t$.

We will next convert $\bar{\cP}_t$ into $\hat{\cP}_t$ by doing some additional merging. For each component $S \in \bar{\cP}_t$, we will check whether $S$ is a complete component. To do so, we look at all of the edges in $\tilde{G}_t$: for each edge we check whether its endpoints are in the same connected component in $\bar{\cP}_t$. If not, we send a message to both endpoints. Every vertex will then know if there is an edge leaving it into another connected component. Thus, every leader of a connected component will know if the connected component has any edges leaving it. We call such a component incomplete. To form $\hat{\cP}_t$, we group together all incomplete components in $\bar{\cP}_t$ with their leaders in the same cell $c$ at level $\alpha^{k+1}/\beta$.

We include pseudocode for this step in Algorithm <ref>.

Part 2: Approximately generating $\cP_t$, $\alpha^{k} < t < \alpha^{k+1}$, $t$ a power of $2$.
Recall that $\alpha = 2^{2^g}$. We will generate $\hat{\cP}_t$ in decreasing order of $v_2(\log_2 t)$ (recall Definition <ref> for $v_2(\cdot)$).

In other words, we first generate $\hat{\cP}_t$ for $t = \alpha^{k + 1/2} = \alpha^k \cdot 2^{2^{g-1}}$, then for $t = \alpha^{k + 1/4} = \alpha^k \cdot 2^{2^{g-2}}$ and $t = \alpha^{k + 3/4} = \alpha^k \cdot 2^{3 \cdot 2^{g-2}}$ simultaneously, and so on. This will result in $g = \log_2 \log_2 \alpha$ iterations.
When generating some $\alpha^{k} < t < \alpha^{k+1}$, we define $\kappa = 2^{2^{v_2(\log_2 t)}}$. We note that $v_2(\log_2 (t/\kappa)), v_2(\log_2 (t \cdot \kappa)) > v_2(\log_2 t)$, so we have already generated $\hat{\cP}_{t/\kappa}$ and $\hat{\cP}_{t \cdot \kappa}$. We will use these two partitions to generate $\hat{\cP}_{t}$.

To do so, we start with the connected components from $\hat{\cP}_{t/\kappa}$. Then, we perform $h = O(\log \log n)$ rounds of leader compression on $\hat{\cP}_{t/\kappa}$ with respect to $\tilde{G}_t$, to create $\bar{\cP}_t$.
Finally, we convert $\bar{\cP}_t$ to $\hat{\cP}_t$, by performing merging in a similar way as in Part 1. Specifically, we check each edge in $\tilde{G}_t$ and see if the endpoints are in the same connected component in $\bar{\cP}_t$, and use this information to determine whether each component in $\bar{\cP}_t$ is complete or incomplete. (Namely, a connected component $C$ in $\bar{\cP}_t$ is incomplete iff there exists an edge $\tilde{G}_t$ with exactly one vertex in $C$.) Finally, we group together all incomplete connected components with their leaders in the same connected component in $\hat{\cP}_{t \cdot \kappa}$.

We include pseudocode for this step in Algorithm <ref>.

Part 3: Generating the edges. We have listed out the approximate connected components $\hat{\cP}_t$ for each $t$ a power of $2$. Now, for any such $t$, we want to generate edges connecting $\hat{\cP}_{t/2}$ into $\hat{\cP}_t$.

We will again perform $h = O(\log \log n)$ rounds of leader compression on $\hat{\cP}_{t/2}$ with respect to $\tilde{G}_t$, but this time we keep track of all edges that we added. We will show that the partition we generate after doing leader compression still refines $\hat{\cP}_t$. So, to finish generating $\hat{\cP}_t$ along with the necessary edges, we connect all disconnected components in each partition of $\hat{\cP}_t$, using arbitrary edges.

We include pseudocode for this step in Algorithm <ref>.

$\textsc{LeaderCompression}(\cP, \ell, H, \text{Edges})$: A single round of leader compression on $\cP$ with respect to $H$, where $\ell$ is the function mapping each node to its leader in the partition. $\text{Edges}$ is a boolean value that denotes whether we want to generate edges (which is only needed for Step 3).

[1]
$S = \{\ell(x): x \in X\}$ $S$ is the set of leader nodes
$x \in S$
$b_x \leftarrow \text{Unif}(\{0, 1\})$. $b_x$ is the random bit for leader node $x$
$x \in X$

$b_x \leftarrow b_{\ell(x)}$.
$x \in X$ with $b_x = 1$
$e = (x, y) \in H$
$x$ sends message “$(x,\ell(x))$” to $y$
$y \in X$ with $b_y = 0$
Select any message $(x,\ell(x))$ sent to $y$ (if it exists)
$y$ sends message “$(x, y, \ell(x))$” to $\ell(y)$.
$z \in S$ with $b_z = 0$
Select any message $(x, y, \ell(x))$ sent to $z$ (if it exists)
$E \leftarrow E \cup \{(x, y)\}$. $E$ is a set of edges, initialized to $\emptyset$
$z$ broadcasts message “$\ell(x)$” to all descendants, all descendants (including $z$) update their leader to be $\ell(x)$.
Update partition $\cP$ based on leader function.
Return $(\cP, \ell, H, E).$ If Edges is False, we return False instead of $E$.

$\textsc{Part1}(X, t, Q, \tilde{G}_t)$: Generating $\hat{\cP}_t$ for $t = \alpha^k$.

[1]
Generate partition $\cP_t^{(0)}$ of $X$ based on the quadtree at level $t/\beta$, i.e., two points in $X$ are in the same connected component in $\cP_t^{(0)}$ if and only if they are in the same cell at level $t/\beta$.
Choose an arbitrary leader for each (nonempty) component in $\cP_t^{(0)}$, and let the corresponding leader mapping with respect to $\cP_t^{(0)}$ to be $\ell_t^{(0)}$.
$i = 1$ to $h = O(\log \log n)$
$(\cP_t^{(i)}, \ell^{(i)}_t, \tilde{G}_t, \text{False}) \leftarrow \textsc{LeaderCompression}(\cP_t^{(i-1)}, \ell^{(i-1)}_t, \tilde{G}_t, \text{False})$.
$e = (x, y) \in \tilde{G}_t$
$\ell^{(h)}_t(x) \neq \ell^{(h)}_t(y)$
$(x, y)$ sends Incomplete to both $x$ and $y$
$x \in X$ that received Incomplete message
$x$ sends Incomplete to $\ell^{(h)}_t(x)$.
Merge all Incomplete components with leaders in the same cell in $Q$ at level $\alpha^{k+1}/\beta$, to form $\hat{\cP}_t$.

$\textsc{Part2}(X, t, \tilde{G}_t, \hat{\cP}_{t/\kappa}, \hat{\cP}_{t \cdot \kappa})$: Generating $\hat{\cP}_t$, given $\hat{\cP}_{t/\kappa}$ and $\hat{\cP}_{t \cdot \kappa}$.

[1]
Initialize $\cP_t^{(0)} \leftarrow \hat{\cP}_{t/\kappa}$, and choose an arbitrary leader for each component in $\cP_t^{(0)}$.
Let the corresponding leader mapping with respect to $\cP_t^{(0)}$ to be $\ell_t^{(0)}$
$i = 1$ to $h = O(\log \log n)$
$(\cP_t^{(i)}, \ell^{(i)}_t, \tilde{G}_t, \text{False}) \leftarrow \textsc{LeaderCompression}(\cP_t^{(i-1)}, \ell^{(i-1)}_t, \tilde{G}_t, \text{False})$.
$e = (x, y) \in \tilde{G}_t$
$\ell^{(h)}_t(x) \neq \ell^{(h)}_t(y)$
$(x, y)$ sends Incomplete to both $x$ and $y$
$x \in X$ that received Incomplete message
$x$ sends Incomplete to $\ell^{(h)}_t(x)$.
Merge all Incomplete components with leaders in the same component in $\hat{\cP}_{t \cdot \kappa}$, to form $\hat{\cP}_t$.

$\textsc{Part3}(X, t, \tilde{G}_t, \hat{\cP}_{t/2}, \hat{\cP}_{t})$: Generating the edges merging $\hat{\cP}_{t/2}$ into $\hat{\cP}_{t}$.

[1]
Initialize $\cP_t^{(0)} \leftarrow \hat{\cP}_{t/2}$, and choose an arbitrary leader for each component in $\cP_t^{(0)}$. Let the corresponding leader mapping with respect to $\cP_t^{(0)}$ to be $\ell_t^{(0)}$.
$i = 1$ to $h = O(\log \log n)$
$(\cP_t^{(i)}, \ell^{(i)}_t, \tilde{G}_t, E_t^{(i)}) \leftarrow \textsc{LeaderCompression}(\cP_t^{(i-1)}, \ell^{(i-1)}_t, \tilde{G}_t, \text{True})$.
Create an arbitrary star on the set of leaders $\{\ell^{(h)}_t(x)\}$ in the same component in $\hat{\cP}_t$, to create a forest of stars $F_t$.
Return $F_t \cup \bigcup_{i=1}^h E_t^{(i)}$.

§ ANALYSIS OF THE OFFLINE ALGORITHM

§.§ Comparison to the Spanner Graph

Given the spanners $\tilde{G}_t$ for each $t$ a power of $2$ (as described in Section <ref>), we create the graph $\tilde{G}$ as follows. For each pair of distinct vertices $(y, z)$, we assign $(y, z)$ the weight $t$ for $t$ the smallest power of $2$ such that $(y, z) \in \tilde{G}_t$ (if such a $t$ exists). Otherwise, we do not connect $(y, z)$.

We first note that any spanning tree in $\tilde{G}$ does not increase in cost by too much after converting to the corresponding Euclidean spanning tree.

Suppose that $T$ is a spanning tree in $\tilde{G}$. Then, the cost of $T$ in $X$ (i.e., over the true Euclidean distance) is at most $O(1/\eps)$ times the cost of $T$ in $\tilde{G}$.

We recall that $(x, y) \in \tilde{G}_t$ only if $\|x-y\|_2 \le O(t/\eps)$. Therefore, if $T = \{(y_i, z_i)\}_{i=1}^{n-1}$, the cost of $T$ in $X$ is $\sum_{i=1}^{n-1} \|y_i-z_i\|$. However, if the edge $(y_i, z_i)$ had weight $t_i$, then $\|y_i-z_i\| \le O(t_i/\eps)$, so $t_i \ge \Omega(\eps) \cdot \|y_i-z_i\|$. Thus, the cost of $T$ in $\tilde{G}$ is at least $\sum_{i=1}^{n-1} \Omega(\eps) \cdot \|y_i-z_i\|$. This completes the proof.

Next, we show that the minimum spanning tree cost in $\tilde{G}$ is not much more than the Euclidean spanning tree cost.
To do so, we make use of the following two simple but important propositions.

For any edge $e$ connecting two points $p, q \in [0, \Delta]^d$ of length $w = \|p-q\|_2$, the probability that a randomly shifted grid of side length $L \le \Delta$ splits the edge (i.e., $p, q$ are not in the same cell in this grid) is at most $\frac{w \cdot \sqrt{d}}{L}$

Let $G$ be any weighted graph on a dataset $X$, with all edges having weight at most $\Delta$ and at least some sufficiently large constant.
Let $\MST(G)$ denote the weight of the minimum spanning tree of $G$. For each $t$, let $\cP_t$ represent the partition of $X$ representing the connected components of the threshold graph $G_t$ of edges with weight at most $t$.

\[\MST(G) = \Theta(1) \cdot \left(\sum_{t = 1}^\Delta (|\cP_t|-1) \cdot t\right),\]

where the sum ranges over all $1 \le t \le \Delta$ where $t$ is a power of $2$.

Let $\MST$ represent the true minimum spanning tree cost of $X$, and for any weighted graph $G$, let $\MST(G)$ represent the minimum spanning tree cost of $G$. First, we prove the following proposition.

Suppose that $\alpha^{k-1} < t \le \alpha^{k}.$ Then, $\BE[|\tilde{\cP}_{t}|] \le |\cP_t| + \MST \cdot \frac{\sqrt{d} \cdot \beta}{\alpha^{k+1}}$.

Let $L := \alpha^{k+1}/\beta$.
For each component $S \in \cP_t$, let $M_S$ represent the minimum spanning tree of $X_S$, and $\MST(S)$ represent the cost of $M_S$. Note that $\MST \ge \sum_{S \in \cP_t} \MST(S),$ by Kruskal's algorithm. Now, for each edge $e \in M_S$ of weight $w(e)$, the probability that the randomly shifted grid at level $L$ splits $e$ is at most $\frac{w(e) \cdot \sqrt{d}}{L}$, by <Ref>. This means that the expected number of edges in $M_S$ across all $S \in \cP_t$ that are cut is at most $\sum_{S \in \cP_t} \frac{\MST(S) \cdot \sqrt{d}}{L} \le \MST \cdot \frac{\sqrt{d}}{L} = \MST \cdot \frac{\sqrt{d} \cdot \beta}{\alpha^{k+1}}.$

Next, for any piece of a tree that has not been cut, all of the points in this piece will be in the same connected component in the spanner $\tilde{G}_t$. Therefore, the additional number of connected components is at most the number of cut edges, which completes the proof.

Hence, we have the following corollary.

The minimum spanning tree cost in $\tilde{G}$, in expectation, is at most $O(1) \cdot \MST(X)$.

By <Ref>, we can write $\MST(X) = \Theta(1) \cdot \left(\sum_{t} (|\cP_t|-1) \cdot t\right),$ where $t$ ranges as powers of $2$ from $1$ to $\Delta$. Likewise, $\MST(\tilde{G}) = \Theta(1) \cdot \left(\sum_{t} (|\tilde{\cP}_t|-1) \cdot t\right).$ So,

\[\BE[\MST(\tilde{G})] \le O(1) \cdot \left(\MST(X) + \sum_t t \cdot (\BE[|\tilde{\cP}_t|]-|\cP_t|)\right).\]

Using <Ref>, and the fact that $t \le \alpha^k$ in <Ref>, this is at most

\begin{align*}
O(1) \cdot \left(\MST(X) + \sum_t t \cdot \MST(X) \cdot \frac{\sqrt{d} \cdot \beta}{t \cdot \alpha}\right) &= O(1) \cdot \left(\MST(X) + \MST(X) \cdot \sum_t \frac{\sqrt{d} \cdot \beta}{\alpha}\right) \\
&= O(1) \cdot \MST(X),
\end{align*}

as long as $\alpha \ge \sqrt{d} \cdot \beta \cdot \log n$.

Hence, it suffices to find an $O(1)$-approximate MST in the graph $\tilde{G}$. This tree will have cost at most $O(1) \cdot \MST(X)$ in $\tilde{G}$ by <Ref>, so by <Ref>, it also has Euclidean cost at most $O(1/\eps) \cdot \MST(X)$. The rest of the analysis will go into showing the algorithm finds an $O(1)$-approximate MST in $\tilde{G}$.

§.§ Important Properties of Leader Compression with Early Termination

Here, we note some simple but important properties of leader compression, and some general properties of the approximate connected components we form.

Given two partitions $\cP$ and $\cQ$ on $X$, we define $\cP \oplus \cQ$ to be the finest partition $\cR$ such that $\cR \sqsubseteq \cP$ and $\cR \sqsubseteq \cQ$. Equivalently, it is the partition generated by merging a spanning forest of $\cP$ and of $\cQ$, and taking the connected components.

Given a graph $H$ on $X$, we define $\cP_H$ as the set of connected components of the graph $H$. We abuse notation and write $\cP \oplus H$ to mean $\cP \oplus \cP_H$.

First, we note the following basic proposition.

Let $\cP^{(0)}$ be a starting partition, with a graph $H$. After $h$ rounds of leader compression, let $\cP^{(h)}$ be the set of connected components. Then, $\cP^{(0)} \oplus H \sqsubseteq \cP^{(h)} \sqsubseteq \cP^{(0)}$.

Since we are only connecting connected components together, we trivially have that $\cP^{(h)} \sqsubseteq \cP^{(0)}.$ To prove that $\cP^{(0)} \oplus H \sqsubseteq \cP^{(h)}$, we first consider the case that $h = 1$. In this case, we never merge two connected components in $\cP^{(0)}$ unless they had an edge in $H$, so the proof is clear.

For general $h \ge 2$, we proceed by induction (base case $h = 1$ is already done). We know that $\cP^{(0)} \oplus H \sqsubseteq \cP^{(h-1)} \sqsubseteq \cP^{(0)}$. Since $\cP^{(h-1)} \sqsubseteq \cP^{(0)}$, this implies that $\cP^{(h-1)} \oplus H \sqsubseteq \cP^{(0)} \oplus H$. However, we also know that $\cP^{(h-1)} \sqsupseteq \cP^{(0)} \oplus H$, so this clearly implies that $\cP^{(h-1)} \oplus H \sqsupseteq \cP^{(0)} \oplus H$. So, in fact $\cP^{(h-1)} \oplus H = \cP^{(0)} \oplus H$. Therefore, by the base case, if we performing a single round of leader compression on $\cP^{(h-1)}$ to obtain $\cP^{(h)}$, we have that $\cP^{(0)} \oplus H = \cP^{(h-1)} \oplus H \sqsubseteq \cP^{(h)}$, which completes the proof.

We next note a simple proposition about $\bar{\cP}_t$.

For $t = \alpha^k$, we have that $\bar{\cP}_t \sqsupseteq \tilde{\cP}_t$.
Hence, every connected component $C \in \bar{\cP}_t$ is in a single cell at level $\alpha^{k+1}/\beta$.

Initially, $\cP_t^{(0)}$ is based on the quadtree at level $\alpha^k/\beta$, and every two points in the same cell have distance at most $\alpha^k \cdot \sqrt{d}/\beta \le t$ and are also in the same cell at level $\alpha^{k+1}/\beta$, which means they must be in the same connected component in $\tilde{\cP}_t$. Hence $\tilde{\cP}_t \sqsubseteq \cP_t^{(0)}$.
Then, we perform $h$ rounds of leader compression on $\cP_t^{(0)}$ with respect to $\tilde{G}_t$, to obtain $\bar{\cP}_t \sqsupseteq \cP_t^{(0)} \oplus \tilde{G}_t,$ by <Ref>. However, since $\tilde{\cP}_t \sqsubseteq \cP_t^{(0)}$, this means $\cP_t^{(0)} \oplus \tilde{G}_t = \cP_t^{(0)} \oplus \tilde{\cP}_t = \tilde{\cP}_t$.

Finally, for $t = \alpha^k$, $\tilde{G}_t$ never crosses a cell at level $\alpha^{k+1}/\beta$. Therefore, any component in $\bar{\cP}_t$ is contained in a single cell at level $\alpha^{k+1}/\beta$.

The following important lemma helps us understand the approximate connected components $\tilde{\cP}_t$.

For every $t$ a power of $2$, the following hold.

* If $t \le \alpha^k$, then every connected component in $\hat{\cP}_t$ is contained in the same cell at level $\alpha^{k+1}/\beta$.

* $\hat{\cP}_t \sqsubseteq \tilde{\cP}_t$.

* $\hat{\cP}_t \sqsubseteq \hat{\cP}_{t/2}.$

We shall prove these three properties in an inductive manner. In the base case, we prove the first two claims for $t = \alpha^k$, and that $\hat{\cP}_{\alpha^{k+1}} \sqsubseteq \hat{\cP}_{\alpha^k}$.
For the inductive step, we consider creating $\hat{\cP}_t$, given $\hat{\cP}_{t/\kappa}$ and $\hat{\cP}_{t \cdot \kappa}$, where $\alpha^k \le t/\kappa$ and $t \cdot \kappa \le \alpha^{k+1}$. We inductively assume that every connected component in $\hat{\cP}_{t/\kappa}$ and $\hat{\cP}_{t \cdot \kappa}$ is in a single cell at level $\alpha^{k+2}/\beta$, that $\hat{\cP}_{t/\kappa} \sqsubseteq \tilde{\cP}_{t/\kappa}$ and $\hat{\cP}_{t \cdot \kappa} \sqsubseteq \tilde{\cP}_{t \cdot \kappa}$, and finally, $\hat{\cP}_{t \cdot \kappa} \sqsubseteq \hat{\cP}_{t/\kappa}$. Then, the inductive step proves that every connected component in $\hat{\cP}_{t}$ is in a single cell at level $\alpha^{k+2}/\beta$, that $\hat{\cP}_{t} \sqsubseteq \tilde{\cP}_{t}$, and that $\hat{\cP}_{t \cdot \kappa} \sqsubseteq \hat{\cP}_t \sqsubseteq \hat{\cP}_{t/\kappa}$.

Base case: $g = 0$, i.e., $t = \alpha^k$.

Suppose that $x, y \in X$ are in the same connected component in $\tilde{G}_t$. Then, either $x, y$ are in the same component in $\bar{\cP}_t$ (and thus in $\hat{\cP}_t$), or $x, y$ are both in incomplete connected components in $\bar{\cP}_t$. Since $\bar{\cP}_t \sqsupseteq \tilde{\cP}_t$ by <Ref>, this means the leaders of $x$ and $y$ (in $\bar{\cP}_t$) are in the same connected component in $\tilde{G}_t$, which means they are in the same cell at level $\alpha^{k+1}/\beta$. So, these two components are merged, and thus $x, y$ are in the same component in $\hat{\cP}_t$. Hence, $\hat{\cP}_t \sqsubseteq \tilde{\cP}_t$.
In addition, every connected component in $\bar{\cP}_t$ is contained in a single cell at level $\alpha^{k+1}/\beta$, by <Ref>. Therefore, every connected component in $\hat{\cP}_t$ is fully contained in a single cell at level $\alpha^{k+1}/\beta$.
Finally, all points in a single cell at level $\alpha^{k+1}/\beta$ start off connected as $\cP^{(0)}_{\alpha^{k+1}}$, so this also implies that $\hat{\cP}_{\alpha^{k+1}} \sqsubseteq \hat{\cP}_{\alpha^k}$.

Inductive step:
First, we show that $\hat{\cP}_{t \cdot \kappa} \sqsubseteq \hat{\cP}_t \sqsubseteq \hat{\cP}_{t/\kappa}$. The claim that $\hat{\cP}_t \sqsubseteq \hat{\cP}_{t/\kappa}$ is immediate, because we generate $\hat{\cP}_t$ by performing leader compression on $\hat{\cP}_{t/\kappa},$ and then doing additional merging. So, we prove that $\hat{\cP}_{t \cdot \kappa} \sqsubseteq \hat{\cP}_t$.
By our inductive hypothesis, $\hat{\cP}_{t/\kappa} \sqsupseteq \hat{\cP}_{t \cdot \kappa}$. To generate $\bar{\cP}_t$, we perform rounds of leader compression on $\hat{\cP}_{t/\kappa}$ with respect to $\tilde{G}_t$. But, we know that $\tilde{\cP}_t \sqsupseteq \tilde{\cP}_{t \cdot \kappa} \sqsupseteq \hat{\cP}_{t \cdot \kappa}$ (the last part following from our inductive hypothesis), so $\bar{\cP}_t \sqsupseteq \hat{\cP}_{t \cdot \kappa}$.
Finally, we only connect components of $\bar{\cP}_t$ to form $\hat{\cP}_t$ if they are incomplete and their leaders are in the same component of $\hat{\cP}_{t \cdot \kappa}$, and since $\bar{\cP}_t \sqsupseteq \hat{\cP}_{t \cdot \kappa}$, this implies that $\hat{\cP}_t \sqsupseteq \hat{\cP}_{t \cdot \kappa},$ as desired.

Next, by the inductive hypothesis, we have that $\hat{\cP}_{t \cdot \kappa} \sqsupseteq \hat{\cP}_{\alpha^{k+1}}$, and by the base case, every connected component in $\hat{\cP}_{\alpha^{k+1}}$ is contained in a single cell at level $\alpha^{k+2}/\beta.$ Therefore, the same holds for $\hat{\cP}_{t}$, since $\hat{\cP}_{t} \sqsupseteq \hat{\cP}_{t \cdot \kappa} \sqsupseteq \hat{\cP}_{\alpha^{k+1}}$.

To finish the proof, we show that $\hat{\cP}_t \sqsubseteq \tilde{\cP}_t$. Consider any $x, y$ in the same component in $\tilde{\cP}_t$. If they are in the same component in $\bar{\cP}_t$, then they are also in the same component in $\hat{\cP}_t$. Otherwise, $x$ and $y$ are in two different incomplete components in $\bar{\cP}_t$, but are in the same connected component in $\hat{\cP}_{t \cdot \kappa}$, since $\tilde{\cP}_t \sqsupseteq \tilde{\cP}_{t \cdot \kappa} \sqsupseteq \hat{\cP}_{t \cdot \kappa}$ by the inductive hypothesis. Recall that we showed in the first paragraph of the proof that $\bar{\cP}_t \sqsupseteq \hat{\cP}_{t \cdot \kappa}$. Therefore, since $x$ and $y$ are in the same connected comonent in $\hat{\cP}_{t \cdot \kappa}$, so are the leaders of $x$ and $y$ in $\bar{\cP}_t$. Therefore, the components get merged together, so $x$ and $y$ are in the same connected component in $\hat{\cP}_t$.

Next, we prove an probabilistic result about leader compression.

Consider any partitioning $\cP^{(0)}$ of $X$, and a graph $H$. After $h$ rounds of leader compression, $\BE\left[|\cP^{(h)}| - |\cP^{(0)} \oplus H|\right] \le (3/4)^h \cdot (|\cP^{(0)}|-|\cP^{(0)} \oplus H|).$

We first prove the lemma for $h = 1$. Fix a connected component $C \in \cP^{(0)} \oplus H$, and suppose that $C$ splits into $C_1, \dots, C_r$ in $\cP^{(0)}$, for some $r \ge 1.$ If $r = 1$, then $C$ still splits into $1$ connected component in $\cP^{(1)}$, since $\cP^{(0)} \oplus H \sqsubseteq \cP^{(1)} \sqsubseteq \cP^{(0)}$. Otherwise, for every $C_j$, there must exist some $C_i$, $i \neq j$, such that there is an edge in $H$ connecting $C_i$ to $C_j$ (or else $C_j$ is not connected to the rest of $C$). Hence, with probability at least $1/4$, $C_j$ has value $0$, $C_i$ has value $1$, and there must be a message sent from some point in $C_i$ to some point in $C_j$. This means that $C_j$ will become merged to some connected component (not necessarily $C_i$) and will have a new head. Hence, if $r > 1$, the value of $r$ multiplies by at most $3/4$ in expectation after a single round of compression.

Hence, in all cases, the expectation of $r-1$ multiplies by at most $3/4$. However, $|\cP^{(0)}| - |\cP^{(0)} \oplus H|$ precisely equals the sum of $r-1$ across all connected components in $\cP^{(0)} \oplus H$ at the beginning, and $|\cP^{(1)}| - |\cP^{(0)} \oplus H|$ precisely equals the sum of $r-1$ across all connected components in $\cP^{(0)} \oplus H$ at the end. Therefore, $\BE\left[|\cP^{(1)}| - |\cP^{(0)} \oplus H|\right] \le (3/4) \cdot (|\cP^{(0)}|-|\cP^{(0)} \oplus H|).$

For general values of $h$, note that $\cP^{(0)} \oplus H = \cP^{(h-1)} \oplus H.$ Therefore, we have $\BE\left[|\cP^{(h)}| - |\cP^{(0)} \oplus H|\right] \le (3/4) \cdot (|\cP^{(h-1)}|-|\cP^{(0)} \oplus H|),$ which, after an inductive argument, completes the proof.

§.§ Part 1 of the Algorithm

In this subsection, we analyze Part 1 of the algorithm for some fixed $t = \alpha^k$.

First, we recall the following, which is immediate by combining <Ref> and <Ref>.

For every $t$ a power of $\alpha$, $\bar{\cP}_t \sqsupseteq \tilde{\cP}_t \sqsupseteq \hat{\cP}_t$.

Recall that by our algorithmic construction (Part 1), and because $\beta > \sqrt{d}$, all points in a cell at level $t/\beta$ must be in the same connected component for any of $\tilde{\cP}_t, \bar{\cP}_t, \hat{\cP}_t$.

Let $S \in \tilde{\cP}_t$ be some connected component. Then, after $h \ge 0$ rounds of leader compression using the graph $\tilde{G}_t$, the expected number of connected components that $S$ is split into is at most $1 + (|S|-1) \cdot (3/4)^h$.

Suppose that after $h \ge 0$ rounds of leader compression, the component $S$ has been partitioned into $S_1, \dots, S_r$.
After $0$ rounds of leader compression, $S$ is partitioned based on the quadtree at level $t/\beta$, so $r = |S|$.
We now see what happens after performing round $h+1$ of leader compression.

If $r = 1$, then there are no edges in $\tilde{G}_t$ that leave $S$. Otherwise, for every $S_j$, there must exist some $S_i$, $i \neq j$ such that there is an edge in $\tilde{G}_t$ connecting $S_i$ to $S_j$ (or else $S_j$ is not connected to the rest of $S$).
Hence, with probability at least $1/4$, $S_j$ has value T, $S_i$ has value H, and $x_j$ sends a message to $x_i$. This means that $T_i$ and $T_j$ merge in this round, or $T_j$ merges with some other $T_i$ based on another edge contained in $\tilde{G}_t$). Hence, if $r > 1,$ the value of $r$ multiplies by at most $3/4$ in expectation after an additional round of compression.

Hence, if $r_h$ is the number of connected components after $h$ rounds of compression, $\BE[r_{h+1}|r_h] \le \frac{3}{4} \cdot r_h$ for $r_h > 1$, and $r_{h+1} = 1$ if $r_h = 1$. We can summarize this as $\BE[r_{h+1}-1] \le \frac{3}{4} \cdot (\BE[r_h]-1)$. So, after $h$ rounds of leader compression, the expected number of components is at most $1 + (|S|-1) \cdot (3/4)^h$.

For some fixed $t = \alpha^k$, let $\cP_t^{(h)}$ be the partitioning after $h$ rounds of leader compression on $\cP_t^{(0)}$ with respect to $\tilde{G}_t$.
Then, the expected number of incomplete connected components in $\bar{\cP}_t$ is at most $(3/4)^h \cdot \alpha \cdot \frac{\MST(\tilde{G})}{t}.$

First, note that $\cP_t^{(0)} \oplus \tilde{G}_t = \tilde{\cP}_t$, since $\cP_t^{(0)} \sqsupseteq \tilde{\cP}_t$. Therefore, by <Ref>, $\BE[|\cP_t^{(h)}| - |\tilde{\cP}_t|] \le (3/4)^h \cdot (|\cP_t^{(0)}|-|\tilde{\cP}_t|) \le (3/4)^h \cdot (|\cP_t^{(0)}|-1)$. Next, note that $|\cP_t^{(0)}|$ equals the number of distinct nonempty cells in the quadtree $Q$ at side length $t/\beta$. Any points in distinct cells can only be connected by an edge in the spanner of length at least $2 \alpha^{k-1}$. Hence, $\MST(\tilde{G}) \ge 2 \alpha^{k-1} \cdot (|\cP_t^{(0)}|-1),$ which means that $|\cP_t^{(0)}|-1 \le \frac{\MST(\tilde{G})}{2 \alpha^{k-1}}$. Hence, $\BE[|\cP_t^{(h)}| - |\tilde{\cP}_t|] \le (3/4)^h \cdot \frac{\MST(\tilde{G})}{2 \alpha^{k-1}} = (3/4)^h \cdot \alpha \cdot \frac{\MST(\tilde{G})}{2t}$.

Next, we note that the number of incomplete connected components in $\cP_t^{(h)}$ is at most $2 \cdot (|\cP_t^{(h)}| - |\tilde{\cP}_t|)$. To see why, if any connected component $C \in \tilde{\cP}_t$ is split into $r_C$ connected components in $\cP_t^{(h)}$, then $|\cP_t^{(h)}| - |\tilde{\cP}_t| = \sum_{C \in \tilde{\cP}_t} (r_C-1)$, but the number of incomplete connected components is $\sum_{C \in \tilde{\cP}_t} r_C \cdot \textbf{1}(r_C \ge 2)$. Since $2(r_C-1) \ge r_C$ whenever $r_C \ge 2$, this means that $2 \cdot (|\cP_t^{(h)}| - |\tilde{\cP}_t|)$ is at least the number of incomplete connected components. Hence, the expected number of incomplete connected components is at most $(3/4)^h \cdot \alpha \cdot \frac{\MST(\tilde{G})}{t}.$

Consider some component $S \in \tilde{\cP}_t$. Let $Z$ represent the random variable representing how many connected components remain after $h$ rounds of leader compression. Then, the number of incomplete connected components is $0$ if $Z = 1$, and $Z$ if $Z \ge 2$. Importantly, the number of incomplete connected components is at most $2 \cdot (Z-1)$. So, the expected number of incomplete connected components is at most $2 \cdot (\BE[Z]-1)$. However, by <Ref>, $\BE[Z] \le 1 + (|S|-1) \cdot (3/4)^h$. Therefore, the expected number of incomplete connected components coming from $S$ is at most $2 \cdot (|S|-1) \cdot (3/4)^h$.

Adding over all $S \in \tilde{\cP}_t$, the expected number of incomplete connected components is at most $2 \cdot (3/4)^h \cdot \sum_{S \in \tilde{\cP}_t} (|S|-1)$. Note that $\sum_{S \in \tilde{\cP}_t} |S|$ equals the number of nonempty cells at level $t/\beta$ in $\tilde{\cP}_t$, because all points in any such cell are connected in $\tilde{\cP}_t$.
So, calling this value $M_t$, the expected number of incomplete connected components is at most $2 \cdot (3/4)^h \cdot (M_t-1)$.
However, in $\tilde{G}$, any edges connecting points in distinct cells at level $t/\beta$ have cost at least $t/\beta$, which means that $\MST(\tilde{G}) \ge (t/\beta) \cdot (M_t-1)$. Thus, the expected number of incomplete connected components in $\tilde{\cP}_t$ is at most $2 \cdot (3/4)^h \cdot \frac{\beta}{t} \cdot \MST(\tilde{G})$.

Hence, the following holds.

For some fixed $t = \alpha^k$, $\BE[|\tilde{\cP}_t|-|\hat{\cP}_t|] \le (3/4)^h \cdot \frac{\alpha}{t} \cdot \MST(\tilde{G})$.

By <Ref>, we have that $|\tilde{\cP}_t| - |\hat{\cP}_t| \le |\bar{\cP}_t| - |\hat{\cP}_t|$. However, to form $\hat{\cP}_t$ from $\bar{\cP}_t$, we only merge incomplete connected components together. So, $|\bar{\cP}_t| - |\hat{\cP}_t|$ is at most the number of incomplete connected components, minus $1$. Hence, by <Ref>, the expectation is at most $(3/4)^h \cdot \frac{\alpha}{t} \cdot \MST(\tilde{G}).$

§.§ Part 2 of the Algorithm

In this section, we consider constructing $\hat{\cP}_t$ where $\alpha^{k} < t < \alpha^{k+1}$.

Let $\cP$ be any partition, and $\cP_1, \cP_2 \sqsubseteq \cP$ be coarser partitions. Then, $|\cP|+|\cP_1 \oplus \cP_2| \ge |\cP_1|+|\cP_2|$.

Let $M = |\cP|$. Consider graphs on $[M]$, where each vertex represents a partition in $\cP$. Let $G_1$ be the spanning forest on $[M]$ that generates the partition $\cP_1$ (via the connected components of $G_1$) and $G_2$ be the graph that generates the partition $\cP_2$ on $[M]$. Then, $G_1 \cup G_2$ generates the partition $\cP_1 \oplus \cP_2$. Since $G_1, G_2$ are forests, the number of edges $|G_1|, |G_2|$ equal $M - |\cP_1|, M - |\cP_2|$, respectively. Hence, $|G_1 \cup G_2| \le 2M - |\cP_1|-|\cP_2|$. The number of connected components in $G_1 \cup G_2$ is at least $M - |G_1 \cup G_2|$, with equality if and only if $G_1 \cup G_2$ is also a forest. Therefore, $|\cP_1 \oplus \cP_2| \ge M - (2M - |\cP_1|-|\cP_2|) = |\cP_1|+|\cP_2| - M,$ which completes the proof.

Define $T := |\tilde{\cP}_{t/\kappa}| - |\hat{\cP}_{t/\kappa}|$.
Since $\tilde{\cP}_t, \hat{\cP}_{t/\kappa} \sqsubseteq \tilde{\cP}_{t/\kappa}$ by <Ref>, we have the following corollary.

We have that $|\tilde{\cP}_t| - |\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t| \le T$.

We recall that $\tilde{\cP}_t \sqsupseteq \hat{\cP}_t$.
The rest of this section is devoted to bouding

which generalizes <Ref> to $t$ not necessarily a power of $\alpha$.

Next, we bound the number of incomplete connected components, similar to <Ref>.

For some fixed $\alpha^k < t < \alpha^{k+1}$, the expected number of incomplete connected components in $\bar{\cP}_t$ is at most $(3/4)^h \cdot \frac{\alpha^2}{t} \cdot \MST(\tilde{G})$.

Define $\cP_t^{(0)} := \hat{\cP}_{t/\kappa}$ as the starting partition before leader compression. Let $\cP_t^{(h)}$ be the partition after performing $h$ rounds of leader compression on $\cP_t^{(0)}$ with respect to $\tilde{G}_t$. By <Ref>, we know that $\BE\left[|\cP_t^{(h)}| - |\cP_t^{(0)} \oplus \tilde{\cP}_t| \big\vert \cP_t^{(0)} \right] \le (3/4)^h \cdot \left(|\cP_t^{(0)}| - |\cP_t^{(0)} \oplus \tilde{\cP}_t|\right)$. Since $\cP_t^{(0)} = \hat{\cP}_{t/\kappa},$ this means that

\[\BE\left[|\cP_t^{(h)}| - |\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t| \big\vert \hat{\cP}_{t/\kappa} \right] \le (3/4)^h \cdot \left(|\hat{\cP}_{t/\kappa}| - |\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t|\right).\]

By Part 3 of <Ref>, know that $\hat{\cP}_{t/\kappa} \sqsubseteq \hat{\cP}_{\alpha^k}$, so we can bound $|\hat{\cP}_{t/\kappa}|$ as at most the number of nonempty cells at level $\alpha^k/\beta$.
Moreover, $|\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t| \ge 1$, which means that $|\hat{\cP}_{t/\kappa}| - |\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t|$ is at most the number of nonempty cells at level $\alpha^k/\beta$ minus $1$, which as we saw in <Ref> is at most $\frac{\MST(\tilde{G})}{2 \alpha^{k-1}} \le \alpha^2 \cdot \frac{\MST(\tilde{G})}{2t},$ because $t \le \alpha^{k+1}$. So, by removing the conditioning on $\hat{\cP}_{t/\kappa}$, we have that $\BE\left[|\cP_t^{(h)}| - |\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t|\right] \le (3/4)^h \cdot \alpha^2 \cdot \frac{\MST(\tilde{G})}{2t}.$

Next, recall that $\cP_t^{(h)} \sqsupseteq \hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t$, and every incomplete connected component in $\cP_t^{(h)}$ has an edge leaving it in $\tilde{G}_t$.
So, if any component $C \in \hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t$ is split into $r_C$ connected components in $\cP_t^{(h)}$, then $|\cP_t^{(h)}| - |\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t| = \sum_{C \in \hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t} (r_C-1)$, but the number of incomplete connected components is $\sum_{C \in \hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t} r_C \cdot \textbf{1}(r_C \ge 2)$. Since $2(r_C-1) \ge r_C$ whenever $r_C \ge 2$, this means that

the number of incomplete connected components is at most $2 \cdot (|\cP_t^{(h)}| - |\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t|).$ Hence, the expected number of incomplete connected components is at most $(3/4)^h \cdot \alpha^2 \cdot \frac{\MST(\tilde{G})}{t}$.

We next show that $|\tilde{\cP}_t| - |\hat{\cP}_t|$ is small, in expectation.

Suppose $t$ is a power of $2$ with $\alpha^k < t < \alpha^{k+1}$, and let $\kappa = 2^{2^{v_2(\log_2 t)}}$. Then, $\BE\left[|\tilde{\cP}_t| - |\hat{\cP}_t|\right] \le \BE\left[|\tilde{\cP}_{t/\kappa}| - |\hat{\cP}_{t/\kappa}|\right] + (3/4)^h \cdot \frac{\alpha^2}{t} \cdot \MST(\tilde{G})$.

Since we only merge incomplete connected components together to go from $\bar{\cP}_t = \cP_t^{(h)}$ to $\hat{\cP}_t$, we know that

\begin{equation} \label{eq:b1}
\BE[|\cP_t^{(h)}| - |\hat{\cP}_t|] \le (3/4)^h \cdot \frac{\alpha^2}{t} \cdot \MST(\tilde{G}),
\end{equation}

by <Ref>.

\begin{equation} \label{eq:b2}
\BE[|\tilde{\cP}_t| - |\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t|] \le \BE[|\tilde{\cP}_{t/\kappa}| - |\hat{\cP}_{t/\kappa}|],
\end{equation}

by <Ref>.
Finally, $\cP_t^{(h)} \sqsupseteq \hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t,$ by <Ref>. Therefore,

\begin{equation} \label{eq:b3}
\BE[|\hat{\cP}_{t/\kappa} \oplus \tilde{\cP}_t| - |\cP_t^{(h)}|] \le 0.
\end{equation}

Adding Equations (<ref>), (<ref>), and (<ref>) together completes the proof.

By a simple inductive argument, we have $|\tilde{\cP}_t| - |\hat{\cP}_t|$ is small in expectation. Specifically, we have the following corollary.

For any $t$ a power of $2$, $\hat{\cP}_t \sqsubseteq \tilde{\cP}_t$, and $\BE\left[|\tilde{\cP}_t| - |\hat{\cP}_t|\right] \le (3/4)^h \cdot \frac{\alpha^3}{t} \cdot \MST(\tilde{G})$.

Suppose $\alpha^k \le t < \alpha^{k+1}$. We can construct a sequence $t = t_0 > \cdots > t_r = \alpha^k$, where $t_{i+1} = t_i/2^{2^{v_2(\log_2 t_i)}}$. Then, we can form a telescoping sum

\begin{align*}
\BE\left[|\tilde{\cP}_t| - |\hat{\cP}_t|\right] &= \BE\left[|\tilde{\cP}_{t_r}| - |\hat{\cP}_{t_r}|\right] + \sum_{i = 0}^{r-1} \left(\BE\left[|\tilde{\cP}_{t_i}| - |\hat{\cP}_{t_i}|\right] - \BE\left[|\tilde{\cP}_{t_{i+1}}| - |\hat{\cP}_{t_{i+1}}|\right]\right).
\intertext{Using \Cref{cor:overcomplete-bound} and \Cref{lem:overcomplete-bound-part-2}, this is at most}
&\le \left(\frac{3}{4}\right)^h \cdot \frac{\alpha}{t_r} \cdot \MST(\tilde{G}) + \sum_{i = 0}^{r-1} \left(\frac{3}{4}\right)^h \cdot \frac{\alpha^2}{t_i} \cdot \MST(\tilde{G}) \\
&\le \left(\frac{3}{4}\right)^h \cdot \alpha^2 \cdot \MST(\tilde{G}) \cdot \sum_{i=0}^r \frac{1}{t_i} \\
&\le \left(\frac{3}{4}\right)^h \cdot \alpha^2 \cdot \MST(\tilde{G}) \cdot \left(\frac{1}{t} + \frac{2}{t} + \frac{4}{t} + \cdots + \frac{1}{\alpha^k}\right) \\
&\le \left(\frac{3}{4}\right)^h \cdot \alpha^2 \cdot \MST(\tilde{G}) \cdot \frac{2}{\alpha^k} \\
&\le \left(\frac{3}{4}\right)^h \cdot \frac{\alpha^3}{t} \cdot \MST(\tilde{G}),
\end{align*}

since $t \le \alpha^{k+1}/2$ so $\frac{2}{\alpha^k} \le \frac{\alpha}{t}$.

§.§ Part 3 of the Algorithm

From <Ref>, we have generated a nested set of partitions $\hat{\cP}_1 \sqsupseteq \hat{\cP}_2 \sqsupseteq \hat{\cP}_4 \sqsupseteq \cdots$. In Part 3, we generate the edges: we must show that the cost of the edges we produce is at most $O(1) \cdot \MST(\tilde{G})$, and that the edges we produce generate a spanning tree.

When connecting $\hat{\cP}_{t/2}$ into $\hat{\cP}_t$, we generate a new partition ${\cP_t'}^{(h)}$ after $h$ rounds of leader compression on $\hat{\cP}_{t/2}$ with respect to $\tilde{G}_t$. First, we note that ${\cP_t'}^{(h)}$ still refines $\hat{\cP}_t$.

We have ${\cP_t'}^{(h)} \sqsupseteq \hat{\cP}_t$.

By <Ref>, ${\cP_t'}^{(h)} \sqsupseteq \hat{\cP}_{t/2} \oplus \tilde{\cP}_t$. Moreover, by <Ref>, $\hat{\cP}_{t/2} \sqsupseteq \hat{\cP}_t$ and $\tilde{\cP}_{t} \sqsupseteq \hat{\cP}_t$, which means that $\hat{\cP}_{t/2} \oplus \tilde{\cP}_t \sqsupseteq \hat{\cP}_t$. In summary, ${\cP_t'}^{(h)} \sqsupseteq \hat{\cP}_{t/2} \oplus \tilde{\cP}_t \sqsupseteq \hat{\cP}_t$.

Let $\hat{G}_t$ represent the edges generated when connecting $\hat{\cP}_{t/2}$ into $\hat{\cP}_t$ (and $\hat{G}_1 = \emptyset$).

$\bigcup_{t' \le \alpha^H} \hat{G}_{t'}$ is a spanning tree of $X$.

We prove inductively that $\bigcup_{t' \le t} \hat{G}_{t'}$ forms a spanning forest for $\hat{\cP}_t$.

For the base case $t = 1$,

recall that we assume the minimum distance between any two points in $X$ is at least $\alpha^{100}$, which means by Part 1 of <Ref>, every connected component in $\hat{\cP}_1$ consists of a single element. Since $\hat{G}_1$ has no edges, the base case follows.

Define $\hat{G}_{\le t} := \bigcup_{t' \le t} \hat{G}_{t'}$. For the inductive step, assume that $\hat{G}_{\le t/2}$ generates a spanning forest for $\hat{\cP}_{t/2}$. Then, leader compression only adds edges to connect two distinct connected components together, so when adding the edges generated by $h$ rounds of leader compression on $\hat{\cP}_{t/2}$ with respect to $\tilde{G}_t$, we obtain a spanning forest for ${\cP_t'}^{(h)}$, where ${\cP_t'}^{(h)} \sqsupseteq \hat{\cP}_t$ by <Ref>. Finally, we connect all disconnected components in each partition of $\hat{\cP}_t$, which generates a spanning forest for $\hat{\cP}_t$.

Due to Part 2 of <Ref>, $\hat{\cP}_t$ refines $\tilde{\cP}_t$.
Since $\tilde{\cP}_t$ contains only one part $X$ for $t=\alpha^H$, $\bigcup_{t' \le \alpha^H} \hat{G}_{t'}$ is a spanning tree of $X$.

Now, we fix a value $t$, and consider the edges generated to connect $\hat{\cP}_{t/2}$ into $\hat{\cP}_t$. We will bound the sum of the weights of these edges.

The sum of the weights of all edges in $\hat{G}_t$, in expectation, is at most $t \cdot \left(|\tilde{\cP}_{t/2}| - |\tilde{\cP}_t|\right) + (3/4)^h \cdot \left(\alpha^3 + \frac{2 \alpha^4 \sqrt{d}}{\beta}\right) \cdot \MST(\tilde{G}).$

By <Ref>, we have $\hat{\cP}_{t/2} \oplus \tilde{\cP}_t \sqsubseteq {\cP_t'}^{(h)} \sqsubseteq \hat{\cP}_{t/2},$ and by <Ref>, $\BE\left[|{\cP_t'}^{(h)}| - |\hat{\cP}_{t/2} \oplus \tilde{\cP}_t|\right] \le (3/4)^h \cdot \left(|\hat{\cP}_{t/2}| - |\hat{\cP}_{t/2} \oplus \tilde{\cP}_t|\right)$.

As in <Ref>,

we know that
$|\hat{\cP}_{t/2}| - |\hat{\cP}_{t/2} \oplus \tilde{\cP}_t| \le \alpha^2 \cdot \frac{\MST(\tilde{G})}{t},$ so $\BE\left[|{\cP_t'}^{(h)}| - |\hat{\cP}_{t/2} \oplus \tilde{\cP}_t|\right] \le (3/4)^h \cdot \alpha^2 \cdot \frac{\MST(\tilde{G})}{t}.$ In addition, $|\hat{\cP}_{t/2} \oplus \tilde{\cP}_t| - |\tilde{\cP}_t| \le 0$, and $\BE\left[|\tilde{\cP}_t| - |\hat{\cP}_t|\right] \le (3/4)^h \cdot \frac{\alpha^3}{t} \cdot \MST(\tilde{G})$ by <Ref>. So, $\BE\left[|{\cP_t'}^{(h)}| - |\hat{\cP}_t|\right] \le (3/4)^h \cdot \frac{2 \alpha^3}{t} \cdot \MST(\tilde{G})$.

Assume $\alpha^k \le t < \alpha^{k+1}$.
At level $t$, we produce $|\hat{\cP}_{t/2}| - |{\cP_t'}^{(h)}|$ edges of weight $t$, and then $|{\cP_t'}^{(h)}| - |\hat{\cP}_t|$ edges to combine all of $\hat{\cP}_t$ together. But by Part 1 of <Ref>, the diameter of any cell in $\hat{\cP}_t$ is at most $\alpha^{k+1} \cdot \sqrt{d}/\beta,$ so the total weight of all the edges, in expectation, is at most

\begin{align*}
t \cdot \BE\left[|\hat{\cP}_{t/2}| - |{\cP_t'}^{(h)}|\right] + \frac{\alpha^{k+1} \sqrt{d}}{\beta} \cdot \BE\left[|{\cP_t'}^{(h)}| - |\hat{\cP}_t|\right]
&\le t \cdot \BE\left[|\hat{\cP}_{t/2}| - |{\cP_t'}^{(h)}|\right] + \frac{\alpha^{k+1} \sqrt{d}}{\beta} \cdot \left(\frac{3}{4}\right)^h \cdot \frac{2 \alpha^3}{t} \cdot \MST(\tilde{G}) \\
&\le t \cdot \BE\left[|\hat{\cP}_{t/2}| - |{\cP_t'}^{(h)}|\right] + \frac{2 \alpha^{4} \sqrt{d}}{\beta} \cdot \left(\frac{3}{4}\right)^h \cdot \MST(\tilde{G}) \\
&\le t \cdot \BE\left[|\tilde{\cP}_{t/2}| - |\hat{\cP}_t|\right] + \frac{2 \alpha^{4} \sqrt{d}}{\beta} \cdot \left(\frac{3}{4}\right)^h \cdot \MST(\tilde{G}).
\end{align*}

Moreover, $\BE[|\tilde{\cP}_t| - |\hat{\cP}_t|] \le (3/4)^h \cdot \frac{\alpha^3}{t} \cdot \MST(\tilde{G})$ by <Ref>, so $\BE[|\tilde{\cP}_{t/2}| - |\hat{\cP}_t|] \le |\tilde{\cP}_{t/2}| - |\tilde{\cP}_t| + (3/4)^h \cdot \frac{\alpha^3}{t} \cdot \MST(\tilde{G})$. So overall, the weight of the edges we added, in expectation is at most

\[t \cdot \left(|\tilde{\cP}_{t/2}| - |\tilde{\cP}_t|\right) + (3/4)^h \cdot \left(\alpha^3 + \frac{2 \alpha^4 \sqrt{d}}{\beta}\right) \cdot \MST(\tilde{G}). \qedhere\]

Adding this over all levels $t$, we get this is at most $\MST(\tilde{G}) + (3/4)^h \cdot \log n \cdot \left(\alpha^3 + \frac{2 \alpha^4 \sqrt{d}}{\beta}\right) \cdot \MST(\tilde{G})$. So, we just need $h = O(\log \log n)$.

If $h$ is a sufficiently large $\Theta(\log\log n)$, $\bigcup_{t' \le \alpha^H} \hat{G}_{t'}$ is an $O(1)$-approximate $\MST$ for $X$ in expecation.

According to Lemma <ref>, the expected total weights of $\bigcup_{t' \le \alpha^H} \hat{G}_{t'}$ is at most

\begin{align*}
\MST(\tilde{G}) + (3/4)^h \cdot \log n \cdot \left(\alpha^3 + \frac{2 \alpha^4 \sqrt{d}}{\beta}\right) \cdot \MST(\tilde{G}) = O(1)\cdot \MST(\tilde{G}).
\end{align*}

According to Corollary <ref> and Proposition <ref>, $\bigcup_{t' \le \alpha^H} \hat{G}_{t'}$ is a $O(1)$-approximate MST for $X$ in expectation.

§ EUCLIDEAN MST IN THE MPC MODEL

In this section, we describe how to implement our algorithms in the Massively Parallel Computation (MPC) model.
In Section <ref>, we briefly introduce some useful exsiting algorithmic primitives in the MPC model.
In Section <ref>, we show the detailed implementation of our Euclidean MST algorithm in the MPC model.

§.§ Existing Algorithmic Primitives in the MPC model

One of the most basic MPC algorithmic primitive is sorting.

Given size $N$ input data where each data item has size at most $N^{o(1)}$, there is a fully scalable MPC algorithm to sort and index (rank) these data items in $O(1)$ rounds and using $O(N)$ total space.

Sorting can be used to build other MPC subroutines.
One important use case of sorting is to simulate a PRAM algorithm in the MPC model.
The PRAM model is a classic model of parallel computation.
Roughly speaking, there is a shared memory and multiple processors in the PRAM model.
The computation proceeds in rounds, and each processor does at most one algorithmic operation in one round.
In addition, processors can simutaneously read and write the shared memory cells in a round.
The efficiency of a PRAM algorithm is measured by depth (longest chain of dependencies of the computation) and work (total running time over processors).
A CRCW (Concurrent Read Concurrent Write) PRAM algorithm means that processors can simutaneously read and write the same shared memory cell in a round.
It was shown that any PRAM algorithm can be simulated in the MPC model (see e.g. [32, 6]).
We refer readers to Appendix E of [6] for detailed implementations.
We formally state the gaurantees of the simulation as the following.

Given a CRCW PRAM algorithm with $O(D)$ depth and $O(W)$ work, it can be simulated by a fully scalable MPC algorithm with $O(D)$ rounds and $O(W)$ space.

One application of Theorem <ref> is the following simultaneous access problem: several arrays with total size $O(m)$ are stored distributedly on the machines, and $p$ machines want to simultaneously access some entries of these arrays where each machine has $s$ non-adaptive queries.
This operation can be done in $O(1)$ rounds and total space $O(m+p\cdot s)$, and it is fully scalable.
One application of simultaneous access is duplicating and broadcasting a small size message.

Given a data item with size $N^{o(1)}$ where $N$ is the target output size, there is a fully scalable MPC algorithm[Here the “fully scalable” means that the algorithm works for local memory size $N^{\delta}$ for any constant $\delta > 0$.] uses $O(1)$ rounds and $O(N)$ space that duplicates the data item such that the total size over all duplications is $N$.

Another important application of sorting is to duplicate the input data small number of times and rearange them.
This allows us to run multiple tasks which requires the same input data in parallel.

Given size $N$ input data and a parameter $m=N^{o(1)}$, there is a fully scalable algorithm which duplicates the input data $m$ times.
The algorithm takes $O(1)$ rounds and $O(N\cdot m)$ total space.

The following theorem gives a subroutine of applying dimensionality reduction efficiently in the MPC model.
Note that each input data point is not necessarily small enough to fit into the memory of a single machine and the entries of each data point can distributed arbitrarily over machines.

Given a set of points $x_1,x_2,\cdots,x_n\in\mathbb{R}^d$ whose entries are distributed arbitrarily over the machines in the MPC model, there is a fully scalable MPC algorithm which outputs $x_1',x_2',\cdots,x_n'\in\mathbb{R}^{d'}$ where $d'= O(\log n)$ and with probability at least $1-1/\poly(n)$, $\forall i,j\in[n],0.99 \|x_i-x_j\|_2^2\leq \|x'_i-x'_j\|_2^2\leq 1.01 \|x_i-x_j\|_2^2$.
In addition, $\forall i\in[n],x'_i$ is held entirely by a single machine.
The algorithm takes $O(1)$ rounds, and the total space needed is $O(nd + n\log^3 n)$.

The following theorem states that there is an efficient MPC algorithm which computes a constant approximate Euclidean spanner.
Note that a graph can be represented by a set of edges, and we store the edges in an arbitrarily distributed way over machines in the MPC model.

Given parameters $C>1, t>0$ and a set of points $X=\{x_1,x_2,\cdots,x_n\}\subset \mathbb{R}^d$ distributed arbitrarily on several machines in the MPC model with $d=O(\log n)$, there is a fully scalable MPC algorithm which outputs a graph $G=(X, E)$ such that with probability at least $1-1/\poly(n)$:

* For any $x, y \in X$, if there is an edge in $G$ between $x$ and $y$, $\|x-y\|_2\leq C\cdot t$.

* For any $x, y \in X$ with $\|x-y\|_2\leq t$, there is a path in $G$ connecting $x, y$ using at most $2$ edges.

In addition, $G$ has at most $n^{1+1/C^2+o(1)}$ number of edges.
The algorithm uses $O(1)$ rounds and needs total space $n^{1+1/C^2+o(1)}$.

Another algorithmic primitive in the MPC model is to find predecessors.
In particular, given pairs $(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$ where $x_i$ have a total ordering and $y_i\in \{0,1\}$.
The total size of all pairs is $N$ and each $x_i$ has size $N^{o(1)}$.
The goal is to output $(x_1,i_1),(x_2,i_2),\cdots,(x_n,i_n)$ where $\forall j\in [n], i_j$ satisfies that (1) $y_{i_j}=1$, (2) $x_{i_j}$ is the largest one such that $x_{i_j}\leq x_j$.

There is a fully scalable MPC algorithm that solves the predecessor problem in $O(1)$ rounds and $O(N)$ total space.

We also state an MPC algorithmic primitive to index elements in sets.

Given sets $S_1,S_2,\cdots,S_k$ of items with total size $N$, there is a fully scalable MPC algorithm which runs in $O(1)$ rounds and uses total space $O(N)$ to output the size of each set $S_i$, and for each $x\in S_i$, outputs its ranking / index within the set $S_i$.

Similarly, the above primitive can be easily extended to compute a prefix sum for each element in each set.

Given sets $S_1,S_2,\cdots,S_k$ of ranked items with total size $N$, where each item has a weight, there is a fully scalable MPC algorithm which runs in $O(1)$ rounds and uses total space $O(N)$ to output a prefix sum $\sum_{j\in S_l:\text{item }j\text{ has smaller rank than item }i} (\text{weight of }j)$ for each item $i\in S_l$ for each $S_l,l\in[k]$.

§.§ Implementation of Euclidean MST in the MPC Model

In this section, we provide details of the MPC implementation of our Euclidean MST algorithm.

Given $n$ points from $\mathbb{R}^d$, there is a fully scalable MPC algorithm which outputs an $O(1)$-approximate MST with probability at least $0.99$.
The number of rounds of the algorithm is $O(\log\log(n)\cdot \log\log\log(n))$.
The total space required is at most $O(nd+n^{1+\varepsilon})$ where $\varepsilon>0$ is an arbitrary small constant.

The approximation gaurantee is shown by Lemma <ref> in Section <ref>.
In the remaining of the proof, we show how to implement the algorithm described in Section <ref> in the MPC model.

We firstly need to run dimensionality reduction.
By applying the algorithm mentioned in Theorem <ref>, we are able to reduce the dimension of each point to $d'=\Theta(\log n)$ while preserve all pairwise distances up to a constant factor with probability at least $0.999$.
This step requires $O(1)$ rounds and $O(nd+n\log^3n)$ total space.
In addition, the algorithm is fully scalable.
Then we can use sorting (Theorem <ref>) to sort all values in each dimension separtely and parallelly to learn the maximum and the minimum values in each dimension.
Then according to Theorem <ref>, we are able to use $O(1)$ rounds to make every machine learn the maximum and the minimum value of each dimension.
Thus, we are able to shift the point set such that the minimum value in each dimension is $0$.
Note that base on the maximum value and minimum value of each coordinate, we can verify whether all points are at the same location.
If all points are at the same location, the MST cost is $0$ and we can output an arbitrary spanning tree.
Otherwise we linearly scale the entire dataset such that the maximum value of the point set $\Delta = \Theta(n^2/\log n)$.

Next, we need to build the randomly shifted grid and round the coordinates of each point.
To do this, we let one machine generate a randomly shifted vector $(a_1,a_2,\cdots,a_{d'})\in \mathbb{R}^{d'}$ where each coordinate is drawn uniformly from $[0,\Delta)$ (this is the same vector as described in Section <ref>).
Since $d'=\Theta(\log n)$, we apply Theorem <ref> again, we can use $O(1)$ rounds to make every machine learns $(a_1,a_2,\cdots,a_{d'})$.
Therefore, all machines agree on the same randomly shifted grid.
Each machine checks each point stored in its memory, and moves the point to the closest center of a cell at level $t=\alpha^{100}$.
Note that each movement might change the cost of MST by $\sqrt{d'}\cdot \alpha^{100}=\polylog n$, and because we have $n$ points, the total change will be at most $n\polylog n$.
However, since the MST cost is at least the maximum distance which is at least $\Delta = \Theta(n^2/\log n)$, the MST cost is changed by at most a constant factor by above movements.
After doing above steps, our point set satifies that the maximum distance is at most $n^2$ and the minimum distance is at least $\alpha^{100}$ which are the same as mentioned in Section <ref>.

Now we describe how to generate $\tilde{G}_t$ for $t=1,2,4,\cdots,\alpha^H$.
Firstly, we apply Theorem <ref> to duplicate input data $\log(\alpha^H)$ times.
This step is fully scalable and takes $O(1)$ rounds and $O(n\log n)\cdot \log(\alpha^H)$ total space.
Since we duplicated the input data, we can handle each $t=1,2,4,\cdots,\alpha^H$ in parallel.
Consider a fixed $t$ and let $k$ be such $\alpha^{k-1}<t\leq \alpha^k$.
As discussed above, all machines agree on the same randomly shifted grid, thus each cell at level $\alpha^{k+1}/\beta$ can be uniquely determined by a vector in $\mathbb{Z}^{d'}$ (see the discussion in Section <ref>).
Let $c(x)$ be the cell at level $\alpha^{k+1}/\beta$ containing $x$.
We create $(c(x),x)$ for each point $x$.
These steps only require local computations.
Let $\varepsilon>0$ be an arbitray constant.
Then we sort all $(c(x),x)$ (Theorem <ref>) but we restrict that each machine only uses memory $\Theta(s^{1/(1+\varepsilon/2)})$ where $s$ is the local memory size of each machine.
The algorithm is fully scalable, takes $O(1)$ rounds and $O(n^{1+\varepsilon/2}\log n)$ total space.
Then the points $X_c$ in the same cell $c$ are rearranged into consecutive machines.
We set $C$ used in Theorem <ref> to be $\xi/\sqrt{\varepsilon}$ where $\xi\geq 1$ is a sufficiently large constant.
If $X_c$ is entirely contained by a single machine, then $\tilde{G}'_t(X_c)$ can be computed locally and with probability at least $1-1/\poly(n)$,

* For any $p,q\in X_c$, if there is an edge in $\tilde{G}'_t(X_c)$ between $p$ and $q$, $\|p-q\|_2\leq C\cdot t$.

* For any $p,q\in X_c$ with $\|p-q\|_2\leq t$, there is a path in $\tilde{G}'_t(X_c)$ connecting $p,q$ using at most $2$ edges.

Since $\tilde{G}'_t(X_c)$ only has $O(|X_c|^{1+\varepsilon/2})$ edges, $\tilde{G}'_t(X_c)$ can still be stored locally (note each machine only consumes $s^{1+\varepsilon/2}$ space during the sorting).
Otherwise, if $X_c$ is distributed over multiple machines, then only the first machine containing points from $X_c$ and the last machine containing points from $X_c$ might contain points that are not in $X_c$.
Then there are two cases:
(1) If $X_c$ is only on two consecutive machines, we can send them into an arbitrary machine and handle them locally as discussed above.
(2) If $X_c$ is on more than two consecutive machines, the first machine containing points in $X_c$ can move them to the second machine containing points in $X_c$, and the last machine containing points in $X_c$ can move them to the second to the last machine that contains points in $X_c$.
By applying the predecessor algorithm (Theorem <ref>), if a machine holds points in $X_c$, it learns the first machine contains points in $X_c$ as well as the last machine that contains points in $X_c$.
Finding predecessor processor requires $O(1)$ rounds and $O(n\log n)$ space, and it is fully scalable in the MPC model.
Then we are able to apply Theorem <ref> for each $X_c$ in parallel.
Therefore, we obtain graphs $\tilde{G}'_t(X_c)$ for all $X_c$ in $O(1)$ rounds and the total space required is $O(n^{1+\varepsilon/2})$.
This step is also fully scalable.
In addition, with probability at least $1-1/\poly(n)$, for every $X_c$, $G'_t(X_c)$ satisfies the properties mentioned in Theorem <ref> with respect to $X_c$.
Then we let $G'_t$ be the union of all $G'_t(X_c)$.
This step can be done by only local computation, i.e., renaming the graph.

Then, we duplicate $\tilde{G}'_1,\tilde{G}'_2,\tilde{G}'_4,\cdots, \tilde{G}'_{\alpha^H}$ $\log(\alpha^H)$ times.
According to Theorem <ref>, this is fully scalable and only takes $O(1)$ rounds and $O(n^{1+\varepsilon/2}\log n)$ total space.
For each edge of the $i$-th copy of $\tilde{G}'_t$, if $t\leq 2^i$, we add this edge into $\tilde{G}_{2^i}$.
Otherwise, we delete the edge.
Therefore, we obtain that $\tilde{G}_t = \bigcup_{t'\leq t} \tilde{G}'_{t'}$, and thus $\tilde{G}_1\subseteq \tilde{G}_2\subseteq\tilde{G}_4\subseteq\cdots\subseteq \tilde{G}_{\alpha^H}$.

The above step can be done by renaming the edges which only requires local computation.
Finally, we apply sorting (Theorem <ref>) again to remove duplicated edges in each $\tilde{G}_t$.

To conclude, the entire preprocessing stage takes $O(1)$ rounds and uses $O(nd+n^{1+\varepsilon/2}\log n)$ total space.
In addition, these steps are fully scalable in the MPC model.

Leader compression.
Now we describe how to implement leader compression algorithm (Algorithm <ref>) in the MPC model.
We firstly describe the format of the input data of of leader compression stored in the system.
Note that the partition $\cP$ is implied by the leader mapping function $\ell$: $\forall x,y\in X$, $x$ and $y$ are in the same part if and only if $\ell(x)=\ell(y)$.
Therefore, we store $\ell$ in the system to denote $\cP$.
In particular we have $|X|$ tuples $(x,\ell(x))$ distributed on the machines.
The graph $H$ is represented a set of edges, and the edges $(x,y)$ are also distributed on the machines.
The boolean value $\text{Edges}$ is known by all machines (this can be done by Theorem <ref> for broadcasting).

We firstly need to compute the set of leaders $S$.
This step can be done by looking at each tuple $(x,\ell(x))$.
If $\ell(x)=x$, we generate the random bit $b_x$ for the leader node $x$ (e.g., create a tuple $(``b",x,b_x)$).
Above steps only require local computation.
The next step is to let $b_x\gets b_{\ell(x)}$ for every $x\in X$.
We can regard it as a simultaneous access problem in the PRAM model.
In particular, the vector $b$ is stored in the shared memory.
Each processor corresponds to a tuple $(x,\ell(x))$.
If $x\not=\ell(x)$, then the processor reads the value of $b_{\ell(x)}$ and writes the value of $b_x$.
This operation has $O(1)$ depth and $O(|X|)$ work in the PRAM model.
Therefore, according to the simulation algorithm (Theorem <ref>), we can use $O(1)$ rounds and total space $O(n)$ to compute $b_x$ for all $x\in X$.
In addition, this step is fully scalable.
Then the next step is to find all edges $(x,y)\in H$ such that $b_x=1$ and $b_y=0$, and for each such edge, create a tuple $(\ell(y),(x,y,\ell(x)))$.
This step can also be regarded as a simultaneous access problem in the PRAM model.
In particular, the vector $b$ and the vector $\ell(\cdot)$ is stored in the shared memory.
Each processor corresponds to each edge $(x,y)\in H$.
The process that all processors simulateously read corresponding $b_x,b_y,\ell(x),\ell(y)$ has $O(1)$ depth and $O(|H|+|X|)$ work.
Therefore, by applying the simulation algorithm again (Theorem <ref>), we can use $O(1)$ rounds and $O(|H|+|X|)$ total space in the MPC model to create all tuples $(\ell(y),(x,y,\ell(x)))$ for edges $(x,y)\in H$ whose $b_x=1,b_y=0$.
This step is also fully scalable.
Then for each $z=\ell(y)$, if there are some tuples $(z,(\cdot, \cdot,\cdot))$ created, we only keep an arbitrary one $(\ell(y),(x,y,\ell(x)))$.
This deduplication step can be done by sorting (Theorem <ref>).
Thus it is fully scalable, takes $O(1)$ rounds and uses total space at most $O(|H|)$.
For every tuple $(\ell(y),(x,y,\ell(x)))$ that is kept, if $\text{Edges}$ is true, we add edge $(x,y)$ into the output edge set $E$.
This operation can be done by local computation only (e.g., create a tuple $(``E",(x,y))$).
Finally, we need to update $\ell(y)$ for all $y\in X$.
In particular, if there is a tuple $(\ell(y),(x,y,\ell(x)))$ kept, we need to update $\ell(y)\gets \ell(x)$.
Otherwise we keep $\ell(y)$ unchanged.
This operation can also be seen as a simultaneous access in the PRAM model.
In particular, we have a size $|X|$ array stored in the shared memory, if there is a tuple $(\ell(y),(x,y,\ell(x)))$ kept, then the entry of the array with index $\ell(y)$ has value $(x,y,\ell(x))$.
Otherwise, the entry of the array with index $\ell(y)$ has value empty.
Each processor corresponds to each tuple $(y,\ell(y))$.
Each processor simutaneously accesses the array and see whether the entry with index $\ell(y)$ is empty or not.
If the entry is empty, the processor keeps $(y,\ell(y))$ unchanged.
Otherwise the entry is $(x,y,\ell(x))$, the processor updates $(y,\ell(y))$ to $(y,\ell(x))$.
These PRAM operations take $O(1)$ depth and $O(|X|)$ total work.
Therefore, according to the simulation theorem again (Theorem <ref>), the above steps can also be done using $O(1)$ rounds and $O(|X|)$ total space, and the algorithm is fully scalable in the MPC model.

To conclude, the one leader compression step can be implemented in the MPC model using $O(1)$ rounds and $O(|X|+|H|)$ total space.
In addition, the algorithm is fully scalable.

Part 1 of the algorithm.
We consider how to implement Algorithm <ref> in the MPC model.
Notice that we will run Algorithm <ref> for $t=\alpha,\alpha^2,\alpha^3,\cdots,\alpha^H$ simutenously in parallel.
Firstly, we can apply Theorem <ref> to duplicate the point set $H$ times.
This operation is fully scalable and takes $O(1)$ rounds and $O(H\cdot n\log n)$ total space.
Note that the graphs $\tilde{G}_\alpha,\tilde{G}_{\alpha^2},\tilde{G}_{\alpha^3},\cdots,\tilde{G}_{\alpha^H}$ are already computed and stored distributedly in the system.
We can use sorting (Theorem <ref>) to send each $\tilde{G}_t$ and a duplicated copy of the input point set to a group of machines.
Thus we can handle $t=\alpha,\alpha^2,\alpha^3,\cdots,\alpha^H$ simutenously in parallel.
This operation is fully scalable and takes $O(1)$ rounds and $O(n^{1+\varepsilon/2}\log n)$ total space.

Next, we focus on how to implement Algorithm <ref> for a fixed $t$.
The first step is to generate partition $\cP^{(0)}_t$.
As we discussed before, we only need to generate the leader mapping function $\ell_t^{(0)}(\cdot)$ such that $x$ and $y$ are in the same part of $\cP^{(0)}_t$ if and only if $\ell_t^{(0)}(x) = \ell_t^{(0)}(y)$.
Recall the definition $\cP^{(0)}_t$, two points $x,y$ are in the same part if and only if they are in the same cell in the grid of level $t/\beta$.
As discussed in the preprocessing step, all machines agree on the same randomly shifted grid, thus each cell at level $t/\beta$ can be uniquely determined by a vector in $\mathbb{Z}^{d'}$ (see the discussion in Section <ref>).
Let $c(x)\in \mathbb{Z}^{d'}$  denote the cell which contains point $x$ in level $t/\beta$.
Then we can compute $(c(x), x)$ for every point $x\in X$.
This step only requires local computation.
We can sort (Theorem <ref>) all $(c(x),x)$ such that each point $x$ learns whether it is the first point in the cell $c(x)$.
For each $(c(x),x),$ we create a tuple $((c(x),x),1)$ if $x$ is the first point in the cell $c(x)$ and set $\ell_t^{(0)}(x) = x$.
Otherwise we create a tuple $((c(x),x),0)$
Then, by applying the predecessor algorithm (Theorem <ref>), each point $x$ learns the index of the point $y$ which is the first point within the same cell $c(x)=c(y)$.
By using the index of the point $y$ and simulating the simultaneous access operation in PRAM (Theorem <ref>), each point $x$ learns $y$ which is the first point in the same cell.
Then we set $\ell_t^{(0)}(x)=y$.
The above operations only require $O(1)$ rounds and $O(n\log n)$ total space.

Once we obtained $\ell^{(0)}_t$, we are able to run $h=O(\log\log n)$ rounds of leader compression process.
As we discussed previously, running $h$ rounds of leader comression takes $O(\log\log n)$ rounds and $O(|X|+|\tilde{G}_t|)$ space.
The algorithm is fully scalable as well.
For each $(x,y)\in\tilde{G}_t$, we want to access $\ell^{(h)}_t(x)$ and $\ell^{(h)}_t(y)$, this again can be regarded as a simultaneous access problem in the PRAM model where $\ell^{(h)}_t$ is stored in the shared memory and each processor corresponds to each edge $(x,y)\in\tilde{G}_t$.
Each processor requires to read $\ell^{(h)}_t(x)$ and $\ell^{(h)}_t(y)$, and if they are not equal, the processor writes $\textsc{Incomplete}$ to the $\ell^{(h)}_t(x)$-th entry and the $\ell^{(h)}_t(y)$-th entry of an array in the shared memory.
According to the simulation theorem (Theorem <ref>), these steps can be done in $O(1)$ rounds in the MPC model and $O(|X|+|\tilde{G}_t|)$ space, and it is fully scalable.
Then for each point $x$, we can check whether it is a leader, i.e., $\ell^{(h)}_t(x)=x$ and whether it is marked as Incomplete.
This operation can be done by simulating simultaneous access in PRAM (Theorem <ref>) which takes $O(1)$ rounds and $O(n)$ total space, and is fully scalable.
Let $I$ be the set of all incomplete leaders.
Then for each $x\in I$, we can locally compute $(c(x),x)$ where $c(x)\in\mathbb{Z}^{d'}$ indicates the cell at the level $\alpha^{k+1}/\beta$ containing $x$.
Then we can sort all such $(c(x),x)$, and each point in $I$ learns whether it is the first point among $I$ and in the cell $c(x)$.
By following the similar approach of computing $\ell_t^{(0)}$, we compute $\ell_t^{(h+1)}(x)=y$ for each $x\in I$ where $y\in I$ is the first point in the cell $c(x)$.
Similar as computing $\ell_t^{(0)}$, this step takes $O(1)$ MPC rounds and requires $O(n\log n)$ total space, and it is fully scalable.
For each leader which is not Incomplete, i.e., $x\not\in I$, we set $\ell^{(h+1)}(x)=x$.
This can be done by simulating simultaneous access in PRAM (Theorem <ref>).
Thus, it is fully scalable, has $O(1)$ rounds, and uses space $O(n)$.
Finally, for each tuple $(x,\ell^{(h)}_t(x))$, we access $\ell^{(h+1)}_t(\ell^{(h)}_t(x))$ and create a new tuple $(x,\ell^{(h+1)}_t(\ell^{(h)}_t(x)))$ to indicate $\ell^{(h+1)}_t(x)\gets \ell^{(h+1)}_t(\ell^{(h)}_t(x))$.
This can also be done by simulating simultaneous access in PRAM (Theorem <ref>).
Thus, it is fully scalable, has $O(1)$ rounds, and uses space $O(n)$.
The output $\hat{\cP}_t$ is represented by $\ell_t(\cdot)\equiv\ell^{(h+1)}_t(\cdot)$.

To conclude, Part 1 of the algorithm (Algorithm <ref>) is fully scalable.
It requires $O(\log\log n)$ rounds and requires total space $O(n^{1+\varepsilon/2}\log n)$.

Part 2 of the algorithm.
We consider how to implement Algorithm <ref> for all $t=1,2,4,8,\cdots,\alpha^H$.
Firstly, we can duplicate our input data $\log(\alpha^H)$ times (Theorem <ref>) which takes $O(1)$ rounds and $O(n\log n \cdot \log(\alpha^H))$ total space, and the algorithm is fully scalable.
Then we can use disjoint set of machines to handle each $t$ separately.
Note that $\tilde{G}_t$ are already stored in the system due to the preprocessing stage.
We also send $\tilde{G}_t$ to the group of machines which will be used to compute $\hat{\cP}_t$.
This is also fully scalable and takes only $O(1)$ rounds and total space $O(n^{1+\varepsilon/2}\log n)$.

As described in Section <ref>, instead of computing all $t$ at the same time, we handle $t$ in descreasing order of $v_2(\log t)$ (recall Definition <ref> for $v_2(\cdot)$).
In particular, we already obtained $\hat{\cP}_t$ for all $t=1,\alpha,\alpha^2,\cdots,\alpha^H$ by running Part 1 of the algorithm.
More precisely, we obtained $\ell_t(\cdot)$ for these $t$.
In the first iteration, $\kappa=\sqrt{\alpha}$, we will handle $t=\sqrt{\alpha},\alpha^{1.5},\cdots,\alpha^{H-0.5}$ at the same time in parallel, i.e., we will have $\hat{\cP}_t$ for all $t=1,\alpha^{0.5},\alpha,\alpha^{1.5},\cdots,\alpha^H$ at the end of the first iteration.
In the second iteration, $\kappa=\alpha^{0.25}$, we will have $\hat{\cP}_t$ for all $t=1,\alpha^{0.25},\alpha^{0.5},\alpha,\cdots,\alpha^H$ at the end of the second iteration.
In the $i$-th iteration we will have $\kappa=\alpha^{1/2^i}$, and we will have $\hat{\cP}_t$ for all $t=\kappa^0,\kappa,\kappa^2,\cdots,\alpha^H$ at the end of the $i$-th iteration.
Thus, we will have $O(\log\log(\alpha))=O(\log\log\log(n))$ iterations in total.
Note that if $\hat{\cP}_t$ is computed in the $i$-th iteration, then $\forall j\geq 1$, $\hat{\cP}_{t}$ (more precisly, $\ell_t(\cdot)$) will be the input for computing $\hat{\cP}_{t\cdot \alpha^{1/2^{i+j}}}$ and $\hat{\cP}_{t/ \alpha^{1/2^{i+j}}}$.
Therefore, when all $\ell_t(\cdot)$ are computed after the $i$-th iteration, we can use duplication process (Theorem <ref>) to duplicate all $\ell_t(\cdot)$ at most $O(\log\log\log(n))$ times and send each duplicated copy of $\hat{\cP}_t$ (more precisely, $\ell_t(\cdot)$) to the groups of machines that will be used to compute $\hat{\cP}_{t\cdot \alpha^{1/2^j}}$ or $\hat{\cP}_{t/ \alpha^{1/2^j}}$ for $j\geq 1$.

When a group of machines recieves all required inputs $X, \tilde{G}_t,\ell_{t/\kappa}(\cdot),\ell_{t\cdot \kappa}(\cdot)$, it starts to run Algorithm <ref> to compute $\hat{\cP}_t$ (i.e., $\ell_t(\cdot)$).
We firstly intialize $\ell_t^{(0)}(\cdot)$ to be $\ell_{t/\kappa}(\cdot)$.
Then, similar as Part 1 of the algorithm, we run $O(\log\log n)$ rounds of leader compression.
This step takes $O(\log\log n)$ MPC rounds and $O(|X|+|\tilde{G}_t|)$ space.
This step is fully scalable.
Then by using the same process described in how to implement Part 1 of the algorithm, we can simulate PRAM operations (Theorem <ref>) to find all $x\in X$ that are marked as Incomplete.
For each leader $x$ ($\ell_t^{(h)}(x)=x$) which is marked as Incomplete, let $\ell_{t}^{(h+1)}(x)=\ell_{t\cdot \kappa}(x)$.
For each leader $x$ ($\ell_t^{(h)}(x)=x$) which is not marked as Incomplete, let $\ell_{t}^{(h+1)}(x)=x$.
Finally, for each $x\in X$, let $\ell_{t}^{(h+1)}(x)\gets \ell_{t}^{(h+1)}(\ell_{t}^{(h)}(x))$.
Similar as before, above operations used to compute $\ell_{t}^{(h+1)}(\cdot)$ can be seen as simultaneous accesses in the PRAM model which requires $O(1)$ depth and $O(n)$ total work.
By applying PRAM simulation again (Theorem <ref>), the above procedure to compute $\ell_t^{(h+1)}(\cdot)$ requires $O(1)$ MPC rounds and $O(n)$ total space, and it is fully scalable.
Note that the output $\hat{\cP}_t$ is represented by $\ell_t(\cdot)\equiv \ell_{t}^{(h+1)}(\cdot)$.

To conclude, to compute $\hat{\cP}_t$ (more preciesly, $\ell_t(\cdot)$) for all $t=1,2,4,\cdots,\alpha^H$, our algorithm takes $O(\log\log(n)\cdot\log\log\log(n))$ rounds.
The total space required is at most $n^{1+\varepsilon/2}\cdot \polylog(n)$.
In addition, the algorithm is fully scalable.

Part 3 of the algorithm.
Finally, let us consider how to implement Algorithm <ref> in parallel for all $t$ in the MPC model.

Similar as before, we use a disjoint group of machines to compute $\textsc{Part3}(X,t,\tilde{G}_{t},\hat{\cP}_{t/2},\hat{\cP}_t)$ for each $t$.
To do this, we need to duplicate $X$ $\log(\alpha^H)$ times and duplicate $\hat{\cP}_t$ (i.e., $\ell_t(\cdot)$) $2$ times ($\hat{\cP}_t$ is used to compute $\textsc{Part3}(X,t,\tilde{G}_{t},\hat{\cP}_{t/2},\hat{\cP}_t)$ and $\textsc{Part3}(X,2t,\tilde{G}_{2t},\hat{\cP}_{t},\hat{\cP}_{2t})$).
Then we send each copy of the data and $\tilde{G}_t$ to the corresponding group of machines.
According to Theorem <ref>, above process can be done using $O(1)$ rounds and $n^{1+\varepsilon/2}\polylog(n)$ space, and these steps are fully scalable.

In the following, we describe how to implement Algorithm <ref> for any fixed $t$.
We initialize ${\ell'}^{(0)}_t(\cdot)$ to be $\ell_{t/2}(\cdot)$.
This only requires local computation.
Then, as we discussed previously, $O(\log\log n)$ rounds of leader compression can be implemented in $O(\log\log n)$ MPC rounds and $O(n^{1+\varepsilon/2}\log (n))$ total space, and the process is fully scalable.
The $i$-th round of leader compression outputs a set of edges $E_t^{(i)}$.
At the end of the last leader compression process, let the obtained leader mapping be ${\ell'}_t^{(h)}(\cdot)$.
For each $x\in X$, we check whether ${\ell'}_t^{(h)}(x)=\ell_t(x)$, if not, we create a set $S_{\ell_t(x)}$ and add ${\ell'}_t^{(h)}(x)$ into the set $S_{\ell_t(x)}$.
Note that this operation can be regarded as simultaneous access of ${\ell'}_t^{(h)}(\cdot)$ and $\ell_t(\cdot)$ under the PRAM model, which only has $O(1)$ depth and $O(n)$ work.
Therefore, according to the simulation theorem (Theorem <ref>), the computation of all $S_{\ell_t(x)}$ only requires $O(1)$ MPC rounds and $O(n)$ total space, and it is fully scalable.
Then, for each set $S_c$ if $z$ is in $S_c$, we add an edge $\{z,c\}$ into $F_t$.
Thus $F_t$ will be a forest of stars.
Then we output $F_t\cup \bigcup_{i=1}^h E_t^{(i)}$.

Next, we show how to create a balanced binary tree for each non-empty set $S_c$.
We use Theorem <ref> to compute an index of each element in each $S_c$, the index for elements in each set starts from $0$.
This step is fully scalable and takes $O(1)$ MPC rounds and $O(n)$ total space.
Then for each $u$ in each $S_c$ whose index is $i$, if $i\not = 0$, we find the element $v$ in $S_c$ whose index is $i-2^{v_2(i)}$ (recall Definition <ref> for the definition of $v_2(\cdot)$), we add the edge $\{u,v\}$ in $F_t$.
The above step only requires simultaneous accesses, therefore it can be done in MPC in $O(1)$ rounds and $O(n)$ total space by simulating PRAM operations (Theorem <ref>), and it is fully scalable.

To conclude, to compute $F_t\cup \bigcup_{i=1}^h E_t^{(i)}$ for all $t=1,2,4,\cdots,\alpha^H$, our algorithm takes $O(\log\log(n))$ rounds.
The total space required is at most $n^{1+\varepsilon/2}\cdot \polylog(n)$.
In addition, the algorithm is fully scalable.

For the purpose of computing an Euler tour of the tree later.
We do the following additional steps to create intermediate partitions between the partition represented by ${\ell'}_t^{(h)}$ and the partition represented by $\ell_t$, and thus we only merge at most $2$ components at each level of the partition.
We rearrange all sets on the machines such that each machine only uses memory $\Theta(s/\log(n))$.
To do this operation, we only need to use sorting (Theorem <ref>) which is fully scalable, takes $O(1)$ rounds and $O(n\log n)$ total space.
For each $u$ in each $S_c$ whose index is $i$, we do for each $j\in [\log n]$ in parallel, we query the vertex $v_j$ in $S_c$ whose index is $i - (i\bmod 2^j)$, and we set ${\ell'}_t^{(h+j)}(u)=v_j$.
These steps only corresponds to simultaneous accesses and thus we can simulate a PRAM operation in the MPC model which uses $O(1)$ rounds, $O(n\log n)$ total space and it is fully scalable.
Then, we duplicate $X$, $\log n$ times using Theorem <ref>.
This step takes $O(1)$ rounds, $O(n\log n)$ space and is fully scalable.
Next, we can do in parallel for all $j\in [\log n]$, for each $x\in X$, if ${\ell'}_{t}^{(h)}(x)=\ell_t(x)$, we set ${\ell'}_{t}^{(h+j)}(x)=\ell_t(x)$
Then, we check again for all $x\in X$.
We set ${\ell'}_t^{(h+j)}(x)={\ell'}_t^{(h+j)}({\ell'}_t^{(h)}(x))$.
Note that ${\ell'}_t^{(h+j)}({\ell'}_t^{(h)}(x))$ should be already set since either ${\ell'}_t^{(h)}(x)=\ell_t(x)$ or ${\ell'}_t^{(h)}(x)\in S_{\ell_t(x)}$.
In either case, ${\ell'}_t^{(h+j)}({\ell'}_t^{(h)}(x))$ is properly set.
Above steps only require simultaneous accesses and thus we can simulate a PRAM operation again in the MPC model which uses $O(1)$ rounds, $O(n\log n)$ total space and it is fully scalable.

Put them together.
All parts of our algorithm are fully scalable.
Thus, the overall algorithm is fully scalable as well.
The preprocessing stage takes $O(1)$ rounds and $O(nd+n^{1+\varepsilon/2}\log n)$ total space.
Running Algorithm <ref> for all $t=1,\alpha,\alpha^2,\cdots,\alpha^H$ takes $O(\log\log(n))$ rounds and $O(nd+n^{1+\varepsilon/2}\log n)$ total space.
Running Algorithm <ref> for all remaining $t$ takes $O(\log\log(n)\cdot \log\log\log(n))$ rounds and $n^{1+\varepsilon/2}\cdot\polylog n$ total space.
Running Algorithm <ref> for all $t$ takes $O(\log\log(n))$ rounds and $n^{1+\varepsilon/2}\cdot\polylog n$ total space.
Therefore, the entire algorithm takes $O(\log\log(n)\log\log\log(n))$ rounds and $O(nd+n^{1+\varepsilon})$ total space.

§ EULER TOUR OF APPROXIMATE EUCLIDEAN MST IN MPC

In this section, we show how to compute an Euler tour of the approximate MST that we obtained.
Note that the actual diameter of the tree that we obtained can be very large (for example, the tree that we obtained can be a path which has diameter $\Theta(n)$).
Therefore, we cannot use the algorithm of [6] which requires $\Omega(\log(\text{diameter}))$ rounds.
We propose a new method.
In particular, given the approximate MST and the hierarchy of clusters that we used to obtain the tree, we are able to use linear total space and $O(1)$ MPC rounds to compute an Euler tour of the tree, and our algorithm is fully scalable.

§.§ Additional Existing Algorithmic Primitives in the MPC Model

A standard way to store a sequence $A=(a_1,a_2,\cdots,a_n)$ in the MPC model is that we store tuples $(1,a_1),(2,a_2),(3,a_3),\cdots,(n,a_n)$ arbitrarily on the machines in a distributed manner (see e.g., [6]).
In this way, one can easily use sorting (Theorem <ref>) to reorder the elements such that the sequence is stored in consecutive machines and each machine stores corresponding consecutive elements in order. Similarly, a standard way to store a mapping $f:[n]\rightarrow [m]$ in the MPC model is that we store tuples $(1,f(1)),(2,f(2)),\cdots,(n,f(n))$.

The sequence insertion problem is stated as the following:
Given $k+1$ sequences  $A = (a_1, a_2, \cdots , a_m),$ $A_1, A_2, \cdots , A_k$ and a mapping $f:[k]\rightarrow \{0\}\cup[m]$, the goal is to output a sequence $A'$ which is obtained by inserting every $A_i,(i\in[k])$ into $A$ such that $A_i$ is between the element $a_{f(i)}$ and $a_{f(i)+1}$.
Let the total size of the input sequences is $|A|+|A_1|+|A_2|+\cdots+|A_k|=N$.
The size of $A'$ is also $N$, and the space to store the input mapping $f$ is $O(k)=O(N)$ as well.

There is a fully scalable MPC algorithm solving the sequence insertion problem in $O(1)$ rounds and $O(N)$ space.

Given a tree of $n$ nodes with diameter at most $\Lambda$, there is a fully scalable which takes $O(\log(\Lambda))$ rounds and $O(n^{1+\varepsilon})$ total space to output an Euler tour (see Definition <ref>) of the tree, where $\varepsilon>0$ is an arbitrarily small constant.

§.§ Join Euler Tours of Spanning Tree of Sub-clusters

Given a tree, we treat each edge $\{x,y\}$ as two directed edges $(x,y)$ and $(y,x)$.
An Euler tour of a tree is a traverse sequence of tree edges such that each directed edge $(x,y)$ appeared in the sequence exactly once.
The following gives a formal definition of an Euler tour of a tree.

Given a tree $T=(V,E)$ with $|V|=n$ nodes, the Euler tour of $T$ is a sequence $((v_1,v_2),(v_2,v_3),\cdots,(v_{2n-2},v_1))$ of length $2n-2$ where $\forall i\in[2n-2], \{v_{i},v_{(i\bmod (2n-2)) + 1}\}\in E$, and $\forall \{x,y\}\in E$, there exists exactly one $i\in [2n-2]$ and exactly one $i'\in[2n-2]$ such that $(v_i,v_{(i\bmod (2n-2)) + 1})=(x,y)$ and $(v_{i'},v_{(i'\bmod (2n-2)) + 1})=(y,x)$.

§.§.§ Properties of An Euler Tour of a Tree

In this section, we give some formal definitions for Euler tour of a tree.
Most observations stated in this section can also be found in the textbooks of algorithms such as [21].

Given a rooted tree $T$ over $V$, we use $\p:V\rightarrow V$ to denote a set of parent pointers which is a mapping from each node to its parent, and we set $\p(v)=v$ for the root $v$ of $T$.

Note that $\p(\cdot)$ contains the information of all tree edges and the root that we select.

Given parent points $\p(\cdot)$ of tree with root $v$, let $\size_{\p}(u)$ denote the number of nodes in the subtree rooted at $u$.
If $\p(\cdot)$ is clear in the context, we omit the subscript $\p$ and use $\size(u)$ for short.

Given a rooted tree represented by parent pointers $\p$, and an ordering of children of each node, we use $\child_{\p}(v)$ to denote the set of children of $v$, $\child_{\p}(v,i),(i\in[|\child_{\p}(v)|])$ to denote the $i$-th child of $v$, and $\rank_{\p}(v)$ to denote its rank among its siblings, i.e., $\rank_{\p}(v)$ satisfies $\child_{\p}(\p(v),\rank_{\p}(v))=v$ if $v$ is not a root and $\rank_{\p}(v)=1$ otherwise.

If $\p$ is clear in the context, we use $\child(\cdot)$ and $\rank(\cdot)$ without subscript $\p$ for short.

[Euler tour for different root]
Let $A=((v_1,v_2),(v_2,v_3),(v_3,v_4),\cdots,(v_{2n-2},v_1))$ be any Euler tour of a tree $T$, then any circular shift of $A$, $((v_j,v_{j+1}),(v_{j+1},v_{j+2}),\cdots,(v_{2n-2},v_1),(v_1,v_2),(v_2,v_3),\cdots,(v_{j-1},v_j))$ for $j\in[2n-2]$, is still an Euler tour of $T$.

If $A=((v_1,v_2),(v_2,v_3),(v_3,v_4),\cdots,(v_{2n-2},v_1))$ is an Euler tour of a tree $T=(V,E)$ and $v_1=u\in V$, then $A$ is an Euler tour with respect to the root $u$.

Let $A=((v_1,v_2),(v_2,v_3),(v_3,v_4),\cdots,(v_{2n-2},v_1))$ be an Euler tour of a tree $T=(V,E)$ with respect to the root $u$.
Suppose the children of $u$ are $u_1,u_2,\cdots,u_k$.
Then $A$ must have the form $(u,u_{j_1}),A_{j_1},(u_{j_1},u),(u,u_{j_2}),A_{j_2},(u_{j_2},u),\cdots,(u,u_{j_k}),A_{j_k},(u_{j_k},u)$ where $A_{j_i}$ is an Euler tour of the subtree with respect to the root $u_{j_i}$, and $j_1,j_2,\cdots,j_k$ is a permutation of $1,2,\cdots,k$.

Let $A=(e_1,e_2,\cdots,e_{2n-2})$ be an Euler tour of a tree $T$ where $e_i=(v_i,v_{i+1})$.
Given any node $v$, we say that the first appearance of $v$ is at $\first_A(v)=i$ of $A$ if $i$ is the smallest value such that $v_i=v$, and we say that the last appearance of $v$ is at $\last_A(v)=i$ if $i$ is the largest value such that $v_{i+1}=v$.
If the Euler tour is clear in the context, we omit the subscript $A$ of $\first$ and $\last$.

[Parent via Euler tour]
Let $A=((v_1,v_2),(v_2,v_3),(v_3,v_4),\cdots,(v_{2n-2},v_1))$ be an Euler tour of a tree $T$ with root $v$.
If $u$ is not a root, then $v_{\first(u)-1}$ is the parent of $u$.

[Euler tour of subtree]
Let $A=(e_1,e_2,\cdots,e_{2n-2})$ be an Euler tour of a tree $T$ with respect to the root $u$.
Let $v$ be any node in tree $T$, let $i$ be the first appearance of $v$ in $A$, and let $j$ be the last appearance of $v$ in $A$.
Then $(e_i,e_{i+1},\cdots,e_j)$ is an Euler tour of the subtree rooted at $v$ (note that $j=i-1$ when $v$ is a leaf and thus the tour is an empty sequence), and thus $(j-i+1)/2+1$ is the size of the subtree rooted at $v$.

Given a tree $T$ rooted at $v$ with parent pointers $\p$, and given a mapping $\child_{\p}(\cdot,\cdot)$ (Definition <ref>), then we are able to construct an Euler tour $A$ with respect to the root $v$ such that for any node $u$ in the tree, we have $\first(\child(u,1))<\first(\child(u,2))<\first(\child(u,3))<\cdots<\first(\child(u,|\child(u)|))$.
In addition, for any non-root node $u$, let the path $((x_1,x_2),(x_2,x_3),\cdots,(x_{k-1},x_k))$ be the unique simple path from the root $v$ to $u$ (i.e., $x_1=v,x_k=u$), then the position of the (directed) edge $(\p(u),u)$ in $A$ is:

\begin{align*}
p=\sum_{l=2}^k \left(1+\sum_{i=1}^{\rank(x_l)-1}\size(\child(x_{l-1},i))\right),
\end{align*}

and the position of the (directed) edge $(u,\p(u))$ is $p+2\cdot (\size(x_k)) -1$

The proof is by induction and construction.
If $T$ only has one node, then $\child(v)=\emptyset$ and we just output $A$ to be an empty sequence.

Suppose the statement is true for any tree whose depth is at most $l-1$, now we consider how to construct $A$ for a tree with depth $l$.
Suppose $T$ has root $v$ and $\forall i\in[|\child(v)|],\child(v,i)=v_i$.
We construct $A$ to be following:

\begin{align*}
(v,v_1), A_1, (v_1,v), (v, v_2), A_2, (v_2, v),\cdots,(v,v_{|\child(v)|}), A_{|\child(v)|}, (v_{|\child(v)|},v),
\end{align*}

where $A_i$ is an Euler tour of the subtree rooted at $v_i$ via our induction hypothesis.
Then, if $u$ is in a subtree of $v_i$, then we still have $\first(\child(u,1))<\first(\child(u,2))<\first(\child(u,3))<\cdots<\first(\child(u,|\child(u)|))$ by our induction hypothesis.
Otherwise, if $u=v$, it is clear that $\first(v_1)<\first(v_2)<\first(v_3)<\cdots<\first(v_{|\child(v)}|)$.
In the remaining of the proof, we need to determine the position of an edge.
If an edge is $(v,v_i)$, then its position is clearly $1+\sum_{j=1}^{i-1}2\cdot\size(v_j)$.
If an edge is $(v_i,v)$, then its position is $\sum_{j=1}^{i}2\cdot\size(v_j)$.
Consider an edge $(\p(u),u)$ is in the subtree rooted at $v_i$.
Let $((x_1,x_2),(x_2,x_3),\cdots,(x_{k-1},x_k))$ be the path from $v$ to $u$, i.e., $x_1=v,x_2=v_i,x_{k-1}=\p(u),x_k=u$.
Then by our induction hypothesis, the position of $(\p(u),u)$ is

\begin{align*}
&1+\left(\sum_{j=1}^{\rank(v_i)-1}2\cdot\size(v_j)\right)+\sum_{l=3}^k \left(1+\sum_{j=1}^{\rank(x_l)-1}2\cdot\size(\child(x_{l-1},j))\right)\\
&=\sum_{l=2}^k \left(1+\sum_{j=1}^{\rank(x_l)-1}2\cdot\size(\child(x_{l-1},j))\right).
\end{align*}

Similarly, the position of $(u,\p(u))$ is

\begin{align*}
&1+\left(\sum_{j=1}^{\rank(v_i)-1}2\cdot\size(v_j)\right)+\sum_{l=3}^k \left(1+\sum_{j=1}^{\rank(x_l)-1}2\cdot\size(\child(x_{l-1},j))\right)+2\cdot\size(x_k) - 1\\
&=\sum_{l=2}^k \left(1+\sum_{j=1}^{\rank(x_l)-1}2\cdot\size(\child(x_{l-1},j))\right)+2\cdot\size(x_k) - 1.
\end{align*}

Therefore, we conclude the proof of the induction.

[Euler tour and a path from the root]
Let $A=(e_1,e_2,\cdots,e_{2n-2})$ be an Euler tour of a tree $T$ with respect to the root $u$.
Consider any node $v$.
If $i$ is the first appearance of $v$, and $B=((x_1,x_2),(x_2,x_3),\cdots,(x_{k-1},x_k))$ is a simple directed path from $u$ to $v$ (i.e., $x_1=u,x_k=v$), then we have:

* $\forall j\in [k-1]$, $(x_{j},x_{j+1})$ appears in $(e_1,\cdots,e_{i-1})$ in $A$, and $(x_{j+1},x_j)$ appears in $(e_i,\cdots,e_{2n-2})$.

* If $\{p,q\}$ is a tree edge but neither $(p,q)$ nor $(q,p)$ appears in the path $B$, then both $(p,q)$ and $(q,p)$ appear simultaneously in $(e_1,\cdots,e_{i-1})$ or appear simultaneously in $(e_i,\cdots,e_{2n-2})$.

Let $A=(e_1,e_2,\cdots,e_{2n-2})$ be an Euler tour of a tree $T$ with respect to the root $u$.
Let $w$ be a weight function such that every edge $\{p,q\}$ has a weight $w(\{p,q\})$ in the tree.
Let $w'$ be the weight function of directed edge such that $\forall \text{edge }\{p,q\}$, if $p=\p(q)$, then $w'(p,q)=w(\{p,q\})$ and $w'(q,p)=-(w\{p,q\})$.
Let $B=((x_1,x_2),(x_2,x_3),\cdots,(x_{k-1},x_k))$ be a simple directed path from $u$ to $v$, then the total edge weight on the path $\sum_{i=2}^k w(\{x_{i-1},x_{i}\})=\sum_{j=1}^{\first(x_k)-1} w'(e_j)$, i.e., the prefix sum over $A$ with weights $w'$.

Due to Observation <ref>, for the prefix of $A$, if an edge is on the path,  we will count its edge weight once, otherwise, the non-path edge weight is either cancelled since both directions appeared, or none of the directions is appeared so we did not count it.

§.§.§ MPC Algorithms for Trees via Euler Tour

Given an arbitrary Euler tour $A$ of a tree $T$ over $n$ nodes $V$, and given any node $v\in V$, there is a fully scalable MPC algorithm which outputs an Euler tour $A'$ of tree $T$ with respect to the root $v$ in $O(1)$ rounds and $O(n)$ total space.

We use sorting (Theorem <ref>) to find the first appearance of $v$ in $A=\{e_1,e_2,\cdots,e_{2n-2}\}$, and send $i=\first_A(v)$ to all machines by broadcasting algorithm (Theorem <ref>).
These steps only take $O(1)$ rounds and $O(n)$ total space, and they are fully scalable.
Then compute the circular shift $A'=(e_i,e_{i+1},\cdots,e_{2n-2},e_1,\cdots,e_{i-1})$ of $A$.
Since every machine learns $\first_A(v)$, computing the circular shift only requires local computation.
According to Observation <ref>, the circular shift $A'$ is also an Euler tour of $T$.
Since $A'$ starts from node $v$, $A'$ is an Euler tour of $T$ with respects to the root $v$.

Given an arbitrary Euler tour $A$ of a tree $T$ over $n$ nodes $V$ with root $v$, there is a fully scalable MPC algorithm which outputs the size of each subtree $u$ in $O(1)$ rounds and $O(n)$ total space.

We suppose $A$ is an Euler tour of $T$ with respect to the root $v$.
Otherwise, we can apply Lemma <ref> to make $A$ satisfiy above condition, and the operation is fully scalable, takes $O(1)$ rounds and $O(n)$ space.

We use sorting (Theorem <ref>) to compute $\first(u)$ and $\last(u)$ for each $u\in V$.
It is fully scalable and only takes $O(1)$ rounds and $O(n)$ total space.
Then, for each $u$ in parallel, we simultaneously query both $\first(u)$ and $\last(u)$, which can be done in the fully scalable setting by Theorem <ref> in $O(1)$ rounds and $O(n)$ total space.
According to Observation <ref>, $\size(u)=(\last(u)-\first(u)+1)/2+1$.

Given a tree $T$ rooted at $v$ over $n$ nodes $V$ with parent pointers $\p$, and given a mapping $\child_{\p}(\cdot,\cdot)$ (Definition <ref>), if we also have an arbitrary Euler tour $A'$ of $T$, there is an MPC algorithm which constructs an Euler tour $A$ with respect to the root $v$ such that for any node $u$ in the tree, it satisfies $\first(\child(u,1))<\first(\child(u,2))<\first(\child(u,3))<\cdots<\first(\child(u,|\child(u)|))$.
In addition, for any non-root node $u$, let the path $((x_1,x_2),(x_2,x_3),\cdots,(x_{k-1},x_k))$ be the unique simple path from the root $v$ to $u$ (i.e., $x_1=v,x_k=u$), then the position of the (directed) edge $(\p(u),u)$ in $A$ is:

\begin{align*}
p=\sum_{l=2}^k \left(1+\sum_{i=1}^{\rank(x_l)-1}\size(\child(x_{l-1},i))\right),
\end{align*}

and the position of the (directed) edge $(u,\p(u))$ is $p+2\cdot (\size(x_k)) -1$.
In addition, the algorithm is fully scalable, and it takes $O(1)$ rounds and $O(n)$ total space.

Note that the formulation of the position of each directed edge $(\p(u),u),(u,\p(u))$ is given, and Lemma <ref> already showed that the resulting sequence is indeed an Euler tour with stated properties.
Therefore, our goal is to provide an MPC algorithm to efficiently compute the position of each directed edge in the resulting Euler tour $A$.

We can assume $A'$ is an Euler tour of $T$ with respect to the root $v$.
Otherwise, we apply Lemma <ref> to make $A'$ be with respect to the root $v$ which takes $O(1)$ rounds, $O(n)$ total space in the fully scalable setting.
We apply Lemma <ref> on $A'$ to compute the size of each subtree in $O(1)$ rounds, $O(n)$ total space in the fully scalable setting.
Next, for each node $u$, we want to compute $w(\{u,\p(u)\})=1+\sum_{i=1}^{\rank(u)-1}\size(\child(\p(u),i))$ for each non-root $u$.
To achieve this, for each mapping $y=\child(x,i)$ in parallel, we create $\rank(y)=i$, add $y$ into a set $S_x$, and simultaneously access the value $\size(y)$.
The simultaneous access operation can be done by Theorem <ref>.
Then we apply the subset prefix sum algorithm (Theorem <ref>) over $\{S_x\}$ and thus each non-root $u$ learns the value $\sum_{i=1}^{\rank(u)-1}\size(\child(\p(u),i))$, and it sets the edge weight $w(\{u,\p(u)\})=1+\sum_{i=1}^{\rank(u)-1}\size(\child(\p(u),i))$.
The overall number of rounds needed to compute $w(\cdot)$ is $O(1)$, and it requires $O(n)$ total space, and is fully scalable.

Finally, we want to compute the position of each directed edge $(\p(u),u)$, $(u,\p(u))$ in the final sequence $A$.
Note that the position of $(\p(u),u)$ is $\sum_{x\in V:x\not=v\text{ and } x\text{ is on the path from the root }v\text{ to }u}w(x)$.
Suppose $A'=(e'_1,e'_2,\cdots,e'_{2n-2})$.
If $e'_i=(v'_i,v'_{i+1})$ satisfies $v'_i=\p(v'_{i+1})$, let $w'_i=w(\{v'_i,v'_{i+1}\})$, otherwise, let $w'_i=-w(\{v'_i,v'_{i+1}\})$.
Then according to Corollary <ref>, the position of $(\p(u),u)$ is a prefix sum $\sum_{i=1}^{\first_{A'}(u)} w'_i$.
Note that computing $w'$ only requires simultaneous accesses which can be done in $O(1)$ rounds, $O(n)$ total space, and in fully scalable setting according to Theorem <ref>.
Then computing prefix sum $\sum_{i=1}^j w'_i$ can be done using Theorem <ref>.
It takes $O(1)$ rounds, $O(n)$ total space, and is fully scalable.
Note that the position of $(u,\p(u))$ is the position of $(\p(u),u)$ plus $2\cdot\size(u)-1$.
Since $\size(u)$ is already computed, all computations of positions $(\p(u),u)$ can be done in parallel with an additional call of simultaneous access (Theorem <ref>).

Therefore, the overall algorithm only takes $O(1)$ rounds, $O(n)$ total space.
The algorithm is fully scalable.

§.§.§ Euler Tour Join

Now consider the following problem.
We define the problem of joining Euler tours as following:

* Inputs:

* A partition $\cC=\{C_1,C_2,\cdots,C_k\}$ of a node set $V$, represented by a leader mapping $\ell:V\rightarrow V$ where two nodes $u,v$ are in the same component iff $\ell(u)=\ell(v)$.
Each component $C_i$ is represented by its leader node, i.e., $u\in C_i$ and $\ell(u)=u$.

* A spanning tree $T=(\cC, E)$ over components $C_1,C_2,\cdots,C_k$ where each node in $T$ corresponds to a component $C_i$.
An Euler tour $A$ of $T$ is also given.

* An edge mapping $g,$ where $\forall e=\{C_i,C_j\}\in E$, $g(e)=\{x,y\}\subseteq V$ and $x\in C_i,y\in C_j$, we sometimes also abuse the notation and use directed version $g(C_i,C_j)=(x,y)$ and $g(C_j,C_i)=(y,x)$.
We use $g^{-1}$ to indicate the inverse mapping.

* A spanning tree $T_i=(C_i,E_i)$ for each component $i\in[k]$, and an Euler tour $A_i$ of $T_i$.

* Outputs:

* A spanning tree $T'=\left(V,\{g(e)\mid e\in E\}\cup\bigcup_{i\in[k]}E_i\right)$ over $V$, and an Euler tour $A'$ of $T'$.

In Algorithm <ref>, we show a novel MPC algorithm that solves the Euler tour join problem efficiently.

$\textsc{EulerTourJoin}(\cC, T,A, g, \{T_i\}, \{A_i\})$: Generating a spanning tree of $V$ and the Euler tour of the spanning tree.

[1]
Inputs: $\cC=\{C_1,C_2,\cdots,C_k\}$ is a partition over a node set $V$, $T=(\cC, E)$ is a spanning tree over $\cC$, $A$ is an arbitrary Euler tour of $T$, $g$ is a mapping such that $\forall e=\{C_i,C_j\}\in E, g(e)=\{x,y\}$ where $x\in C_i, y\in C_j$, and $T_i=(C_i,E_i)$ is a spanning tree of $C_i$ and $A_i$ is an Euler tour of $T_i$.
Let $\hat{E}=\{g(e)\mid e\in E\}$.
Let $T'=(V,\hat{E}\cup\bigcup_{i\in [k]}E_i)$ be the spanning tree over $V$.
Let $\hat{V} = \{x \in V \mid \exists y, \{x,y\}\in \hat{E}\}$.
Choose an arbitrary root $C\in\cC$ for $T$, and shift $A$ to make it be an Euler tour of $T$ with respect to the root $C$.
For each $C_i,i\in[k]$, compute its parent $\p_T(C_i)$ in $T$ when root is $C$.
For each $i\in[k]$, let $(x,y)=g(C_i,\p_T(C_i))$, and
circular shift $A_i$ to make $A_i$ be an Euler tour of $T_i$ with root $x$.
If $C_i$ is a root, we circular shift $A_i$ to make $A_i$ be an Euler tour of $T_i$ with an arbitrary node from $\hat{V}$ as a root.
For each $i\in [k]$, sort all children of $C_i$ in $T$:
Consider two children $C_j$ and $C_q$ of $C_i$, if $(x,y)=g(C_i,C_j),(x',y')=g(C_i,C_q)$ and $\first_{A_i}(x)<\first_{A_i}(x')$, then we regard that $C_j$ has smaller rank than $C_q$ among children of $C_i$. If $x=x'$, we can given an arbitrary ordering for $C_j$ and $C_q$.
Compute a new Euler tour $\bar{A}$ for $T$ with respect to the root $C$, satisfying that $\forall C_i\in\cC$, $\first_{\bar{A}}(\child( C_i,1))<\first_{\bar{A}}(\child( C_i,2))<\cdots<\first_{\bar{A}}(\child( C_i,|\child( C_i)|))$.
Compute $\hat{A}$: for each $(C_p,C_q)$ appeared in the sequence of $\bar{A}$, replace it with $g(C_p,C_q)$.
Compute $A_x$ for each $x\in \hat{V}$: Suppose $x$ is in $C_i$, and $A_i=((v_1,v_2),(v_2,v_3),\cdots,(v_{2\cdot|C_i|-2},v_1))$, let $A_x=((v_{\first_{A_i}(x)},v_{\first_{A_i}(x)+1}),(v_{\first_{A_i}(x)+1},v_{\first_{A_i}(x)+2}),\cdots,(v_{j},v_{(j\bmod (2\cdot|C_i|-2))+1}))$ where $j> \first_{A_i}(x)$ is the smallest value such that either $j=2\cdot|C_i|-2$ or $j=\first_{A_i}(x')$ for some $x'\in \hat{V}$.
Compute a mapping $f:\hat{V}\rightarrow [2\cdot |\mathcal{C}|-2]$.
Suppose $\hat{A}=((v'_1,v'_2),(v'_2,v'_3),\cdots,(v'_{2\cdot |\mathcal{C}|-2},v'_1))$.
For each $x\in \hat{V}$, compute $f(x)=j$ where $j\in [2\cdot |\mathcal{C}|-2]$ is the largest value such that $v'_{(j\bmod(2\cdot |\cC|-2 ))+1}=x$.
Compute a sequence $A'$ by plugging $A_x$ for each $x\in \hat{V}$ into $\hat{A}$, where $A_x$ should be inserted directly after $(v'_{f(x)},v'_{(f(x)\bmod(2\cdot |\cC|-2 ))+1})$ in $\hat{A}$.
Output: $T'$ and its Euler tour $A'$.

The output $A'$ of Algorithm <ref> is an Euler tour of the output $T'$, and $T'$ is a spanning tree of $V$, where the edges of $T'$ is the union of edges in $T_1,T_2,\cdots,T_k$ and edges $\{g(e)\mid e\in E\}$.

Since each $T_i$ is a spanning tree of $C_i$, and $T$ is a spanning tree of $\{C_1,C_2,\cdots,C_k\}$ and $\hat{E}$ are inter-cluster edges with respect to $T$, we know that $T'$ is a spanning tree of $\bigcup_{i\in[k]}C_i = V$, and the edges of $T'$ is union of edges in $T_1,T_2,\cdots,T_k$ and $\hat{E}=\{g(e)\mid e\in E\}$.

Since $\bar{A}$ is an Euler tour of $T$ which means that both directions of each edge in $\hat{E}$ must appear in $\hat{A}$, which means that every node in $\hat{V}$ also appears in $\hat{A}$.
According to our construction of $A'$, both directions of every edge in $T'$ must appear in $A'$ and $|A'|=|A|+\sum_{x\in\hat{V}}|A_x|=|A|+\sum_{i\in[k]]}|A_i|=2|V|-2$ which implies that each direction of each edge in $T'$ also appeared exactly once.

In the remaining of the proof, we only need to show that $A'$ is indeed a cycle.
Consider an arbitrary $(u,v)$ appeared in $\hat{A}$.
By our construction of $\hat{A}$, $\{u,v\}$ must be an inter-cluster edge.
There are several cases.
Let $u$ be in the cluster $C_i$ and $v$ be in the cluster $C_j$.

Case 1.1: $C_j=\p_{T}(C_i)$ and there is some $(p,q)$ after $(u,v)$ in $\hat{A}$ satisfying $q=v$.
Suppose $C_i=\child_{\p_T}(C_j,l)$ for some $l$.
If there is some $(p,q)$ after $(u,v)$ in $\hat{A}$ satisfying $q=v$, then there must be a $C_r$ which contains $p$, and $\p_T(C_r)=C_j$, and $C_r=\child_{\p_T}(C_j,l')$ for some $l'>l$.
This means that $(x,y)=g(C_j,\child_{\p_T}(C_j,l+1))$ satisfies that $x=v$.
Since in $\bar{A}$, $(C_j,\child_{\p_T}(C_j,l+1))$ directly follows $(C_i,C_j)$, $(x,y)$ directly follows $(u,v)$ in $\hat{A}$, and thus $(x,y)$ directly follows $(u,v)$ in $A'$ as well.
Since $x=v$, $(u,v),(x,y)$ is a connected path in $A'$.

Case 1.2: $C_j=\p_{T}(C_i)$ and there is no $(p,q)$ after $(u,v)$ in $\hat{A}$ satisfying $q=v$.
Suppose $C_i$ is the last child of $C_j$.
Then $A_v$ must be a suffix of $A_j$.
If $C_j$ is the root of $T$, then $A_v$ is a suffix of $A'$, and since $A'$ starts with a node which is also the first node in $A_j$, and $A_j$ itself is a cycle, we know that it is valid to put $A_v$ at the end of $A'$.
Otherwise, the edge follow $(C_i,C_j)$ in $\bar{A}$ is $(C_j,\p_T(C_j))$
Let $(x,y)=g(\p_T(C_j),C_j)$.
Since we circularly shifted $A_j$ to make $A_j$ be an Euler tour of $T_j$ with respect to the root $y$, it means that the first entry in $A_j$ should be $(y,\cdot)$ (i.e., started from $y$), and the last entry in $A_j$ should be $(\cdot,y)$ (i.e., ended with $y$).
Since $(C_j,\p_T(C_j))$ follows $(C_i,C_j)$ in $\bar{A}$, we have $(y,x)$ follows $(u,v)$ in $\hat{A}$.
By our construction of $A'$, we inserted $A_v$ between $(u,v)$ and $(y,x)$.
Since $A_v$ starts from $v$ (by our construction) and ends in $y$ (since $A_v$ is a suffix of $A_j$), $(u,v),A_v,(y,x)$ is a connected path in $A'$.

Suppose $C_i$ is not the last child of $C_j$ and $C_i=\child_{\p_T}(C_j,l)$ for some $l$.
Then the edge that follows $(C_i,C_j)$ in $\bar{A}$ must be $(C_j,\child_{\p_T}(C_j,l+1))$.
Let $(x,y)=g(C_j,\child_{\p_T}(C_j,l+1))$.
By our construction of $A_v$, we know that $A_v$ must end at some node in $\hat{V}$.
In the following, we show that $A_v$ must end in $x$.
Firstly, we have $\first_{A_j}(x)>\first_{A_j}(v)$ since this is how we used to sort all children of $C_j$ in $T$.
Then, if $A_x$ ends in $z\in\hat{V}$ which is between $\first_{A_j}(x)$ and $\first_{A_j}(v)$, then it means that there is some cluster $C_r$ containing $z$ such that $\p_{T}(C_r)=C_j$ and $g(C_j,C_r)=(z,z')$, and in addition, we have $\first_{A_j}(x)<\first_{A_j}(z)<\first_{A_j}(v)$.
This implies that the rank of $C_r$ among children of $C_j$ should be between $l$ and $l+1$ which leads to a contradiction.
Therefore, $(u,v),A_v,(x,y)$ is a connected path in $A'$.

Case 2.1: $C_i=\p_{T}(C_j)$ and there is some $(p,q)$ after $(u,v)$ in $\hat{A}$ satisfying $q=v$.
In this case, it implies that $C_j$ cannot be a leaf because we should be able to find $C_r$ such that $C_r$ contains $p$, $g(C_r,C_j)=(p,q)$ and $\p_T(C_r)=C_j$.
Note that we circular shifted $A_j$ such that $A_j$ starts from $v$.
Based on how we sorted the children of $C_j$, we now that $g(C_j,\child(C_j,1))$ should be some $(x,y)$ where $x=v$.
In $\bar{A}$, $(C_j,\child(C_j,1))$ should follow $(C_i,C_j)$ immediately, which means $(x,y)$ follows $(u,v)$ $\hat{A}$ as well as $A'$.
Since $v=x$, $(u,v),(x,y)$ is a connected path in $A'$.

Case 2.2: $C_i=\p_{T}(C_j)$ and there is no $(p,q)$ after $(u,v)$ in $\hat{A}$ satisfying $q=v$.
Note that we circular shifted $A_j$ such that $A_j$ starts from $v$.
If $C_j$ is a leaf in $T$, then the edge in $\bar{A}$ following $(C_i,C_j)$ is $(C_j,C_i)$ and thus, the edge in $\hat{A}$ following $(u,v)$ is $(v,u)$.
Since $A_j$ is a cycle starting from $v$, we have $(u,v),A_j,(v,u)$ in $A'$ which is a connected path (or cycle).

If $C_j$ is not a leaf in $T$, the edge $(C_j,\child_{\p_T}(C_j,1))$ should directly follow $(C_i,C_j)$ in $\bar{A}$ and thus $(x,y) = g(C_j,\child_{\p_T}(C_j,1))$ directly follows $(u,v)$ in $\hat{A}$.
Since $A_j$ starts from $v$, we have $A_v$ is a prefix of $A_j$.
If $A_v$ ends in some $z\in\hat{V}$ which is before $\first_{A_j}(x)$, then there must be a cluster $C_r$ such that $g(C_j,C_r)=(z,z')$ which implies that $C_r$ should have smaller than rank than $\child_{\p_T}(C_j,1)$ which contradicts to the definition of $\child_{\p_T}(C_j,1)$.
Therefore $A_v$ must ends in $x$ which implies that $(u,v),A_j,(x,y)$ is a connected path in $A'$.

Put them together.
Since each $(u,v)$ in $\hat{A}$ can find a valid path in $A'$ to the following $(v,p)$ in $\hat{A}$, $A'$ is indeed a cycle and thus $A'$ is Euler tour of $T'$.

Given (1) a partition $\cC=\{C_1,C_2,\cdots, C_k\}$ over a set of $n$ nodes $V$, (2) a spanning tree $T=(\cC,E)$ over $\cC$ and an arbitrary Euler tour $A$ of $T$, (3) an edge mapping $g$ where $\forall \{C_i,C_j\}\in E,g(e)=\{x,y\}$ and $x\in C_i,y\in C_j$, and (4) spanning trees $T_1,T_2,\cdots,T_k$ and corresponding Euler tours $A_1,A_2,\cdots,A_k$ for $C_1,C_2,\cdots, C_k$ respectively, there is an MPC algorithm (Algorithm <ref>) that outputs a spanning tree $T'$ over $V$ and an Euler tour $A'$ of $T'$ using $O(1)$ rounds and $O(n)$ total space where the edges of $T'$ is the union of edges in $T_1,T_2,\cdots,T_k$ and edges $\{g(e)\mid e\in E\}$.
In addition, the algorithm is fully scalable.

The correctness of Algorithm <ref> is proved by Lemma <ref>.
In the remaining of the proof, we show how to implement Algorithm <ref> in the MPC model using $O(1)$ rounds, $O(n)$ total space, and make the implemented algorithm fully scalable.

Computing $\hat{E}$ only require simultaneously access $g(e)$ for each $e\in E$.
According to Theorem <ref>, this step only takes $O(1)$ rounds and $O(n)$ total space.
Computing $T'$ only requires local computation (i.e., renaming the tuples).
To compute $\hat{V}$, for each $\{x,y\}\in E$, it generates $x$ and $y$.
This only requires local computation.
Then we run sorting (Theorem <ref>) to remove duplicates.