# Distributed Approximation Algorithms for Steiner Tree in the
$\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$ model

Parikshit Saikia1 and Sushanta Karmakar1<EMAIL_ADDRESS><EMAIL_ADDRESS>
1Department of Computer Science and Engineering
Indian Institute of Technology Guwahati, India, 781039

###### Abstract

The _Steiner tree_ problem is one of the fundamental and classical problems in
combinatorial optimization. In this paper we study this problem in the
$\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$ model of distributed computing and
present two deterministic distributed approximation algorithms for the same.
The first algorithm computes a Steiner tree in $\tilde{O}(n^{1/3})$ rounds and
$\tilde{O}(n^{7/3})$ messages for a given connected undirected weighted graph
of $n$ nodes. Note here that $\tilde{O}(\cdot)$ notation hides polylogarithmic
factors in $n$. The second one computes a Steiner tree in $O(S+\log\log n)$
rounds and $O(S(n-t)^{2}+n^{2})$ messages, where $S$ and $t$ are the _shortest
path diameter_ and the number of _terminal_ nodes respectively in the given
input graph. Both the algorithms admit an approximation factor of
$2(1-1/\ell)$, where $\ell$ is the number of terminal leaf nodes in the
optimal Steiner tree. For graphs with $S=\omega(n^{1/3}\log n)$, the first
algorithm exhibits better performance than the second one in terms of the
round complexity. On the other hand, for graphs with $S=\tilde{o}(n^{1/3})$,
the second algorithm outperforms the first one in terms of the round
complexity. In fact when $S=O(\log\log n)$ then the second algorithm admits a
round complexity of $O(\log\log n)$ and message complexity of
$\tilde{O}(n^{2})$. To the best of our knowledge, this is the first work to
study the Steiner tree problem in the $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$
model.

###### keywords:

Steiner tree, shortest path forest, $\mathcal{CONGESTED}$ $\mathcal{CLIQIUE}$,
distributed approximation algorithm

##  1 Introduction

The $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$ model (CCM) is one of the
fundamental models in distributed computing that was first introduced by
Lotker et al. [1]. In this model nodes can communicate with each other via an
underlying communication network, which is a _clique_. Communication happens
in synchronous rounds and a pair of nodes can exchange $b$ bits in a round. In
this paper we assume that $b=O(\log n)$, where $n$ is the number of nodes in
the communication network. In literature there are two other classic models of
distributed computing, namely $\mathcal{LOCAL}$ and $\mathcal{CONGEST}$. The
$\mathcal{LOCAL}$ model of distributed computing mainly focuses on _locality_
111In distributed computing the _locality_ means processors are restricted to
collecting data from others which are at a distance of $x$ hops in $x$ time
units. The issue of locality is, to what extent a global solution to a
computational problem can be obtained from locally available data [2]. and
ignores the congestion by allowing messages of unlimited sizes to be
communicated [3, 2]. The $\mathcal{CONGEST}$ model on the other hand
simultaneously considers the congestion (by bounding the transmitted message
size) and locality. In contrast, the CCM takes locality out of the picture and
solely focuses on congestion. Since in CCM the hop diameter is _one_ therefore
nodes can directly communicate with each other and in each round they can
together exchange $O(n^{2}\log n)$ bits. Note that in all the above three
models of distributed computing, nodes (processors) are considered
computationally unbounded.

The $n$ nodes and a subset of the edges of the communication network form the
_input graph_ in the CCM. In the input graph each node has a unique identity
(ID) and it knows the weights of all the edges incident on it. In this paper
we study a classical combinatorial optimization problem, the _Steiner tree_
problem, in the CCM. It is defined as follows.

######  Definition 1.1 (Steiner tree (ST) problem).

Given a connected undirected graph $G=(V,E)$ and a weight function
$w:E\rightarrow\mathbb{R}^{+}$, and a set of vertices $Z\subseteq V$, known as
the set of terminals, the goal of the ST problem is to find a tree
$T^{\prime}=(V^{\prime},E^{\prime})$ such that $\sum_{e\in E^{\prime}}w(e)$ is
minimized subject to $Z\subseteq V^{\prime}\subseteq V$ and
$E^{\prime}\subseteq E$.

The set $V\setminus Z$ is known as the set of _non-terminals_ or _Steiner_
nodes. Note that if $|Z|=2$ then the ST problem reduces to the problem of
finding shortest-path between two distinct nodes in the network. On the other
hand if $|Z|=|V|$ then the ST problem becomes the minimum spanning tree (MST)
problem. Specifically the ST problem is a generalized version of the MST
problem. It is known that both MST and the shortest path problem can be solved
in polynomial time whereas the ST problem is one of the original 21 problems
proved NP-complete by Karp [4] (in the centralized setting). The best known
(polynomial time) approximation ratio for solving the ST problem in the
centralized setting is $\ln(4)+\epsilon\approx 1.386+\epsilon$, for
$\epsilon>0$ due to Byrka et al. [5]. It is also known that the ST problem can
not be solved in polynomial time with an approximation factor
$\leq\frac{96}{95}$ unless $P=NP$ [6].

The ST problem finds applications in numerous areas such as the VLSI layout
design, communication networks, transportation networks, content distribution
(video on demand, streaming multicast) networks, phylogenetic tree
reconstruction in computational biology etc. Moreover the ST problem appears
as a subproblem or as a special case of many other problems in network design
such as Steiner forest, prize-collecting Steiner tree etc. There are many
variations of the ST problem such as directed Steiner tree, metric Steiner
tree, euclidean Steiner tree, rectilinear Steiner tree, and so on. Hauptmann
and Karpinaski [7] provide a website with continuously updated state of the
art results for many variants of the problem.

Motivation. The motivation behind the study of the CCM is to understand the
role of congestion in distributed computing. There has been a lot of progress
in solving various problems in the CCM including minimum spanning tree (MST)
[1, 8, 9, 10], facility location [11, 12], shortest paths and distances [13,
14, 15], subgraph detection [16], triangle finding [16, 17], sorting [18, 19],
routing [19], and ruling sets [8, 11]. Recently Pai and Pemmaraju [20] studied
the _graph connectivity_ lower bounds in the CCM. Specifically they showed
that the lower bound round complexity for graph connectivity problem in the
BCCM($1$)222In literature the CCM is classified into two types namely
$\mathcal{BROADCAST}$ $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$ model (BCCM)
and $\mathcal{UNICAST}$ $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$ model (UCCM)
[21]. In BCCM($b$) each node can only broadcast a single $b$-bit message over
each of its incident links in each round. On the other hand the $b$-bits UCCM
(UCCM($b$)) allows each node to send a possibly different $b$-bit message over
each of its incident links in the network in each round., which is
$\Omega(\log n)$, holds for both deterministic as well as constant-error
randomized Monte Carlo algorithms [20]. Despite the fact that the ST problem
has been extensively studied in the $\mathcal{CONGEST}$ model of distributed
computing [22, 23, 24, 25, 26], to the best of our knowledge, such a study has
not been carried out in the CCM. The best deterministic round complexity for
solving the ST problem in the $\mathcal{CONGEST}$ model was recently proposed
by Saikia and Karmakar [26], which is $O(S+\sqrt{n}\log^{*}n)$ with the
approximation factor of $2(1-1/\ell)$, where $S$ is the _shortest path
diameter_ 333The term _shortest path diameter_ was first introduced by Khan
and Pandurangan [27]. (the definition is deferred to Section 2) of a graph and
$\ell$ is the number of terminal leaf nodes in the optimal ST, which improves
the previous best round complexity of the ST problem [25]. The MST problem is
a special case of the ST problem and has been extensively studied in the
$\mathcal{CONGEST}$ model as well as in the CCM. The best deterministic round
complexity known so far for solving the MST problem in the CCM is due to
Lotker et al. [1], which is $O(\log\log n)$. The algorithm in [1] has a
message complexity of $O(n^{2})$. There are other algorithms for the MST
problem in the CCM that are randomized in nature with the round complexities
of $O(\log\log\log n)$ [28] and $O(\log^{*}n)$ [29, 9]. The message
complexities of the algorithms in [28], [9], and [29] are $O(n^{2})$,
$O(n^{2})$, and $o(m)$ respectively. Here $m=|E|$. Recently Jurdziński and
Nowicki [10] achieved a randomized algorithm that constructs an MST in $O(1)$
rounds in the CCM with high probability. Therefore an intriguing question is:

“What is the best round complexity that can be achieved in solving the ST
problem in the CCM while maintaining an approximation factor of at most $2$?”

In CCM, one can trivially compute an ST in $O(n)$ rounds by maintaining an
approximation factor of at most $2$. It can be computed as follows. One can
collect the entire topology of the input graph in a special node $r$, which
takes $O(n)$ rounds. Then we can compute an ST by applying one of the best
known centralized ST algorithms [30, 31, 5] whose approximation factor is at
most $2$, and finally inform each of the nodes involved with the resultant ST.
Note that the resultant ST has at most $n-1$ edge information which can be
decomposed into $O(n)$ messages. Therefore $r$ can perform the final step in
$O(1)$ rounds by sending each edge of the resultant ST to a different
intermediate node, which will eventually sends to the destined node.

Our contribution. In this work we propose two non-trivial deterministic
distributed approximation algorithms for the ST problem in the CCM. Both the
algorithms admit an approximation factor of $2(1-1/\ell)$. The first one,
which will be denoted by STCCM-A, computes an ST in $\tilde{O}(n^{1/3})$
rounds and $\tilde{O}(n^{7/3})$ messages. We also propose a deterministic
distributed _shortest path forest_ (SPF) (the definition is deferred to
Section 3) algorithm in the CCM (henceforth it will be denoted by SPF-A) that
computes a SPF in $O(n^{1/3}\log n)$ rounds and $O(n^{7/3}\log n)$ messages
which will be used as a subroutine in the proposed STCCM-A algorithm. The
SPF-A algorithm is based on an _all pairs shortest path_ (APSP) algorithm in
the CCM due to Censor-Hillel et al. [13]. The first contribution of this paper
is summarized in the following theorem.

######  Theorem 1.1.

Given a connected undirected weighted graph $G=(V,E,w)$ and a terminal set
$Z\subseteq V$, there exists an algorithm that computes an ST in
$\tilde{O}(n^{1/3})$ rounds and $\tilde{O}(n^{7/3})$ messages in the CCM with
an approximation factor of $2(1-1/\ell)$, where $\ell$ is the number of
terminal leaf nodes in the optimal ST.

The proposed STCCM-A algorithm is inspired by an algorithm proposed in [26].
It consists of four steps (each step is a small distributed algorithm)– the
first step is to build a SPF $G_{F}$ of the input graph $G$ for a given
terminal set $Z$, which is essentially a partition of the graph $G$ into
disjoint trees: Each partition contains exactly one terminal and a subset of
non-terminals. A non-terminal $v$ joins a partition containing the terminal
$z\in Z$ if and only if $\forall x\in Z\setminus\\{z\\}$, $d(z,v)\leq
d(x,v)$.444$d(u,v)$ denotes the (weighted) shortest distance between nodes $u$
and $v$ in graph $G$. In the second step the weights of the edges of $G$ with
respect to the SPF $G_{F}$ are suitably changed, which produces a modified
graph $G_{c}$; in the third step the MST algorithm proposed by Lotker et al.
[1] is applied on the graph $G_{c}$ to build an MST $T_{M}$; and finally some
edges are pruned from $T_{M}$ in such a way that in the remaining tree $T_{Z}$
(which is the required ST) all leaves are terminal nodes.

The second proposed algorithm for the ST problem in the CCM, which will be
denoted by STCCM-B, computes a $2(1-1/\ell)$-approximate ST in $O(S+\log\log
n)$ rounds and $O(S(n-t)^{2}+n^{2})$ messages. Similar to the STCCM-A
algorithm, the STCCM-B algorithm also consists of four steps. Except the step
$1$, all other steps in STCCM-B algorithm are same as that of the STCCM-A
algorithm. For step $1$ in the STCCM-B algorithm, which is the SPF
construction, we propose another SPF algorithm in the CCM (henceforth it will
be denoted by SPF-B) that computes a SPF in $O(S)$ rounds and
$O(S(n-t)^{2}+nt)$ messages. The second contribution of this paper is
summarized in the following theorem.

######  Theorem 1.2.

Given a connected undirected weighted graph $G=(V,E,w)$ and a terminal set
$Z\subseteq V$, there exists an algorithm that computes an ST in $O(S+\log\log
n)$ rounds and $O(S(n-t)^{2}+n^{2})$ messages in the CCM with an approximation
factor of $2(1-1/\ell)$, where $n>t$, $S$ is the shortest path diameter of
$G$, and $\ell$ is the number of terminal leaf nodes in the optimal ST.

As a by-product of the above theorem, for constant or sufficiently small
shortest path diameter networks (where $S=O(\log\log n)$) the following
corollary holds.

######  Corollary 1.3.

If $S=O(\log\log n)$ then a $2(1-\frac{1}{\ell})$-approximate ST can be
deterministically computed in $O(\log\log n)$ rounds and $\tilde{O}(n^{2})$
messages in the CCM.

The above round and message complexities of the STCCM-B algorithm almost
coincide with the best known deterministic result for MST construction in the
CCM due to Lotker et al. [1] and the approximation factor of the resultant ST
is at most $2(1-1/\ell)$ of the optimal.

Related work. Chen et al. [22] proposed the first deterministic distributed
algorithm for the ST problem in the $\mathcal{CONGEST}$ model and achieved an
approximation factor of $2(1-1/\ell)$. The time and message complexities of
this algorithm are $O(n(n-t))$ and $O(m+n(n-t+\log n))$ respectively.
Chalermsook et al. [23] presented a deterministic distributed $2$-approximate
algorithm for the ST problem in the synchronous model (which allows a bounded
message size only) with time and message complexities of $O(n\log n)$ and
$O(tn^{2})$ respectively. Khan et al. [24] presented an $O(\log
n)$-approximate randomized distributed algorithm for the ST problem in the
$\mathcal{CONGEST}$ model with time complexity $O(S\log^{2}n)$ and message
complexity $O(Sn\log n)$. Lenzen and Patt-Shamir [25] presented two
distributed algorithms for the Steiner forest problem (a more generalized
version of the ST problem) in the $\mathcal{CONGEST}$ model: one is
deterministic and the other one is randomized. The former one finds, a
$(2+o(1))$-approximate Steiner forest in
$\tilde{O}(\sqrt{\min\\{D,k\\}}(D+k)+S+\sqrt{\min\\{St,n\\}})$ rounds, where
$D$ is the unweighted diameter and $k$ is the number of terminal components in
the given input graph. The latter one finds a $(2+o(1))$-approximate Steiner
forest in $\tilde{O}(\sqrt{\min\\{D,k\\}}(D+k)+\sqrt{n})$ rounds with high
probability. Note that if $k=1$ then the Steiner forest problem reduces to the
ST problem. In this case the round complexities of the two algorithms in [25],
in which one is deterministic and the other one is randomized reduce to
$\tilde{O}(S+\sqrt{\min\\{St,n\\}})$ and $\tilde{O}(D+\sqrt{n})$ respectively.
Saikia and Karmakar [26] proposed a deterministic distributed
$2(1-1/\ell)$-factor approximation algorithm for the ST problem in the
$\mathcal{CONGEST}$ model with the round and message complexities of
$O(S+\sqrt{n}\log^{*}n)$ and $O(\Delta(n-t)S+n^{3/2})$ respectively, where
$\Delta$ is the maximum degree of a node in the graph. Recently Bachrach et
al. [32] showed that the lower bound round complexity in solving the ST
problem exactly in the $\mathcal{CONGEST}$ model is $\Omega(n^{2}/\log^{2}n)$.
In the approximate sense on the other hand, no immediate lower bound result
exists for solving the ST problem in the $\mathcal{CONGEST}$ model. Since the
ST problem is a generalized version of the MST problem, we believe that in the
approximate sense the lower bound results for the MST problem555Das Sarma et
al. [33] showed that approximating (for any factor $\alpha\geq 1$) MST
requires $\Omega(D+\sqrt{n/(B\log n)})$ rounds (assuming $B$ bits can be sent
through each edge in each round) in the $\mathcal{CONGEST}$ model. Kutten et
al. [34] established that $\Omega(m)$ is the message lower bound for leader
election in the $KT_{0}$ model (i.e. Knowledge Till radius 0) which holds for
both the deterministic as well as randomized (Monte Carlo) algorithms even if
the network parameters $D$, $n$, and $m$ are known, and all the nodes wake up
simultaneously. Since a distributed MST algorithm can be used to elect a
leader, the above message lower bound in the $KT_{0}$ model also applies to
the distributed MST construction. also hold for the ST problem in the
$\mathcal{CONGEST}$ model.

References | Model | Type | Round complexity | Message complexity | Approximation
---|---|---|---|---|---
Chen et al. [22] | CM | DT | $O(n(n-t))$ | $O(m+n(n-t+\log n))$ | $2(1-1/\ell)$
Chalermsook et al. [23] | CM | DT | $O(n\log n)$ | $O(tn^{2})$ | $2$
Khan et al. [24] | CM | RM | $O(S\log^{2}n)$ | $O(Sn\log n)$ | $O(\log n)$
Lenzen and Patt-Shamir [25] | CM | DT | $\tilde{O}(S+\sqrt{min\\{st,n\\}})$ | - | $2+o(1)$
RM | $\tilde{O}(D+\sqrt{n})$ | - | $2+o(1)$
Saikia and Karmakar [26] | CM | DT | $O(S+\sqrt{n}\log^{*}n)$ | $O(\Delta(n-t)S+n^{3/2})$ | $2(1-1/\ell)$
this paper | CCM | DT | $\tilde{O}(n^{1/3})$ | $\tilde{O}(n^{7/3})$ | $2(1-1/\ell)$
$O(S+\log\log n)$ | $O(S(n-t)^{2}+n^{2})$ | $2(1-1/\ell)$
Table 1:  Summary of results for Steiner tree problem in distributed setting.
Here CM = $\mathcal{CONGEST}$ model, DT = deterministic, RM = randomized,
$n=|V|$, $m=|E|$, $t=|Z|$, $n>t$, $S$ and $D$ are the shortest path diameter
and the unweighted diameter respectively of a connected undirected weighted
graph $G$.

Performances of some of the distributed algorithms mentioned above, together
with that of our work, are summarized in Table 1.

Paper organization. The rest of the paper is organized as follows. In Section
2 we define the system model and notations. The description of the SPF-A
algorithm is given in Section 3. The description of the STCCM-A algorithm and
an illustrative example of it are given in Section 4. The proof of the STCCM-A
algorithm is given in Section 5. The description and proof of the STCCM-B
algorithm are given in Section 6. A brief description of the Censor-Hillel et
al.’s APSP algorithm and Lotker et al’s MST algorithm are deferred to A and B
respectively. We conclude the paper in Section 7.

##  2 Model and notations

System model. We consider the CCM as specified in [1]. This model consists of
a complete network described by a _clique_ of $n$ nodes. Each node represents
an independent computing entity (processor). Nodes are connected through a
point-to-point network of $n\choose 2$ bidirectional communication links. The
bandwidth of each of the communication links is bounded by $O(\log n)$ bits.

At the beginning of the computation, each node knows its own (unique) identity
(ID) which can be represented by $O(\log n)$ bits and the part of the input
assigned to it.666In this paper, we assume that initially each node knows only
its own identity and weights of all the edges incident on it; nodes do not
have initial knowledge of the identifiers of their neighbors and other nodes.
This is known as the $KT_{0}$ model, also called the _clean network model_
[35]. On the other hand if each node has initial knowledge of itself and the
identifiers of its neighbors then such a model is known as the $KT_{1}$ model
(i.e. Knowledge Till radius 1). In $KT_{1}$ model only the knowledge of the
identifiers of neighbors is assumed, not other information such as the
incident edges of the neighbors. In the CCM the _input graph_ $G$ and the
underlying _communication network_ , which is a clique, are not same. The
input graph $G$ is distributed among the nodes (processors) of the clique via
a vertex partition. In this paper we consider that each vertex of $G$ along
with its incident edges (with their weights) are assigned to a distinct node
(processor) in the clique. If an edge does not exist in $G$ then the weight of
such an edge is considered equal to $\infty$ in the clique. Communication
happens in synchronous rounds and a pair of nodes can exchange $O(\log n)$
bits in each round. Nodes communicate and coordinate their actions with other
nodes by passing messages (of size $O(\log n)$ bits) only. In general, a
message contains a constant number of edge weights, node IDs, and other
arguments (each of them is polynomially bounded in $n$). Note here that each
of the arguments in a message is polynomially bounded in $n$ and therefore
polynomially many sums of arguments can be encoded with $O(\log n)$ bits. We
assume that nodes and links do not fail.

An execution of the system advances in synchronous rounds. In each round:
nodes receive messages that were sent to them in the previous round, perform
some local computation, and then send (possibly different) messages. The time
complexity is measured by the number of rounds required until all the nodes
(explicitly) terminate. The message complexity is measured by the number of
messages sent until all the nodes (explicitly) terminate.

Notations. We use the following terms and notations.

  * 1.

$\mathit{\delta(v)}$ denotes the set of edges incident on a node $v$.
Similarly $\delta(C)$ denotes the set of edges having exactly one endpoint in
a subgraph $C$.

  * 2.

$w(e)$ denotes the weight of an edge $e$.

  * 3.

$\mathit{ES(e)}$ denotes the state of an edge $e$.

  * 4.

$s(v)$ denotes the source node of a node $v$.

  * 5.

$d(v)$ denotes the shortest distance from a node $v$ to its source ID $s(v)$.

  * 6.

$\pi(v)$ denotes the predecessor node of a node $v$.

  * 7.

Let $M_{n\times n}$ denotes a matrix of size $n\times n$, where $n$ is a
positive integer. Then $m(i,j)$ denotes the value of an entry located at the
$i^{th}$ row and $j^{th}$ column in $M_{n\times n}$.

  * 8.

$\langle X\rangle$ denotes the message $X(a_{1},a_{2},...)$. Here
$a_{1},a_{2},...$ are the arguments of the message $X$. Note that unless it is
necessary, arguments of $\langle X\rangle$ will not be shown in it.

##  3 SPF construction in CCM

The SPF is defined as follows.

######  Definition 3.1 (SPF [22]).

Let $G=(V,E,w)$ be a connected undirected weighted graph, where $V$ is the
vertex set, $E$ is the edge set, and $w:E\rightarrow\mathbb{R}^{+}$ is the
non-negative weight function. Given a subset $Z\subseteq V$, a SPF for $Z$ in
$G$ is a sub-graph $G_{F}=(V,E_{F},w)$ of $G$ consisting of disjoint trees
$T_{i}=(V_{i},E_{i},w)$, $i=1,2,...,|Z|$ such that

  * 1.

for all $i$, $V_{i}$ contains exactly one node $z_{i}$ of $Z$.

  * 2.

if $v\in V_{i}$ then its $s(v)$ in $G$ is $z_{i}\in Z$.

  * 3.

$V_{1}\cup V_{2}\cup...V_{|Z|}=V$ and $V_{i}\cap V_{j}=\phi$ for all $i\neq
j$.

  * 4.

$E_{1}\cup E_{2}\cup...E_{|Z|}=E_{F}\subseteq E$.

  * 5.

The shortest path between $v$ and $s(v)=z_{i}$ in $T_{i}$ is the shortest path
between $v$ and $s(v)$ in $G$.

###  3.1 SPF-A algorithm

The SPF-A algorithm is used as a subroutine in the proposed STCCM-A algorithm.
Here we give a brief description of it. It consists of two parts: the first
part constructs an APSP of the input graph $G$ and the second part constructs
the required SPF from the graph formed by the APSP. Specifically, in the first
part we apply the algebraic method due to Censor-Hillel et al. [13]. Censor-
Hillel et al. showed that in the CCM, the iterated squaring of the weight
matrix over the _min-plus semiring_ [36, 37] computes an APSP in
$O(n^{1/3}\log n)$ rounds and $O(n^{7/3}\log n)$ messages. One of the
fundamental applications of the APSP is the construction of the routing tables
in a network. Specifically a routing table entry denoted by $R[u,v]=w\in V$ is
a node such that $(u,w)\in E$ and $w$ lies on a shortest path from $u$ to $v$.
Censor-Hillel et al. also showed that in the CCM the iterated squaring
algorithm can be used to construct routing tables of a network as well. For
the sake of completeness a brief description of the iterated squaring
algorithm and the procedure of the routing table construction due to Censor-
Hillel et al. is provided in A.

Now we describe the second part of the SPF-A algorithm and show that it
requires $O(1)$ rounds and $O(n)$ messages. From the first part we assume that
each node in $V$ knows the shortest path distances to all other nodes in $V$
and its routing table entries $R$. Therefore, by using the shortest path
distance information each node $v\in V\setminus Z$ can locally choose the
closest terminal as its source node $s(v)$. Note that there may be more than
one terminal with equal shortest distances for a given non-terminal. In this
case, the non-terminal chooses the one with the smallest ID among all such
terminals. Once a non-terminal $v$ chooses the closest terminal as its source
node $s(v)$, by using its own routing table $R$, it can also choose its parent
node $\pi(v)$ with respect to $s(v)$. Whenever a non-terminal $v$ sets its
$\pi(v)$, it also informs $\pi(v)$ that it has chosen $\pi(v)$ as its parent.
It is obvious that to establish the parent-child relationship between a pair
of nodes $(\pi(v),v)$, where $s(v)=s(\pi(v))$, it requires $O(1)$ rounds and
$O(1)$ messages. In this way each node $v\in V\setminus Z$ is connected to
exactly one tree rooted at some source node $s(v)$. Here each source node is a
terminal. Therefore exactly $|Z|$ number of shortest path trees are
constructed by the above procedure which together form the required SPF. Since
the procedure of choosing parent can be started in parallel by all nodes in
$V\setminus Z$, for all such pair of nodes it requires $O(1)$ rounds and
$O(n)$ messages. It is clear that the overall round and message complexities
of the SPF-A algorithm are dominated by the first part of the algorithm.
Therefore the following theorem holds.

######  Theorem 3.1.

A SPF can be deterministically computed in $\tilde{O}(n^{1/3})$ rounds and
$\tilde{O}(n^{7/3})$ messages in the CCM.

The correctness of the SPF-A algorithm directly follows from the correctness
of the algorithm proposed by Censor-Hillel et al. [13].

##  4 STCCM-A algorithm

###  4.1 Preliminaries

######  Definition 4.1.

(Complete distance graph) A graph $K_{Z}$ is called a complete distance graph
on the node set $Z\subseteq V$ of a connected undirected weighted graph
$G=(V,E,w)$ only if for each pair of nodes $u,v\in Z$, there is an edge
$(u,v)$ in $K_{Z}$ and the weight of the edge $(u,v)$ is the length of the
shortest path between $u$ and $v$ in $G$.

The approximation factor of the proposed STCCM-A algorithm directly follows
from the correctness of a centralized algorithm due to Kou et al. [30]
(Algorithm H). For a given connected undirected weighted graph $G=(V,E,w)$ and
a set of terminals $Z\subseteq V$, the Algorithm H computes an ST $T_{Z}$ as
follows.

  1. 1.

Construct a complete distance graph $K_{Z}$.

  2. 2.

Find an MST $T_{A}$ of $K_{Z}$.

  3. 3.

Construct a sub-graph $G_{A}$ of $T_{A}$ by replacing each edge of $T_{A}$
with its corresponding shortest distance path in $G$.

  4. 4.

Find an MST $T_{B}$ of $G_{A}$.

  5. 5.

Construct an ST $T_{Z}$, from $T_{B}$ by deleting edges of $T_{B}$ so that all
leaves of $T_{Z}$ are terminals.

The running time of the Algorithm H is $O(tn^{2})$. Following the principles
of both Prim’s and Krushkal’s algorithms, Wu at el. [31] proposed a faster
centralized algorithm (Algorithm M) which improves the time complexity to
$O(m\log n)$, achieving the same approximation ratio as that of the Algorithm
H. The Algorithm M computes a sub-graph called generalized MST $T_{Z}$ for $Z$
of $G$ which is defined as follows.

######  Definition 4.2 (Generalized MST [31]).

Let $G=(V,E,w)$ be a connected undirected weighted graph and $Z$ be a subset
of $V$. Then a generalized MST $T_{Z}$ is a sub-graph of $G$ such that

  * 1.

there exists an MST $T_{A}$ of the complete distance graph $K_{Z}$ such that
for each edge $(u,v)$ in $T_{A}$, the length of the unique path in between $u$
and $v$ in $T_{Z}$ is equal to the weight of the edge $(u,v)$ in $T_{A}$.

  * 2.

all leaves of $T_{Z}$ are in $Z$.

It is clear that $T_{Z}$ is an ST for $Z$ in $G$ and is the actual realization
of $T_{A}$ (Recall that $T_{A}$ is the MST of $K_{Z}$). In summary, the
Algorithm M constructs a generalized MST $T_{Z}$ for $Z$ of $G$ as follows.
Initially, the set of nodes in $Z$ are treated as a forest of $|Z|$ separate
trees and successively merge them until all of them are in a single tree
$T_{Z}$. A priority queue $Q$ is used to store the frontier vertices of paths
extended from the trees. Each tree gradually extends its branches into the
node set $V\setminus Z$. When two branches belonging to two different trees
meet at some node then they form a path through that node merging these two
trees. The algorithm always guarantees to compute only such paths of minimum
length for merging trees.

The proposed STCCM-A algorithm also computes a generalized MST for $Z$ of $G$
(which is essentially the required ST with the approximation factor of
$2(1-1/\ell)$) in the CCM. The round and message complexities of the STCCM-A
algorithm are $\tilde{O}(n^{1/3})$ and $\tilde{O}(n^{7/3})$ respectively.
Saikia and Karmakar [26] proposed a $2(1-1/\ell)$-factor deterministic
distributed approximation algorithm which also computes a generalized MST for
$Z$ of $G$ in $O(S+\sqrt{n}\log^{*}n)$ rounds and $O(\Delta(n-t)S+n^{3/2})$
messages. However, the algorithm in [26] was proposed for the
$\mathcal{CONGEST}$ model, whereas the STCCM-A algorithm is proposed for the
CCM.

There are four small distributed algorithms (step $1$ to step $4$) involved in
the STCCM-A algorithm similar to the algorithm proposed in [26]. However,
except the step $2$, all other steps in the STCCM-A algorithm are different
from the algorithm proposed in [26]. The step $2$ of the STCCM-A algorithm is
similar to that of the algorithm proposed in [26].

###  4.2 Outline of the STCCM-A algorithm

Input specification. We assume that there is a special node $r\in V$ available
at the start of the algorithm. For correctness we assume that $r$ is the node
with the smallest ID in the system. Initially each node $v\in V$ knows its
unique ID, whether it is a terminal or a non-terminal, and weight $w(e)$ of
each edge $e\in\mathit{\delta(v)}$. Each node in $\mathit{V}$ maintains a
boolean variable $\mathit{steiner\\_flag}$ whose values can be either
$\mathit{true}$ or $\mathit{false}$. Initially $\mathit{steiner\\_flag(v)}$ is
set to $\mathit{false}$ for each $\mathit{v\in V\setminus Z}$, whereas
throughout the execution of the algorithm the value of
$\mathit{steiner\\_flag(v)}$ is $\mathit{true}$ for each $\mathit{v\in Z}$.
Also each node $v\in V$ initially sets its local variable $\mathit{ES(e)}$ to
$\mathit{basic}$ for each $\mathit{e\in\delta(v)}$. Recall that
$\mathit{ES(e)}$ denotes the state of an edge $e$.

Output specification. Whenever the algorithm terminates, the pair
$\mathit{(steiner\\_flag,B)}$ at each node $v\in V$ defines the distributed
output of the algorithm. Here $\mathit{B\subseteq\delta(v)}$.
$\mathit{steiner\\_flag(v)=false}$ ensures that $v$ does not belong to the
final ST; in this case $B=\emptyset$. On the other hand
$\mathit{steiner\\_flag(v)=true}$ ensures that $v$ is a part of the final ST;
in this case $B\neq\emptyset$ and for each $e\in B$, $\mathit{ES(e)}$ is set
to $\mathit{branch}$.

The special node $r$ initiates the algorithm. An ordered execution of the
steps is necessary for the correct working of the STCCM-A algorithm. We assume
that $r$ ensures the ordered execution of the steps (step $1$ to step $4$) and
initiates the step $i+1$ after the step $i$ is terminated. The outline of the
proposed STCCM-A algorithm is as follows.

  1. Step 1.

SPF-construction. Construct a SPF $G_{F}=(V,E_{F},w)$ for $Z$ in $G$ by
applying the SPF-A algorithm described in Section 3.1. Theorem 3.1 ensures
that the round and message complexities of this step are $\tilde{O}(n^{1/3})$
and $\tilde{O}(n^{7/3})$ respectively.

  2. Step 2.

Edge Weight modification. With respect to the SPF $G_{F}$, each edge $e\in E$
of the graph $G=(V,E,w)$ is classified as any one of the following three
types.

    1. (a)

$\mathit{tree}$ edge: if $e\in E_{F}$.

    2. (b)

$\mathit{inter\\_tree}$ edge: if $e\notin E_{F}$ and end points are incident
in two different trees of the $G_{F}$.

    3. (c)

$\mathit{intra\\_tree}$ edge: if $e\notin E_{F}$ and end points are incident
in the same tree of the $G_{F}$.

Now transform $G=(V,E,w)$ into $G_{c}=(V,E,w_{c})$. The cost of each edge
$(u,v)\in E$ in $G_{c}$ is computed as follows.

    1. (a)

$w_{c}(u,v)=0$ if $(u,v)$ is a $\mathit{tree}$ edge.

    2. (b)

$w_{c}(u,v)=\infty$ if $(u,v)$ is an $\mathit{intra\\_tree}$ edge.

    3. (c)

$w_{c}(u,v)=d(u,s(u))+w(u,v)+d(v,s(v))$ if $(u,v)$ is an
$\mathit{inter\\_tree}$ edge. In this case $w_{c}(u,v)$ realizes the weight of
a path from the source node $s(u)$ to the source node $s(v)$ in $G$ that
contains the $\mathit{inter\\_tree}$ edge $(u,v)$. Recall that $d(u,v)$
denotes the (weighted) shortest distance between nodes $u$ and $v$ in $G$.

The classification of the edges of $G$ and the transformation to $G_{c}$ can
be done as follows. Each node $v$ of $G$ sends a message (say $\langle
set\\_category(v,s(v),d(v,s(v)),\pi(v))\rangle$) on all of its incident edges
with respect to the input graph $\mathit{G}$. Let a node $v$ receives $\langle
set\\_category(u,s(u),d(u,s(u)),\pi(u))\rangle$ on an incident edge $(v,u)$.
If $s(v)\neq s(u)$ then $v$ sets $(v,u)$ as an $\mathit{inter\\_tree}$ edge
and $w_{c}(v,u)$ to $d(v,s(v))+w(v,u)+d(u,s(u))$. On the other hand if
$s(v)=s(u)$ then $(v,u)$ can be either a $\mathit{tree}$ edge or an
$\mathit{intra\\_tree}$ edge: if $v=\pi(u)$ or $\pi(v)=u$ then $v$ sets
$(v,u)$ as $\mathit{tree}$ edge and $w_{c}(v,u)$ to $0$. Otherwise, $v$ sets
$(v,u)$ as $\mathit{intra\\_tree}$ edge and $w_{c}(v,u)$ to $\infty$.

It is clear that step $2$ can be performed in $O(1)$ rounds. Also on each edge
of $G$, the message $\langle set\\_category\rangle$ is sent exactly twice
(once from each end). Therefore, the message complexity of the step $2$ is
$O(m)$.

  3. Step 3.

MST construction. Construct an MST $\mathit{T_{M}}$ of $G_{c}$. In this step,
we apply the deterministic MST algorithm proposed by Lotker et al. [1] (a
brief description of the algorithm is deferred to B). To the best of our
knowledge, it is the only known deterministic MST algorithm proposed in the
CCM till date. All other existing MST algorithms in the CCM [28, 29, 9, 10]
are randomized in nature. Note that the round and message complexities of the
algorithm proposed by Lotker et al. are $O(\log\log n)$ and $O(n^{2})$
respectively.

We assume that each node $v\in V$ ($T_{M}$ contains all the nodes of $V$)
knows which of the edges in $\delta(v)$ are in the $\mathit{T_{M}}$ and for
each such edge $\mathit{e}$ it sets $\mathit{ES(e)}$ to $\mathit{branch}$. On
the other hand for each $\mathit{e\in\delta(v)}$ which is not in the
$\mathit{T_{M}}$, $v$ sets $\mathit{ES(e)}$ to $\mathit{basic}$.

  4. Step 4.

Pruning. Construct a generalized MST $T_{Z}$ by performing a pruning operation
on the MST $T_{M}$. For correctness we assume that a node in $Z$ with the
smallest ID is the root $r_{t}$ of $T_{M}$. The pruning operation deletes
edges from $T_{M}$ until all leaves are terminal nodes. It is performed as
follows. Each $v\in V$ sends its parent information (with respect to the
$T_{M}$ rooted at $r_{t}$) to all other nodes. This requires $O(1)$ rounds and
$O(n^{2})$ messages. Now each $v\in V\setminus Z$ locally computes the $T_{M}$
rooted at $r_{t}$ from these received parent information. Then each node in
$V\setminus Z$ can locally decide whether it should prune itself or not from
the $T_{M}$. From the locally known $T_{M}$ each $v\in V\setminus Z$ finds
whether it is an intermediate node in between two or more terminals in the
$T_{M}$ or not. If yes, it does not prune itself from the $T_{M}$ and sets its
$\mathit{steiner\\_flag}$ to $\mathit{true}$. Otherwise, it prunes itself.
Whenever a node $v$ prunes itself from the $\mathit{T_{M}}$ it sets its
$\mathit{steiner\\_flag}$ to $\mathit{false}$ and for each
$\mathit{e\in\delta(v)}$ such that $\mathit{ES(e)\neq basic}$, it sets its
$\mathit{ES(e)}$ to $\mathit{basic}$. On each such pruned edge $e$, $v$ asks
the other end of $e$ to prune the common edge $e$. Now the edge weights of
resultant ST $T_{Z}$ are restored to the original edge function $w$. Since
each node in $\mathit{V\setminus Z}$ can start the pruning operation in
parallel and in the worst-case the number of pruned edges in the network can
be at most $n$, this step takes $O(1)$ rounds and $O(n)$ messages.

The overall round and message complexities of the pruning step are $O(1)$ and
$O(n^{2})$ respectively.

The STCCM-A algorithm terminates with the step $4$.

Figure 2: (a) An arbitrary graph $G=(V,E,w)$ and a terminal set
$Z=\\{B,F,H\\}$. (b) The input graph $G$ is distributed among the processors
of a complete network $K_{9}$ via a vertex partition. (c) A SPF
$G_{F}=(V,E_{F},w)$ for $Z$ of $G$. The distances of nodes to their respective
sources are shown in the table. (d) The modified graph $G_{c}=(V,E,w_{c})$.
(e) An MST $T_{M}$ of $G_{c}$. (f) The final Steiner tree $T_{Z}$ (generalized
MST) for $Z$ of $G$.

Figure 2 (continued).

###  4.3 An illustrating example of the STCCM-A algorithm

Consider the application of the STCCM-A algorithm in an arbitrary graph
$G=(V,E,w)$ and a terminal set $Z=\\{B,F,H\\}$ shown in Figure 2(a). The input
graph $G$ is distributed among the nodes (processors) of a complete network
$K_{9}$ via a vertex partition which is shown in Figure 2(b). Specifically
each vertex and its incident edges (with weights) of $G$ are assigned to a
distinct processor in the $K_{9}$. The weight of an edge in $K_{9}$ which is
not in $G$ is considered equal to $\infty$ (not shown in the figure). A SPF
$G_{F}=(V,E_{F},w)$ for $Z$ is constructed which is shown in Figure 2(c). In
$G_{F}$, each non-terminal $v$ is connected to a terminal $s(v)\in Z$ whose
distance is minimum to $s(v)$ than any other terminal in $G$ which is shown in
the table of Figure 2(c). The modified graph $G_{c}$ and labelling of the edge
weights according to the definition of $G_{c}$ are shown in Figure 2(d).
Figure 2(e) shows after the application of the Lotker et al.’s MST algorithm
on $G_{c}$ which constructs an MST $T_{M}$ of $G_{c}$. The final Steiner tree
$T_{Z}$ for $Z$ of $G$, which is a generalized MST for $Z$ of $G$ is
constructed from the $T_{M}$ by applying the pruning step of the STCCM-A
algorithm, which is shown in Figure 2(f).

##  5 Proof of the STCCM-A algorithm

######  Theorem 5.1.

The round complexity of the STCCM-A algorithm is $\tilde{O}(n^{1/3})$.

###### Proof.

It is clear that the overall round complexity of the STCCM-A algorithm is
dominated by the step $1$. Therefore the round complexity of the STCCM-A
algorithm is $\tilde{O}(n^{1/3})$. The polylogarthmic factors involved with
this round complexity is $\log n$. ∎

######  Theorem 5.2.

The message complexity of the STCCM-A algorithm is $\tilde{O}(n^{7/3})$.

###### Proof.

By Theorem 3.1 the message complexity of the step 1 of the STCCM-A algorithm
is $\tilde{O}(n^{7/3})$. Each of the step 3 and step 4 requires $O(n^{2})$
messages. The step $2$ requires $O(m)$ messages. We know that $m\leq n^{2}$.
All of these ensures that the overall message complexity of the STCCM-A
algorithm is dominated by the step $1$. Therefore the message complexity of
the STCCM-A algorithm is $\tilde{O}(n^{7/3})$. The polylogarthmic factors
involved with this message complexity is $\log n$. ∎

######  Definition 5.1 (Straight path).

Given that $G=(V,E,w)$ is a connected undirected weighted graph and
$Z\subseteq V$. Let $u,v\in Z$. Then a path $P_{uv}$ between $u$ and $v$ is
called straight only if all the intermediate nodes in $P_{uv}$ (may contain no
intermediate node) are in $V\setminus Z$.

######  Lemma 5.3.

Given that $G=(V,E,w)$ is a connected undirected weighted graph and
$Z\subseteq V$. Let $u,v\in\mathit{Z}$ and there exists a straight path
$P_{uv}$ between $u$ and $v$ in $\mathit{T_{M}}$, where $T_{M}$ is a resultant
MST constructed after the consecutive applications of step $1$, $2$, and $3$
of the STCCM-A algorithm on the given graph $G$. Then $P_{uv}$ in $T_{M}$ is
the shortest straight path between $u$ and $v$ in $G$.

###### Proof.

By contradiction assume that $P_{uv}$ is not the shortest straight path in
$T_{M}$. Let there exists a straight path $P^{\prime}_{uv}$ between $u$ and
$v$ such that $P^{\prime}_{uv}<P_{uv}$. We show that $P^{\prime}_{uv}<P_{uv}$
does not hold. Since $u$ and $v$ are two different terminals they were in
different trees of the SPF, say $u\in\mathit{T_{1}}$ and $v\in\mathit{T_{2}}$,
before they are included in $\mathit{T=T_{1}\cup T_{2}}$. Let
$\mathit{e=(a,b)\in\delta(T_{1})\cap\delta(T_{2}),e^{\prime}=(a^{\prime},b^{\prime})\in\delta(T_{1})\cap\delta(T_{2})}$
such that $P_{uv}$ and $P^{\prime}_{uv}$ contain $e$ and $e^{\prime}$
respectively as shown in Figure 4. Note that the correctness of the SPF
algorithm described in Section 3.1 ensures that $P_{ua}$, $P_{ua^{\prime}}$,
$P_{vb}$, and $P_{vb^{\prime}}$ are the shortest paths between the respective
nodes in $G$ as shown in Figure 4. During the execution of the step $3$ of the
STCCM-A algorithm, which constructs the MST $T_{M}$, $a$ finds $e$ as its
minimum weight outgoing edge (MWOE) and $a^{\prime}$ finds $e^{\prime}$ as its
MWOE. Similarly $b$ and $b^{\prime}$ finds $e$ and $e^{\prime}$ as their MWOEs
respectively. During the construction of the MST $T_{M}$ since
$\mathit{T_{1}}$ and $\mathit{T_{2}}$ are merged through $e$, this indicates
that $e$ is the MWOE of $\mathit{T_{1}}$. Similarly $e$ is the MWOE of
$\mathit{T_{2}}$. Since $\mathit{T_{1}}$ and $\mathit{T_{2}}$ are merged along
the path $P_{uv}$ to form $\mathit{T}$, this ensures that $P^{\prime}_{uv}\geq
P_{uv}$ contradicting the fact $P^{\prime}_{uv}<P_{uv}$. Therefore $P_{uv}$ is
the shortest straight path between $u$ and $v$ in $G$.

Figure 4: A state before merging of two shortest path trees $\mathit{T_{1}}$
and $\mathit{T_{2}}$ along a shortest straight path $\mathit{P_{uv}}$. The
edge categories in $\mathit{T_{1}}$ and $\mathit{T_{2}}$ are shown according
to the graph $\mathit{G_{c}}$ constructed in step $2$ of the STCCM-A
algorithm. Note that both the trees $\mathit{T_{1}}$ and $\mathit{T_{2}}$ are
subgraphs of a complete graph $K_{n}$.

∎

Consider a graph $T^{*}=(Z,E^{*},w^{*})$ whose vertex set $Z$ and edge set
$E^{*}$ are defined from $T_{M}$ as follows. For each _straight path_ $P_{uv}$
of $T_{M}$, let $(a,b)$ be an edge of $E^{*}$. Then the following lemma holds.

######  Lemma 5.4.

$T^{*}$ is an MST of $K_{Z}$ for $Z\subseteq V$ of graph $G=(V,E,w)$.

The correctness of the above lemma directly follows from the correctness of
the Lemma $4.8$ in [26].

It is obvious that if we unfold the tree $T^{*}=(Z,E^{*},w^{*})$ then it
transforms to a resultant graph $\mathit{T_{Z}}$, which satisfies the
following properties.

  * 1.

For each straight path between $u$ and $v$ in $\mathit{T_{Z}}$, there exists
an edge $e=(u,v)\in E^{*}$, where $u,v\in Z$ and the length of the straight
path between $u$ and $v$ in $\mathit{T_{Z}}$ is the shortest one between $u$
and $v$ in $\mathit{G}$.

  * 2.

All leaves of $\mathit{T_{Z}}$ are in $\mathit{Z}$.

Therefore the following theorem holds.

######  Theorem 5.5.

The tree $T_{Z}$ computed by the STCCM-A algorithm is a generalized MST for
$Z\subseteq V$ of $G=(V,E,w)$.

Let $cost(X)$ denotes the sum of weights of all the edges in a graph $X$. Let
$T_{opt}$ denotes the optimal ST. Then the following theorem holds.

######  Theorem 5.6.

$cost(T_{Z})/cost(T_{opt})\leq 2(1-\frac{1}{\ell})\leq 2(1-\frac{1}{|Z|})$.

The correctness of the above theorem essentially follows from the correctness
of the Theorem 1 of Kou et al. [30]. For the sake of completeness here we give
the outline of this correctness. Let $T_{opt}$ consists of $q\geq 1$ edges.
Then there exists a loop $L=v_{0},v_{1},v_{2},\cdots,v_{2q}(=v_{0})$ in
$T_{opt}$ in such a way that

  * 1.

every edge in $T_{opt}$ appears exactly twice in $L$. This implies that
$cost(L)=2\times cost(T_{opt})$.

  * 2.

every leaf in $T_{opt}$ appears exactly once in $L$ and if $v_{i}$ and $v_{j}$
are two consecutive leaves in $L$ then the sub-path connecting $v_{i}$ and
$v_{j}$ is a simple path.

Note that the loop $L$ can be decomposed into $\ell$ simple sub-paths (recall
that $\ell$ is the number of leaf nodes in the $T_{opt}$), each of them
connects two consecutive leaf nodes in $L$. By deleting the longest such
simple sub-path from $L$ the remaining path (say $P$) in $L$ satisfies the
followings.

  * 1.

every edge in $T_{opt}$ appears at least once in $P$.

  * 2.

$cost(P)\leq(1-\frac{1}{\ell})\times cost(L)=(1-\frac{1}{\ell})\times 2\times
cost(T_{opt})$.

Now assume that $T_{Z}$ is a generalized MST for $Z$ of $G$. We know that
$T_{Z}$ realizes the MST say $T_{A}$ of the complete distance graph $K_{Z}$
for $Z$ of $G$. In other words $cost(T_{Z})=cost(T_{A})$. Note that each edge
$(u,v)$ in $T_{A}$, where $u,v\in Z$, is a _shortest straight path_ between
$u$ and $v$ in $G$. This ensures that the weight of an edge $(u,v)$ in $T_{A}$
is at most the weight of the corresponding simple path between nodes $u$ and
$v$ in $P$. If we consider all the edges of $T_{A}$ then $cost(T_{A})\leq
cost(P)$. This concludes that $cost(T_{Z})=cost(T_{A})\leq cost(P)\leq
2\times(1-\frac{1}{\ell})\times cost(T_{opt})$.

Deadlock issue. The STCCM-A algorithm is free from deadlock. Deadlock occurs
only if a set of nodes in the system enter into a circular wait state. In step
$1$ (SPF construction) of the STCCM-A algorithm, a node uniformly distributes
its input (a brief description of the input distribution is given in A), which
is the incident edge weights of it, among a subset of nodes (which are of
course withing one hop distances) and never sends resource request message to
any other nodes. This ensures that nodes never create circular waiting (or
waiting request) for any resource during the execution of the algorithm. In
Step $2$, each node independently sends a message (containing its own state)
to all of its neighbors only once. Upon receiving messages from all of its
neighbors, a node performs some local computation and then terminates itself.
Therefore, in step $2$ nodes are free from any possible circular waiting. The
correctness of the deadlock freeness of the step 3 essentially follows from
the work of Lotker et al. [1]. In step $4$, the pruning operation is performed
on a tree structure ($T_{M}$) and a node never requests and waits for
resources holding by any other node in the system. This implies that during
the pruning operation, nodes are free from any possible circular waiting.
Therefore, the deadlock freeness of all four steps together ensure deadlock
freeness of the STCCM-A algorithm.

##  6 STCCM-B algorithm

The STCCM-B algorithm is a modified version of the STCCM-A algorithm that
computes an ST in $O(S+\log\log n)$ rounds and $O(S(n-t)^{2}+n^{2})$ messages
in the CCM maintaining the same approximation factor as that of the STCCM-A
algorithm described in Section 4. Similar to the STCCM-A algorithm the STCCM-B
algorithm also has four steps (small distributed algorithms). In the STCCM-B
algorithm except the step $1$ all other steps are same as that of the STCCM-A
algorithm. Recall that step $1$ of the STCCM-A algorithm is a construction of
a SPF of a given input graph $G=(V,E,w)$ with a terminal set $Z\subseteq V$.
In contrast for step $1$ of the STCCM-B algorithm, which is also the SPF
construction, we adapt the SPF algorithm proposed in [26] to the CCM. This new
SPF algorithm denoted by SPF-B helps achieving a different round and message
complexities for $2(1-1/\ell)$-approximate ST construction in the CCM.
Specifically for constant or small shortest path diameter networks (where
$S=O(\log\log n)$) the STCCM-B algorithm outperforms the STCCM-A algorithm in
terms of round complexity in the CCM.

The SPF algorithm in [26] vs. the SPF-B algorithm. The SPF algorithm in [26]
was proposed for the $\mathcal{CONGEST}$ model, whereas our SPF-B algorithm is
devised for the CCM. In the SPF algorithm in [26] the terminal nodes need to
participate in forwarding $\langle update\rangle$ messages until the
termination of the algorithm. However in the SPF-B algorithm the terminal
nodes participate in forwarding $\langle update\rangle$ messages only once and
after that they exchange no further messages in the system. The SPF-B
algorithm terminates in $S+2$ rounds, whereas the SPF algorithm in [26]
terminates in $S+h$ rounds, where $h$ is the height of a breadth first search
tree of the given input graph $G$. Note here that $h\leq D\leq S$. Despite the
same asymptotic round complexities, required by the both algorithms, which is
$O(S)$, they incur different message complexities. The SPF-B algorithm incurs
a message complexity of $O(S(n-t)^{2}+nt)$, where $n>t$, whereas the SPF
algorithm in [26] has the message complexity of $O(\Delta(n-t)S)$, where
$\Delta$ is the maximum degree of a vertex in the input graph $G$.

###  6.1 SPF-B algorithm

In addition to the notations defined in Section 2 the following notations are
used in the description of the SPF-B algorithm.

  * 1.

$ts(v)$ denotes the tentative source ID of a node $v$.

  * 2.

$td(v)$ denotes tentative shortest distance from a node $v$ to its $ts(v)$.

  * 3.

$tf(v)$ denotes the terminal flag of a node $v$.

  * 4.

$t\pi(v)$ denotes the tentative predecessor of a node $v$.

  * 5.

Let $e\in\delta(v)$. Then at node $v$, $tdn(e)$ denotes the tentative shortest
distance of a node incident on the other end of $e$. Similarly at node $v$,
$idn(e)$, $tsn(e)$ and $tfn(e)$ denote ID, tentative source ID and terminal
flag value respectively of a node incident on the other end of $e$.

Input specification.

  * 1.

If $\mathit{v\in Z}$ then $td(v)=0$, $t\pi(v)=v$, $ts(v)=v$, and
$\mathit{tf(v)=true}$.

  * 2.

If $\mathit{v\in V\setminus Z}$ then $td(v)=\infty$, $t\pi(v)=nill$,
$ts(v)=nill$, and $\mathit{tf(v)=false}$.

  * 3.

The value of $\mathit{ES(e)}$ can be either $\mathit{basic}$ or
$\mathit{blocked}$. A node $v$ sets the state of an incident edge
$(v,u)\in\delta(v)$ as $\mathit{blocked}$ if $u\in Z$. Otherwise, at node $v$,
the edge $(v,u)$ has the state value as $\mathit{basic}$. It is possible for
the edge states at the two nodes adjacent to the edge to be temporarily
different.

Output specification. When the algorithm terminates then $d(v)=td(v)$,
$\pi(v)=t\pi(v)$, and $s(v)=ts(v)$ for each node $v\in V$.

SPF-B algorithm. Pseudocode at node $v$ upon receiving a set of messages or no
message.

Let $Z$ be the set of terminals, $U$ be the set of $\langle update\rangle$
messages received by node $v$ in a round.

1:upon receiving no message

2:if $v=r$ then $\triangleright$ spontaneous awaken of the special node $r$

3: for all $\mathit{e\in\delta(v)}$ do $\triangleright$ here
$\mathit{\delta(v)}$ contains $n-1$ edges

4: send $\langle wakeup\rangle$ on $\mathit{e}$

5: end for

6:end if

7:upon receiving $\langle wakeup\rangle$

8:for all $\mathit{e\in\delta(v)}$ do

9: $\mathit{ES(e)\leftarrow basic;}$

10:end for

11:if $\mathit{v\in Z}$ then

12: $tf\leftarrow true;ts\leftarrow v;t\pi\leftarrow v;td\leftarrow 0;$

13: for all $\mathit{e\in\delta(v)}$ do

14: send $\langle update(v,ts,td,tf)\rangle$ on $\mathit{e}$

15: end for

16:else

17: $tf\leftarrow false;ts\leftarrow nill;t\pi\leftarrow
nill;td\leftarrow\infty;$

18:end if

19:upon receiving a set of $\langle update\rangle$ messages $\triangleright$
$U\neq\phi$

20:for all $\langle update(idn(e),tsn(e),tdn(e),tfn(e))\rangle\in U$ such that
$e\in\delta(v)$ do

21: if $tfn(e)=true$ then

22: $ES(e)\leftarrow blocked;$

23: end if

24: if $tdn(e)+w(e)<td$ then $\triangleright$ update the tentative source,
distance, and predecessor

25: $update\\_flag\leftarrow true;$ $\triangleright$ $update\\_flag$ is a
temporary boolean variable

26: $td\leftarrow tdn(e)+w(e);t\pi\leftarrow idn(e);ts\leftarrow tsn(e);$

27: end if

28:end for

29:if $update\\_flag=true$ then

30: for all $e\in\delta(v)$ such that $ES(e)\neq blocked$ do

31: send $\langle update(v,ts,td,tf)\rangle$ on $e$

32: end for

33: $update\\_flag\leftarrow false;$

34:end if

Outline of the algorithm. We assume that the SPF-B algorithm is initiated by a
special node $r$. $r$ initiates the algorithm by sending a $\langle
wakeup\rangle$ message to all other nodes in the communication network, which
is a clique. Upon receiving the $\langle wakeup\rangle$ message, a node $v$
initializes its local variables as shown in the input specification. Now each
node $\mathit{v\in Z}$ sends $\langle update\rangle$ messages to all nodes in
$V$. After that nodes in $\mathit{Z}$ send or receive no further messages,
whereas in each subsequent rounds nodes in $\mathit{V\setminus Z}$ may send or
receive $\langle update\rangle$ messages until the termination of the
algorithm. Upon receiving a set of $\langle update\rangle$ messages (denoted
by $U$) a node $v\in V$ acts as per the following rules.

  1. R1.

if an $\langle update\rangle\in U$ is received through an incident edge
$e=(v,u)$ such that $u\in Z$ then it sets $\mathit{ES(e)}$ to
$\mathit{blocked}$.

  2. R2.

if $v\in V\setminus Z$ then it computes $w(e)+tdn(e)$ for each $\langle
update(idn(e),tsn(e),tdn(e),tfn(e))\rangle\in U$ and chooses the minimum one,
say $w(e^{\prime})+tdn(e^{\prime})$ resulted by $\langle
update(idn(e^{\prime}),tsn(e^{\prime}),tdn(e^{\prime}),$
$tfn(e^{\prime}))\rangle\in U$. If $td(v)>w(e^{\prime})+tdn(e^{\prime})$ then
it updates $td(v)=w(e^{\prime})+tdn(e^{\prime})$, $ts(v)=tsn(e^{\prime})$, and
$t\pi(v)=idn(e^{\prime})$. Otherwise, $td(v)$, $ts(v)$ and $t\pi(v)$ remain
unchanged.

  3. R3.

if the value of $td(v)$ is updated then it sends $\langle
update(v,ts(v),td(v),tf(v))\rangle$ on all of its incident $\mathit{basic}$
edges.

######  Lemma 6.1.

The SPF-B algorithm terminates after at most $S+2$ rounds.

###### Proof.

The special node $r$ initiates the SPF-B algorithm by sending $\langle
wakeup\rangle$ messages to all the nodes in $V$ which takes exactly $1$ round.
Upon receiving $\langle wakeup\rangle$ message each node in $\mathit{Z}$, in
parallel, sends $\langle update\rangle$ messages to each node in $V$. This
takes $1$ round only. After that all nodes in $\mathit{V\setminus Z}$ proceed
in parallel, and if applicable they update their local states. Note that in
each subsequent round at least one node in $\mathit{V\setminus Z}$ must update
its local variables, otherwise, the algorithm must have reached the
termination state. Since $S$ is the shortest path diameter any path in the SPF
contains no more than $S$ edges. Since all nodes in $\mathit{V\setminus Z}$
update their local states in parallel, each such node $v$ converges to its
correct $d(v)$ value in at most $S$ additional rounds. Therefore after $S+2$
rounds of execution no local changes occur at any node in the system and
consequently no further messages related to the SPF-B algorithm will be sent
or in transit. This concludes that the SPF-B algorithm terminates after at
most $S+2$ rounds. ∎

######  Theorem 6.2.

The round complexity of the SPF-B algorithm is $O(S)$.

###### Proof.

By Lemma 6.1 the SPF-B algorithm terminates after at most $S+2$ rounds.
Therefore the overall round complexity of the SPF-B algorithm is $O(S)$. ∎

######  Theorem 6.3.

The message complexity of the SPF-B algorithm is $O(S(n-t)^{2}+nt)$, where
$n>t$.

###### Proof.

The special node $r$ initiates the SPF-B algorithm by sending $\langle
wakeup\rangle$ messages to all the nodes in $V$, which generates exactly $n$
messages (we assume that a node can send message to itself too). Upon
receiving $\langle wakeup\rangle$ message each node in $\mathit{Z}$, in
parallel, sends $\langle update\rangle$ messages to each node in $V$. This
step generates $nt$ messages, where $t=|Z|$. After that no further messages
are generated due to the node set $\mathit{Z}$. On the other hand in each
subsequent round each node in $\mathit{V\setminus Z}$ may update its local
variables and sends $\langle update\rangle$ message to each node in
$\mathit{V\setminus Z}$. In the worst-case in each subsequent round this may
generates $(n-t)^{2}$ messages. By Lemma 6.1 the SPF-B algorithm terminates in
$S+2$ rounds. Combining all the steps the total number of messages generated,
in the worst-case, is $(S+2)(n-t)^{2}+nt+n$. We assume that $n>t$. Therefore
the overall message complexity of the SPF-B algorithm is $O(S(n-t)^{2}+nt)$. ∎

######  Lemma 6.4.

Let $td_{i}(v)$ be the length of the tentative shortest path from node $v$ to
its $ts(v)$ after $i\geq 0$ rounds. Let the SPF-B algorithm terminates after
$X\leq S+2$ rounds. Then $td_{X}(v)=d(v,s(v))$ for each node $v\in V$ that
uses $\leq S$ edges.

The correctness of the above lemma directly follows from the correctness of
the Lemma $3.3$ in [26].

###  6.2 Proof of the STCCM-B algorithm

Similar to the STCCM-A algorithm the STCCM-B algorithm also computes a
generalized MST for $\mathit{Z}$ of $\mathit{G}$. Therefore the approximation
factor of an ST computed by the STCCM-B algorithm is same as that of the
STCCM-A algorithm, which is $2(1-1/\ell)$.

######  Theorem 6.5.

The round complexity of the STCCM-B algorithm is $O(S+\log\log n)$.

###### Proof.

We know that the STCCM-B algorithm consists of four steps. By Theorem 6.2 the
round complexity of the step $1$ is $O(S)$. The round complexities of the
steps $2$, $3$, and $4$ of the STCCM-B algorithm are $O(1)$, $O(\log\log n)$,
and $O(1)$ respectively. It is clear that the overall round complexity of the
STCCM-B algorithm is dominated by the steps $1$ and $3$, which is
$O(S+\log\log n)$. ∎

######  Theorem 6.6.

The message complexity of the STCCM-B algorithm is $O(S(n-t)^{2}+n^{2})$.

###### Proof.

By Theorem 6.3 the message complexity of the step 1 of the STCCM-B algorithm
is $O(S(n-t)^{2}+nt)$. The message complexities of the steps $2$, $3$, and $4$
of the STCCM-B algorithm are $O(m)$, $O(n^{2})$, and $O(n^{2})$ respectively.
We know that $m\leq n^{2}$ and $nt<n^{2}$, where $n>t$. Therefore the overall
message complexity of the STCCM-B algorithm is $O(S(n-t)^{2}+n^{2})$. ∎

##  7 Discussion and Conclusion

In this paper we have presented two deterministic distributed approximation
algorithms for the ST problem in the CCM. The first one constructs a
$2(1-1/\ell)$-approximate ST in $\tilde{O}(n^{1/3})$ rounds and
$\tilde{O}(n^{7/3})$ messages and the polylogarthmic factors involved with
each of the round and message complexities is $\log n$. The second one
computes a $2(1-1/\ell)$-approximate ST in $O(S+\log\log n)$ rounds and
$O(S(n-t)^{2}+n^{2})$ messages. Note that if a graph has the property
$S=\omega(n^{1/3}\log n)$, the first algorithm shows a better performance in
terms of round complexity in contrast to the second one. On the other hand if
a graph has the property $S=\tilde{o}(n^{1/3})$, then the second algorithm
outperforms the first one in terms of the round complexity. Furthermore we
have also observed that for constant or sufficiently small shortest path
diameter networks (where $S=O(\log\log n)$) the second algorithm computes a
$2(1-1/\ell)$-approximate ST in $O(\log\log n)$ rounds and $\tilde{O}(n^{2})$
messages in the CCM. This result almost coincide with the best known
deterministic result for MST construction in the CCM due to Lotker et al. [1]
and the approximation factor of the resultant ST is at most $2(1-1/\ell)$ of
the optimal.

It is known that in the centralized setting, the ST problem can be
approximated upto a factor of $\ln(4)+\epsilon\approx 1.386+\epsilon$ (for
$\epsilon>0$) of the optimal [5]. Pemmaraju and Sardeshmukh [29] showed that
there exists a randomized algorithm that computes an MST in $O(\log^{*}n)$
rounds and $o(m)$ messages in the CCM. Recently Jurdziński and Nowicki [10]
achieved a randomized algorithm in the CCM that computes an MST in $O(1)$
rounds. Since the ST problem is a generalized version of the MST problem,
there is an open research direction on improvement of the approximation
factor, the round and the message complexities in the CCM.

## References

  * Lotker et al. [2005] Z. Lotker, B. Patt-Shamir, E. Pavlov, D. Peleg,  Minimum-Weight Spanning Tree Construction in O(Log Log N) Communication Rounds,  SIAM Journal on Computing 35 (2005) 120–131. doi:10.1137/S0097539704441848.
  * Linial [1992] N. Linial,  Locality in distributed graph algorithms,  SIAM Journal on Computing 21 (1992) 193–201. doi:10.1137/0221015.
  * Peleg and Rubinovich [2000] D. Peleg, V. Rubinovich,  A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction,  SIAM Journal on Computing 30 (2000) 1427–1442. doi:10.1137/S0097539700369740.
  * Karp [1972] R. M. Karp,  Reducibility Among Combinatorial Problems,  in: Proceedings of a Symposium on the Complexity of Computer Computations, 1972, pp. 85–103. doi:10.1007/978-1-4684-2001-2_9.
  * Byrka et al. [2010] J. Byrka, F. Grandoni, T. Rothvoß, L. Sanità,  An Improved LP-based Approximation for Steiner Tree,  in: Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC ’10, 2010, pp. 583–592. doi:10.1145/1806689.1806769.
  * Chlebík and Chlebíková [2008] M. Chlebík, J. Chlebíková,  The Steiner tree problem on graphs: Inapproximability results,  Theoretical Computer Science 406 (2008) 207 – 214. doi:10.1016/j.tcs.2008.06.046.
  * Hauptmann and Karpinski [2015] M. Hauptmann, M. Karpinski,  A Compendium on Steiner Tree Problems,  http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.html (2015).
  * Hegeman et al. [2014] J. W. Hegeman, S. V. Pemmaraju, V. B. Sardeshmukh,  Near-constant-time distributed algorithms on a congested clique,  in: Proceedings of the 28th International Conference on Distributed Computing, DISC’14, 2014, pp. 514–530. doi:10.1007/978-3-662-45174-8_35.
  * Ghaffari and Parter [2016] M. Ghaffari, M. Parter,  MST in Log-Star Rounds of Congested Clique,  in: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC ’16, 2016, pp. 19–28. doi:10.1145/2933057.2933103.
  * Jurdziński and Nowicki [2018] T. Jurdziński, K. Nowicki,  MST in O(1) Rounds of Congested Clique,  in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, 2018, pp. 2620–2632. doi:10.1137/1.9781611975031.167.
  * Berns et al. [2012] A. Berns, J. Hegeman, S. V. Pemmaraju,  Super-fast Distributed Algorithms for Metric Facility Location,  in: Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part II, ICALP’12, 2012, pp. 428–439. doi:10.1007/978-3-642-31585-5_39.
  * Gehweiler et al. [2014] J. Gehweiler, C. Lammersen, C. Sohler,  A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem,  Algorithmica 68 (2014) 643–670. doi:10.1007/s00453-012-9690-y.
  * Censor-Hillel et al. [2015] K. Censor-Hillel, P. Kaski, J. H. Korhonen, C. Lenzen, A. Paz, J. Suomela,  Algebraic Methods in the Congested Clique,  in: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, 2015, pp. 143–152. doi:10.1145/2767386.2767414.
  * Holzer and Pinsker [2016] S. Holzer, N. Pinsker,  Approximation of Distances and Shortest Paths in the Broadcast Congest Clique,  in: 19th International Conference on Principles of Distributed Systems (OPODIS 2015), volume 46, 2016, pp. 1–16. doi:10.4230/LIPIcs.OPODIS.2015.6.
  * Nanongkai [2014] D. Nanongkai,  Distributed approximation algorithms for weighted shortest paths,  in: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC ’14, 2014, pp. 565–573. doi:10.1145/2591796.2591850.
  * Drucker et al. [2012] A. Drucker, F. Kuhn, R. Oshman,  The communication complexity of distributed task allocation,  in: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC ’12, 2012, pp. 67–76. doi:10.1145/2332432.2332443.
  * Dolev et al. [2012] D. Dolev, C. Lenzen, S. Peled,  “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting,  in: Proceedings of the 26th International Conference on Distributed Computing, DISC’12, 2012, pp. 195–209. doi:10.1007/978-3-642-33651-5_14.
  * Patt-Shamir and Teplitsky [2011] B. Patt-Shamir, M. Teplitsky,  The round complexity of distributed sorting: Extended abstract,  in: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’11, 2011, pp. 249–256. doi:10.1145/1993806.1993851.
  * Lenzen [2013] C. Lenzen,  Optimal deterministic routing and sorting on the congested clique,  in: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, 2013, pp. 42–50. doi:10.1145/2484239.2501983.
  * Pai and Pemmaraju [2019] S. Pai, S. V. Pemmaraju,  Connectivity lower bounds in broadcast congested clique,  CoRR (2019). URL: http://arxiv.org/abs/1905.09016.
  * Drucker et al. [2014] A. Drucker, F. Kuhn, R. Oshman,  On the power of the congested clique model,  in: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14, 2014, pp. 367–376. doi:10.1145/2611462.2611493.
  * Chen et al. [1993] G.-H. Chen, M. E. Houle, M.-T. Kuo,  The Steiner problem in distributed computing systems,  Information Sciences 74 (1993) 73–96. doi:10.1016/0020-0255(93)90128-9.
  * Chalermsook and Fakcharoenphol [2005] P. Chalermsook, J. Fakcharoenphol,  Simple distributed algorithms for approximating minimum Steiner trees,  in: Proceedings of the 11th Annual International Conference on Computing and Combinatorics, COCOON ’05, 2005, pp. 380–389. doi:10.1007/11533719_39.
  * Khan et al. [2008] M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, K. Talwar,  Efficient distributed approximation algorithms via probabilistic tree embeddings,  in: Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC ’08, 2008, pp. 263–272. doi:10.1145/1400751.1400787.
  * Lenzen and Patt-Shamir [2015] C. Lenzen, B. Patt-Shamir,  Fast partial distance estimation and applications,  in: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, 2015, pp. 153–162. doi:10.1145/2767386.2767398.
  * Saikia and Karmakar [2019] P. Saikia, S. Karmakar,  A simple $2(1-1/\ell)$ factor distributed approximation algorithm for Steiner tree in the congest model,  in: Proceedings of the 20th International Conference on Distributed Computing and Networking, ICDCN ’19, 2019, pp. 41–50. doi:10.1145/3288599.3288629.
  * Khan and Pandurangan [2008] M. Khan, G. Pandurangan,  A fast distributed approximation algorithm for minimum spanning trees,  Distributed Computing 20 (2008) 391–402. doi:10.1007/s00446-007-0047-8.
  * Hegeman et al. [2015] J. W. Hegeman, G. Pandurangan, S. V. Pemmaraju, V. B. Sardeshmukh, M. Scquizzato,  Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST,  in: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, 2015, pp. 91–100. doi:10.1145/2767386.2767434.
  * Pemmaraju and Sardeshmukh [2016] S. V. Pemmaraju, V. B. Sardeshmukh,  Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages,  in: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), 2016, pp. 47:1–47:15. doi:10.4230/LIPIcs.FSTTCS.2016.47.
  * Kou et al. [1981] L. Kou, G. Markowsky, L. Berman,  A fast algorithm for Steiner trees,  Acta Informatica 15 (1981) 141–145. doi:10.1007/BF00288961.
  * Wu et al. [1986] Y. F. Wu, P. Widmayer, C. K. Wong,  A faster approximation algorithm for the Steiner problem in graphs,  Acta Informatica 23 (1986) 223–229. doi:10.1007/BF00289500.
  * Bachrach et al. [2019] N. Bachrach, K. Censor-Hillel, M. Dory, Y. Efron, D. Leitersdorf, A. Paz,  Hardness of distributed optimization,  CoRR abs/1905.10284 (2019). URL: http://arxiv.org/abs/1905.10284.
  * Das Sarma et al. [2011] A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, R. Wattenhofer,  Distributed verification and hardness of distributed approximation,  in: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC ’11, 2011, pp. 363–372. doi:10.1145/1993636.1993686.
  * Kutten et al. [2015] S. Kutten, G. Pandurangan, D. Peleg, P. Robinson, A. Trehan,  On the complexity of universal leader election,  Journal of the ACM 62 (2015) 7:1–7:27. doi:10.1145/2699440.
  * Peleg [2000] D. Peleg,  Distributed Computing: A Locality-Sensitive Approach,  SIAM : Discrete Mathematics and Applications (2000). doi:10.1137/1.9780898719772.
  * Fischer and Meyer [1971] M. J. Fischer, A. R. Meyer,  Boolean matrix multiplication and transitive closure,  in: Proceedings of the 12th Annual Symposium on Switching and Automata Theory, SWAT ’71, 1971, pp. 129–131. doi:10.1109/SWAT.1971.4.
  * Munro [1971] I. Munro,  Efficient determination of the transitive closure of a directed graph,  Information Processing Letters 1 (1971) 56–58. doi:10.1016/0020-0190(71)90006-8.

##  Appendix A Censor-Hillel et al.’s APSP algorithm in the CCM [13]

Censor-Hillel et al. showed that the APSP of a given graph $G=(V,E,w)$ can be
computed via iterated squaring of the weight matrix over the min-plus semiring
[36, 37]. Let $W$ be the weight matrix of size $n\times n$ for a given graph
$G$, where $n=|V|$. Then the distance product which is also known as the min-
plus product is defined as follows.

$(W\star W)_{uv}=W^{2}_{uv}=\smash{\displaystyle\min_{w}}(W_{uw}+W_{wv})$

where $u,v,w\in V$. The $n^{th}$ distance product denoted by $W^{n}$ produces
the actual shortest path distances in $G$, i.e., $\delta(u,v)=W^{n}_{uv}$ for
each pair of vertices $u,v\in V$. The distance product $W^{n}$ can be computed
by iteratively squaring $W$ for $\lceil\log n\rceil$ times. The distributed
squaring of a weight matrix over the min-plus semiring is similar to the
parallel 3D matrix multiplication. The squaring of $W$ over the min-plus
semiring involves $n^{3}$ element wise additions of the form $W_{uw}+W_{wv}$,
where $u,v,w\in V$. This is viewed as a cube of size $n\times n\times n$ where
each point in the cube represents an addition operation. If we partition the
cube of size $n\times n\times n$ into $n$ sub-cubes of equal sizes then each
of them gets $n^{2/3}\times n^{2/3}\times n^{2/3}$ points of the cube. This
indicates that each node $v\in V$ needs to perform $n^{2/3}\times
n^{2/3}\times n^{2/3}$ addition operations. Note that the weight matrix $W$
has $n^{2}$ entries corresponding to the edge weights of the input graph.777If
an edge $(u,v)$ is not in the input graph $G$, then $w((u,v))$ is considered
equal to $\infty$. This $n^{2}$ entries are distributed uniformly among $n$
nodes in such a way that each node $v\in V$ gets two sub-matrices of sizes
$n^{2/3}\times n^{2/3}$. This ensures that each node needs to compute the min-
plus product of the matrix size $n^{2/3}\times n^{2/3}$ only.

Now we briefly describe the APSP algorithm due to Censor-Hillel et al. [13].
Initially each node $u\in V$ knows the edge weights $w((u,v))$ for each $v\in
V$. Here it is assumed that $n^{1/3}$ is a positive integer, where $n=|V|$.
Each node $v\in V$ partitions its input into $n^{1/3}$ blocks, each one has
$n^{2/3}$ entries. Now each node $v\in V$ sends its each block to $2n^{1/3}$
nodes in such a way that each node $v\in V$ receives two sub-matrices, each of
them has size $n^{2/3}\times n^{2/3}$. Since each block has size $n^{2/3}$ and
there are $2n^{2/3}$ recipients, a total of $2n^{4/3}$ messages are sent by
each node. This distribution is performed in $O(n^{1/3})$ rounds and
$O(n^{7/3})$ messages by using the deterministic routing scheme of Lenzen
[19]. Then each node computes the min-plus product from the two known sub-
matrices. After that all the resulting min-plus products are re-distributed
among $n$ nodes in such a way that each node $v\in V$ receives $n^{4/3}$
values. This distribution of the min-plus products is also performed in
$O(n^{1/3})$ rounds $O(n^{7/3})$ messages by using the deterministic routing
scheme of Lenzen [19]. The received $n^{4/3}$ messages by a node $v\in V$
contain the information related to the row $v$ of the resulting min-plus
product $W^{2}=W\star W$ from which $v$ locally computes the values of its own
row with respect to $W^{2}$. With this the first iteration ends. Considering
that each of the node IDs and edge weights can be encoded by using $O(\log)$
bits, the round and message complexities of the this iteration are
$O(n^{1/3})$ and $O(n^{7/3})$ respectively. Repetition of the above procedure
for $\lceil\log n\rceil$ times on each of the resulting min-plus product
guarantees the final output $W^{n}$ which is the required APSP for a given
graph $G$. The overall round and message complexities of this algorithm are
$O(n^{1/3}\log n)$ and $O(n^{7/3}\log n)$ respectively.

Routing table construction. The task of routing table construction concerns
computing local tables at all the nodes of a network in which each node $u$,
when given a destination node $v$, knows the next hop through which $u$ is
connected to $v$ by the shortest path distance in the network. Specifically
the routing table entry $R[u,v]=w\in V$ is a node such that $(u,w)\in E$ and
$w$ lies on a shortest path from $u$ to $v$. Censor-Hillel et al. [13] showed
that iterated squaring of the weight matrix over the min-plus semiring can
also be used to construct the routing table for each node $v\in V$. The min-
plus product $W\star W$ provides a _witness matrix_ $Q$ such that if
$Q_{uv}=w$, then $(W\star W)_{uv}=W_{uw}+W_{wv}$. Whenever the iterated
squaring algorithm computes the min-plus product $W^{2i}=W^{i}\star W^{i}$,
then using the witness matrix $Q$ the routing table $R$ is updated to
$R[u,v]=R[u,Q_{uv}]$ for each $u,v\in V$ with $W^{2i}_{uv}<W^{i}_{uv}$.

##  Appendix B Lotker et al’s MST algorithm in the CCM [1]

The algorithm operates in phases. Each phase takes $O(1)$ rounds. In each
phase $k\geq 0$ it maintains a set of clusters
$\mathcal{F}^{k}=\\{\mathit{F}^{k}_{1},\mathit{F}^{k}_{2},.....\mathit{F}^{k}_{p}\\}$,
$\bigcup_{i}\mathit{F_{i}^{k}=V}$, where $\mathit{V}$ is the vertex set of the
input graph $\mathit{G}$. For the sake of simplicity it is assumed that at the
beginning of phase $1$, the end of the imaginary phase $0$, with the cluster
set
$\mathcal{F}^{0}=\\{\mathit{F}^{0}_{1},\mathit{F}^{0}_{2},.....\mathit{F}^{0}_{n}\\}$
is known, where $\mathit{F}^{0}_{i}=\\{v_{i}\\}$ for every $1\leq i\leq n$.
For each cluster $\mathit{F}\in\mathcal{F}^{k}$, the algorithm selects a
spanning subtree $\mathit{T(F)}$. At the beginning of phase $k>0$, the cluster
set $\mathcal{F}^{k-1}$ and the corresponding subtree collection
$\mathcal{T}^{k-1}=\\{\mathit{T(F)}|\mathit{F}\in\mathcal{F}^{k-1}\\}$,
including the weights of the edges in those subtrees, are known to every
vertex in the graph. Whenever the algorithm terminates each node in
$\mathit{V}$ knows all the $n-1$ edges in the MST of the given graph
$\mathit{G}$.

The outline of a phase $k>0$ is as follows. Initially each cluster
$\mathit{C}\in\mathcal{F}^{k-1}$ is contracted to a vertex $\mathit{v_{C}}$.
All these contracted vertices together form a smaller logical graph denoted by
$\mathit{\hat{G}}$. The operation of each vertex $\mathit{v_{C}}$ is carried
out by a special node called the leader of $\mathit{C}$ denoted by
$\mathit{l(C)}$. Let $\mathit{N}$ be the minimum size cluster in
$\mathcal{F}^{k-1}$. At the beginning of phase $k>0$, $\mathit{N}$ (or more)
the members of each cluster $\mathit{C}\in\mathcal{F}^{k-1}$ collect
$\mathit{N}$ lightest edges connecting their cluster $\mathit{C}$ to other
clusters in $\mathcal{F}^{k-1}\setminus\\{\mathit{C}\\}$. Then each cluster in
$\mathcal{F}^{k-1}$ sends these $\mathit{N}$ (or more) lightest edges to a
special node $v_{0}$ (node with the lowest ID) of the graph by appropriately
sharing the workload among the nodes of the cluster. Now the node $v_{0}$ has
a partial picture of the logical graph $\mathit{\hat{G}}$, consisting of all
the contracted vertices $\mathit{v_{C}}$ but only some of the edges connecting
them, specifically $\mathit{N}$ lightest edges emanating from each node of
$\mathit{\hat{G}}$ to $\mathit{N}$ different nodes. On the basis of these
received information $v_{0}$ performs (locally) fragment merging operations.
For that the known edges are sorted in non decreasing order of their weights.
Then from the non decreasing ordered edge set add edges to $\mathit{\hat{G}}$
that are the minimum weight outgoing edge (MWOE) of one of two fragments they
connect as long as merging is perfectly safe. The _safety rule_ is as follows:
It is perfectly safe to continue merging a fragment $\mathit{F}$ in the
logical graph $\mathit{\hat{G}}$ as long as the $\mathit{N}$ lightest edges of
each vertex $\mathit{v_{C}}$ in $\mathit{F}$ are not inspected. It is shown
that the safety rule allows to grow each of the fragments to contain at least
$\mathit{N}+1$ vertices of $\mathit{\hat{G}}$. This ensures that the size of
each of the clusters in the next phase will be at least $\mathit{N}^{2}$. This
is a quadratic growth of the clusters. Finally $v_{0}$ sends out the locally
known identity of all the edges that are newly chosen. Note that the number of
such edges can be at most $n-1$. The special node $v_{0}$ performs this in
$O(1)$ rounds by sending each edge to a different intermediate node, which
will broadcast that edge to all other nodes.

It is clear that at the end of a phase $k>0$, each of the cluster sizes is at
least $2^{2^{k-1}}$. Whenever the algorithm terminates, there exists only one
cluster in the cluster set which is the required MST of $\mathit{G}$, i.e.,
$|\mathcal{F}^{k}|=1$. Therefore ${2^{2^{k-1}}}=n\Rightarrow k=\log\log n+1$.
This ensures that the algorithm terminates in $O(\log\log n)$ rounds, whereas
the message complexity is $O(n^{2})$.