SIAM J. COMPUT.

c 1998 Society for Industrial and Applied Mathematics

Vol. 27, No. 1, pp. 302–316, February 1998 013

A SUBLINEAR TIME DISTRIBUTED ALGORITHM FOR

MINIMUM-WEIGHT SPANNING TREES∗
JUAN A. GARAY† , SHAY KUTTEN‡ , AND DAVID PELEG§

Abstract. This paper considers the question of identifying the parameters governing the be-
havior of fundamental global network problems. Many papers on distributed network algorithms
consider the task of optimizing the running time successful when an O(n) bound is achieved on an
n-vertex network. We propose that a more sensitive parameter is the network’s diameter Diam. This
is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm
whose time complexity is sublinear in n, but linear in Diam (specifically, O(Diam + nε · log∗ n) for
ε = ln 3
ln 6
= 0.6131...). Our result is achieved through the application of graph decomposition and
edge-elimination-by-pipelining techniques that may be of independent interest.

Key words. MST, min-weight spanning trees, distributed algorithms

AMS subject classifications. 05C05, 05C85, 68Q22, 68Q25, 68R10

PII. S0097539794261118

1. Introduction.
1.1. Motivation. In many papers on distributed network algorithms, the task of
optimizing the running time is considered successful when an O(n) bound is achieved
on an n-vertex network. Typically, the justification is that there exist n-vertex graphs
for which this bound is the best possible. The sequence of solutions to the leader
election problem (LE) exemplifies the reasoning above. Following the O(n log n) run-
ning time and a first improvement by Chin and Ting [CT] and Gafni [G] (with an
O(n log∗ n) running time), Awerbuch gave an “optimal” O(n)-time solution to the
problem [A1]. Again, this solution is optimal in the sense that there exist networks
for which this is the best possible.
This type of optimality may be thought of as “existential” optimality; namely,
there are points in the class of input instances under consideration for which the al-
gorithm is optimal. A stronger type of optimality, which we may analogously call
“universal” optimality, occurs when the proposed algorithm solves the problem opti-
mally on every instance.
An interesting “side effect” of universal optimality is that a universally optimal
algorithm precisely identifies the parameters of the problem that are inherently re-
sponsible for its complexity. For example, returning to the LE problem, a more careful

∗ Received by the editors January 3, 1994; accepted for publication (in revised form) February

5, 1996. Based on A sub-linear time distributed algorithm for minimum-weight spanning trees (pre-
liminary version), by J. A. Garay, S. Kutten, and D. Peleg, which appeared in the Proceedings of
the 34th Annual IEEE Symposium on the Foundations of Computer Science, Palo Alto, CA, IEEE
Computer Society Press, Los Alamitos, CA, 1993, pp. 659–668.
[Link]
† IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598 (garay@ wat-

[Link]). Part of this author’s work was done while visiting the Weizmann Institute of Science,
Rehovot, Israel.
‡ IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598 (kutten@

[Link]).
§ Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science,

Rehovot, 76100, Israel (peleg@[Link]). The work of this author was supported in
part by a Walter and Elise Haas Career Development Award and by a grant from the Basic Research
Foundation. Part of the work was done while visiting IBM T.J. Watson Research Center, Yorktown
Heights, NY.
302
 SUBLINEAR TIME DISTRIBUTED MST ALGORITHM 303

look reveals that the inherent parameter is the network’s diameter Diam. Indeed, it
was observed in [P] that it is possible to give a trivial O(Diam)-time distributed LE
algorithm (although it should be noted that the solutions mentioned above were also
message-optimal, whereas the algorithm of [P] is not).
The interesting question that arises is, therefore, whether it is possible to identify
the inherent graph parameters associated with the distributed complexity of vari-
ous fundamental network problems and to develop universally optimal algorithms for
them.
A closely related question has been dealt with before in the context of study-
ing the role of locality in distributed computing. Various problems were shown to
be essentially local and hence amenable to a localized algorithm with very fast (e.g.,
polylogarithmic) running times. Notable examples include computing maximal in-
dependent sets and graph coloring [GPS, L, AGLP, PS2]. Locality-based techniques
were also developed for reducing communication and time complexities for other prob-
lems whose local natures are less apparent [AP1, AP2, AKP].
In contrast, we are interested here in problems that are essentially global, i.e.,
ones that do not admit localized solutions but rather always require the algorithm
to “traverse” the network. Problems of this type still raise the interesting (if more
modest) question of deciding whether Ω(n) time is essential—or is the network’s
diameter the inherent parameter? In the latter case, it would be desirable to devise
algorithms for these network problems that have a better complexity for the case of
graphs with low diameter.
In this paper, we tackle the classical minimum-weight spanning tree (MST) prob-
lem. This problem has been studied before as a canonical example for a graph-
algorithmic problem whose communication-efficient distributed solution poses some
surprisingly nontrivial subtleties [GHS]. The time complexity of the algorithm of
[GHS] is O(n log n), which was later improved to the (existentially) “optimal” O(n)
in [A1]. As with other problems, such as the above LE example, it is natural to ask
whether O(n) is universally optimal or if it can be improved.
Once again, the MST problem proves to be a worthy candidate for this type
of study. In other tree constructions, such as the breadth-first-search (BFS) tree
(which is closely related to the LE problem), it is intuitively clear that the true time
bound should be related to the network’s diameter Diam, since the depth of the
constructed tree is proportional to Diam. In contrast, the MST of a given network
may be considerably deeper than Diam, and in fact, may be as high as Ω(n). Hence
construction methods based on communication on the tree structure itself are doomed
to require Ω(n) time, and the problem of breaking the Ω(n) barrier seems intrinsically
harder.
In this paper we get closer to identifying the inherent parameters governing the
behavior of distributed MST construction by presenting a distributed MST algorithm
whose time complexity is sublinear in n, and linear in Diam (specifically, O(Diam +
nε · log∗ n) for ε = ln 3
ln 6 = 0.6131...), thus breaking the O(n) barrier. This result
is achieved through the application of graph decomposition and edge elimination
techniques that may be interesting in their own right.
1.2. Model and definitions. In this paper we focus on the problem of devis-
ing a time-efficient distributed MST algorithm. The statement of the problem is as
follows. The network is represented by an undirected graph G = (V, E), where V
is the set of nodes and E is the set of links between them. (Henceforth we use the
terms “graph” and “network” interchangeably, when no ambiguity arises.) The graph
304 JUAN GARAY, SHAY KUTTEN, AND DAVID PELEG

is given with a weight function ω : E → R+ on the edges, such that each node in
V is associated with its own processor, and processors are able to communicate with
each other via the edges in E. The goal is to have the nodes (processors) cooperate
to construct a tree covering the nodes in V whose total edge weight is no greater than
any other spanning tree for G.
We assume that nodes have unique identifiers and that each edge e ∈ E is asso-
ciated with a distinct weight ω(e) known to the adjacent nodes. The usefulness of
having distinct edge weights stems from the fact that this property guarantees that
the MST is unique. Clearly, having distinct weights is not an essential requirement,
since one can always “create” them by appending the adjacent node’s numbers to
them. However, it is known that if the graph has neither distinct edge weights nor
distinct node identifiers, then no distributed algorithm exists for computing an MST
with a bounded number of messages [GHS].
For every subgraph F of the network, let Diam(F ) denote the diameter of F , i.e.,
the maximum distance between any two vertices of F , where distance is measured in
the unweighted sense, i.e., in the number of hops.
In order to be able to concentrate on the central issue of time complexity, we shall
follow the common trend of stripping away nonessential complications. In particular,
we ignore the communication cost of our algorithm, i.e., the number of messages
it uses. (We comment that while this number is not optimized in any way in our
solution as presented in the current paper, it is not very large. In particular, it is still
considerably smaller than the number of messages needed for every node to learn the
topology of the entire network, as is used in a number of existing routing schemes,
e.g., Internet routing [MRR].)
We also assume that the computation performed by the network is synchronous;
namely, computation proceeds in rounds, governed by a global clock, with each round
taking one time unit. In each round each processor can examine the messages sent to
it by its neighbors (if any), compute, and send messages to any subset of its neighbors.
Such messages, if sent, are available to their recipients in the next round. The time
complexity of a synchronous algorithm is the number of time units elapsing until
the termination of the algorithm. This assumption is quite common in the literature.
Note, however, that here it is not essential, since our decision to ignore communication
costs allows us to freely use a synchronizer of our choice; for example, synchronizer
α [A2] enables an asynchronous network to run any protocol that was designed for
synchronous networks, with the same time complexity, at the cost of some increase in
the message complexity.
Still, we shall not adopt the extreme model employed in previous studies of locality
issues (cf. [L]), in which messages of arbitrary size are allowed to be transmitted
in a single time unit, since in this model the refined distinctions we focus on here
disappear. Clearly, if unbounded-size messages are allowed, then the problem can be
trivially solved in time O(Diam(G)) by collecting the entire graph’s topology into a
central node, computing an MST locally, and broadcasting the result throughout the
network.
Consequently, we will assume the more realistic (and rather common) model in
which messages have size O(log n), and a node may send at most one message on each
edge at each time unit.
We will also make the assumption that edge weights are polynomial in n, so an
edge weight can be sent in a single message. (This assumption is required for the time
analysis of all previous algorithms as well [GHS, A1].)
 SUBLINEAR TIME DISTRIBUTED MST ALGORITHM 305

1.3. Our results. The original distributed MST algorithm of Gallager, Hum-
blet, and Spira [GHS] has a time complexity of O(n log n). This was later improved
by Awerbuch, who gave an O(n)-time algorithm [A1]. In this paper, we present
a distributed MST algorithm with time complexity O(Diam(G) + nε · log∗ n) for
ε = ln 3
ln 6 = 0.6131... .

2. Overview of the MST algorithm. Our algorithm is based on a careful

combination of two distinct approaches to the (distributed) construction of an MST.
Thus, before explaining our algorithm, it is instrumental to review the two approaches
and try to understand their shortcomings (when used individually).
2.1. Distributed growth approach. The first approach is the construction
method that is at the basis of the MST algorithm of [GHS] (referred to from now on
as the GHS algorithm). This algorithm does not utilize a central controller, or “center
of activity,” but rather allows a large number of processes to proceed simultaneously
and independently in the network. These processes gradually grow the MST from
scratch.
The GHS algorithm operates by growing so-called fragments in a distributed
manner, with each fragment consisting of a portion of the final MST. In each iteration
of the algorithm, the nodes of each fragment explore the immediate neighborhood of
the fragment and collectively decide on a neighboring fragment to merge with (by
adding the connecting edge to the tree), thus creating a larger fragment of the final
MST. This is a distributed version of the “blue” rule for MST construction (cf. [T,
p. 71]).
It is crucial to understand why algorithms based on this approach cannot guaran-
tee a time complexity proportional to Diam(G). The inherent difficulty lies in the fact
that the communication necessary for making the merging decisions for each fragment
is done on the fragment itself. This is a problem, since the MST is not guaranteed to
have depth proportional to Diam(G), and neither are any of its fragments. In fact,
it is easy to come up with examples for n-vertex graphs with diameter 1 whose MST
has depth n − 1. Thus, any approach based on communicating over the MST itself
will have time complexity proportional to n in the worst case on some graphs.
Note, however, that in the initial stages of the GHS algorithm, the fragments are
still small, and therefore communication on them is not as expensive. The idea on
which our algorithm is based is thus to start by running the GHS algorithm up to an
appropriately chosen point, and then switch to a different algorithm. In order for this
idea to work, it is essential to have a version of the GHS algorithm that controls the
rate of growth of the different fragments, preventing some fragments from growing
too large while other are still very small. (The original algorithm of [GHS] allows
uncontrolled growth of fragments.)
2.2. Coordinated elimination approach. The second approach to the dis-
tributed construction of an MST is based on synchronous, coordinated, centralized
operation. One extreme example for an algorithm operating in this way is the central-
ized algorithm mentioned in the introduction, in which the entire graph’s topology is
collected into a central node, which then computes an MST locally and broadcasts
the result throughout the network. This algorithm is slowed down considerably by
the heavy communication bottlenecks that are bound to be created along the paths
leading to the center node.
The crucial idea at the basis of the second approach is that some of this commu-
nication burden can be reduced by delegating the work of the center node to other
306 JUAN GARAY, SHAY KUTTEN, AND DAVID PELEG

nodes along the paths leading to the center. This can be achieved if, instead of at-
tempting to build the MST, we concentrate on eliminating candidate edges, using the
so-called “red rule” for MST construction (cf. [T, p. 71]).
In order to control the complexity of the edge-elimination process, we employ a
new efficient pipelining technique aimed at overcoming congestion. This new tech-
nique deserves some discussion, since it is different and considerably simplified com-
pared to the one presented in an earlier version of this paper [GKP]. The new tech-
nique is motivated by the following complication in the solution of [GKP]. In the
end of the first stage of the algorithm, nodes are informed about candidate edges in
the graph (those that connect clusters). In the third stage of the [GKP] algorithm,
the nodes forward the description of those edges to their parents on a spanning tree,
toward the root. The problem is that there might be too many such edges, congest-
ing the accumulation process on the tree. The algorithm of [GKP] overcomes this
difficulty by introducing an intermediate stage employing a rather complex method
(centered on locality-based ideas related to [ADDJ, AGPV, B, PS1]) for eliminating
short cycles, and thus reducing the number of remaining edges for the third stage.
The algorithm presented here has only two stages. Both the second (cycle elim-
ination) and the third stages of [GKP] are replaced by a single stage, similar to the
third stage of [GKP], in which the nodes forward descriptions of candidate edges to
their parents on a breadth-first-search spanning tree. However, we incorporate a new
technique of cycle elimination into this stage. This new pipelining technique is very
simple, and the main novelty lies in its analysis. As in the third stage of the algorithm
in [GKP], nodes on the spanning tree forward the descriptions of their candidate edges
to their parents toward the root. However, here a node avoids forwarding the descrip-
tion of cycle-heavy edges. That is, a node forwards the description of edges according
to their weight and does not forward the description of an edge that closes a cycle with
edges whose description has already been forwarded. Let us now give a hint regarding
the difficulty in analyzing this stage of the protocol. It is not hard to prove that all
non-MST edges get eliminated by this process. The difficulty lies in analyzing the
time complexity. Note that the description above (i.e., that a node does not forward
a description of a cycle-heavy edge) seems to suggest that at certain points in time a
node might be forced to wait, due to not having an edge description that is eligible for
forwarding. Thus, it may seem that the convergecast may not be fully pipelined, and
hence may take a long time. We prove that this simple convergecast is fully pipelined,
and thus its running time is the one required, eliminating the need for the complex
cycle elimination stage of [GKP]. This pipelining proof may be of interest in itself.
2.3. Combined approach. Let us now outline the structure of our algorithm.
The algorithm consists of two parts as follows.

Algorithm Sublinear-MST

Part I: Controlled-GHS;

Part II: Edge elimination.

As its name indicates, Controlled-GHS (part I) is a modified variant of the original

algorithm of [GHS]. The purpose of the modification is to produce a balanced outcome
in terms of number and diameter of the resulting fragments. This is achieved by
computing, in each phase, a small dominating set on the fragment forest and merging
 SUBLINEAR TIME DISTRIBUTED MST ALGORITHM 307

fragments accordingly. This, in turn, is achieved by invoking the distributed maximal

independent set (MIS) algorithm of [GPS]. At the end of this phase, we are left with
a “small” number of fragments, all of which have a “small” diameter.
Finally, part II performs the elimination of most of the remaining edges, leaving
only a tree connecting the fragments, and thus yielding the final MST. This elimi-
nation process is carried out in a distributed manner and requires nodes to forward
the description of certain edges to a central node, while eliminating the description
of certain other edges. (The forwarding is done on a superimposed breadth-first tree,
and the center is the root of this tree.) The central node does the final elimination,
which yields the output MST tree.
The details of each part are given in the remainder of the paper, followed by the
analysis of the total complexity.
3. Part I: Controlled-GHS. In this section we provide a modified, controlled
version of the Gallager-Humblet-Spira algorithm for MST that is suitable for our
purposes. We first provide a brief overview of the original algorithm of [GHS].
3.1. Brief description of the GHS algorithm. In the original distributed
algorithm of [GHS], nodes form themselves into fragments of increasing size. Initially,
all nodes are in singleton fragments. Nodes in each fragment F are connected by edges
that form a rooted MST, T (F ), for the fragment. (Initially, the sole node comprising
a fragment is also its root.) Each node (other than the root) in a fragment has a
pointer to one of its neighbors, which is the next node on the path over the tree to
the root; moreover, each node “knows” the root Id. (In the remainder of this paper
we loosely use the word “fragment” to mean both the collection of nodes F and the
corresponding tree T (F ).)
The events in the algorithm are divided into phases. Each phase takes as its input
the fragment structure output by the previous one and outputs larger fragments. (The
first phase takes as an input the singleton fragments, one per node.)
Let us now describe one phase. We present a simplified version of the GHS
algorithm compared to the original algorithm of [GHS]. (The original version is more
complex because of the desire to save messages and because of the asynchronous
nature of the networks for which it was designed.)
Within each fragment F , nodes cooperate to find the minimum-weight outgoing
edge in the entire fragment (an outgoing edge of a fragment F is an edge with one
endpoint in F and another at a node outside it). The strategy for identifying this
edge involves broadcasting over the fragment’s tree T (F ), asking each node separately
for its own minimum-weight outgoing edge. These edges are then sent upwards on
the tree T (F ), toward the root. Each intermediate node first collects this information
from all its children in the tree and then passes up only the lowest-weight edge it has
seen (which is therefore the lowest-weight edge in its subtree). The minimum-weight
outgoing edge is selected by the root to be included in the final MST.
Once a fragment’s minimum-weight outgoing edge is found, a message is sent out
over that edge to the chosen fragment on the other side. The two fragments then
combine, possibly along with several other fragments, into a new, larger fragment. If
the other fragment chose the same edge, then the two fragments agree at that point to
combine, and the edge they both chose is termed the core edge. Otherwise, following
the route from a fragment F1 , to its chosen fragment F2 , to F2 ’s chosen fragment F3 ,
and so on, [GHS] show that one must eventually reach two fragments that agree to
combine over a core edge. The combined fragment includes these two, as well as all
those other fragments that have such a route to them.
308 JUAN GARAY, SHAY KUTTEN, AND DAVID PELEG

The combined fragment has a root; it is the node with the higher Id of the two
endpoints of the core edge. (This can be simulated in the case that nodes do not have
distinct Id’s but edges have distinct weights.)
This concludes the description of a single phase. In the next phase, the new frag-
ment finds its own minimum-weight outgoing edge, and the entire process is repeated
until all the nodes in the graph have combined themselves into one single fragment.
Each fragment (of size 2 or greater) is identified by the fragment’s core edge and root.
We remark that in the original GHS algorithm, all nodes operate asynchronously.
This creates the risk of undesirable “growth patterns” of fragments, resulting in exces-
sive communication costs (measured in number of messages). This problem is handled
by using special rules for merging fragments, designed to prevent these complications.
These rules are based on a “balanced data structure” approach. A phase number is
associated with each fragment. If phase(F ) = l for a given fragment F , then the
number of nodes in F is greater than or equal to 2l . Initially, all fragments (singleton
nodes) are at phase 0. When two fragments at phase l are combined together, the
resulting new fragment has phase l + 1. Thus, the total number of messages is kept
to O(n log n) (although some more complex rules are needed to allow merges between
fragments of unequal phases). Similarly, it is not hard to show by induction on the
phase numbers that the time complexity of the algorithm is O(n log n) time units.
We refer the reader to [GHS] for further details.
3.2. Computing a small dominating set on a tree. In this subsection we
present a procedure Small-Dom-Set for computing a small dominating set on a given
tree. The procedure makes use of a subprocedure for computing a maximal indepen-
dent set in the tree. (A set M of vertices in a tree T is said to dominate the tree
if every vertex outside M has a neighbor in M .) A distributed version of procedure
Small-Dom-Set will later be used as a component in our Controlled-GHS algorithm,
which is a modification of GHS.
Our goal is as follows. Given a rooted tree T with a vertex set V (T ), find a set
of vertices M ⊆ V (T ) such that
1. M dominates V (T ), and
2. |M | ≤ |V (T
2
)|
.
Furthermore, we would like this procedure to be amenable to a fast distributed
implementation.
The procedure is based on the following. For a vertex v ∈ V (T ), let Child(v)
denote the set of v’s children in T . We use a level function Ľ(v) on the nodes, defined
as follows:

0 if v is a leaf,
Ľ(v) =
1 + minu∈Child(v) (Ľ(u)) otherwise.

We denote by Ľi the set of tree nodes at level i,

Ľi = {v | Ľ(v) = i}.
Procedure Small-Dom-Set for computing a dominating set M on a tree T is presented
next.
Algorithm Small-Dom-Set
1. Mark the nodes of T with level numbers Ľ(v) = 0, 1, 2;
2. Select an MIS, Q, in the set R of unmarked nodes;
3. M ← Q ∪ Ľ1 .
 SUBLINEAR TIME DISTRIBUTED MST ALGORITHM 309

L(v)>2 MIS

L(v)=2 non-MIS
L(v)=1
L(v)=0

(a) (b)

Fig. 1. (a) The level numbers marked by the algorithm on a given tree T . (b) A small domi-
nating set M on the tree T .

A pictorial example is given in Figure 1.

For the distributed implementation discussed in the next subsection, it is impor-
tant to note that although the level numbers Ľ(v) are defined for every vertex v in the
tree, only the vertices belonging to the first three levels, Ľ0 , Ľ1 , and Ľ2 , are actually
marked.
The fact that procedure Small-Dom-Set produces a dominating set is established
by the following lemma.
Lemma 3.1. Let M be the outcome of procedure Small-Dom-Set on the tree T .
Then for every node v 6∈ M there exists an adjacent node v 0 ∈ M .
Proof. Partition V (T ) into Ľ0 ∪ Ľ1 ∪ Ľ2 ∪ R. The set M output by procedure
Small-Dom-Set is composed of Q ∪ Ľ1 . Now, by choice of Q, it dominates each node
of R \ Q. Also, each node of Ľ0 ∪ Ľ2 has a neighbor in Ľ1 .
The “smallness” of the resulting dominating set is guaranteed by the following
lemma.
Lemma 3.2. |M | ≤ |V (T 2
)|
.
Proof. By construction, M = Ľ1 ∪ Q. It is clear that |Ľ1 | ≤ |Ľ0 |, and hence

|Ľ0 ∪ Ľ1 |
(1) |Ľ1 | ≤ .
2
We now claim that
|R ∪ Ľ2 |
(2) |Q| ≤ .
2
This can be proved by selecting for every v ∈ Q a distinct match ω(v) ∈ (R ∪ Ľ2 ) − Q,
thus establishing that |R ∪ Ľ2 | ≥ 2 · |Q|. The matching is done as follows: pick ω(v) to
310 JUAN GARAY, SHAY KUTTEN, AND DAVID PELEG

be an arbitrary child of v (by definition, vertices in Q always have children in R ∪ Ľ2 ).

Distinctness is guaranteed by the fact that each node in the tree has a unique parent.
It now follows from (1) and (2) that

|R ∪ Ľ2 | |Ľ0 ∪ Ľ1 | |V (T )|

|M | = |Q ∪ Ľ1 | ≤ + = .
2 2 2
3.3. Controlled-GHS.
3.3.1. Description of the Controlled-GHS procedure. In this subsection, we
provide the modified, controlled version of GHS (named Controlled-GHS) that is able
to achieve the following:
1. Upon termination, the number of fragments is bounded from above by N (for
N to be specified later).
2. Throughout the execution, the diameter of every fragment F satisfies Diam(F )
≤ d (for d to be specified later).
Intuitively, since we focus on a synchronous algorithm, and we do not care about
communication complexity, our version of GHS is simpler than the original algorithm.
In particular, we are oblivious to balancing fragment sizes, and we do not need to use
the phase rules used in the original algorithm, since phases are imposed by phase
synchronization (using the assumed global clock).
More specifically, Controlled-GHS starts with singleton fragments, just like GHS
(see subsection 3.1), and executes a total of I phases. Each phase outputs a collection
of fragments that serve as the input for the next phase. A fragment is a rooted tree,
where each node (except for the root) has a pointer to the edge that leads to its parent
in the tree. Each phase of Controlled-GHS consists of the following two stages.
Stage 1. Consider the fragments that are input to the phase. Execute a
phase of GHS up to a point where each such input fragment F has chosen its
minimum-weight outgoing edge, i.e., has decided with which other fragment
in the current fragment collection it wants to merge.
This decision induces a “forest” structure on the fragment collection (possibly
with length-2 loops at the tree roots). Henceforth we refer to this structure
as the fragment forest, denoted F F .
Stage 2. Break the resulting trees into “small” (O(1) depth) trees, and merge
only these small trees.
This process is depicted in Figure 2. To accomplish Stage 2, the algorithm first
computes a dominating set MF F (T̃ ) on each tree T̃ of the fragment forest F F . Note
that the nodes of this tree are input fragments of the current phase of the algorithm.
Let MF F be the union over the trees T̃ (of the F F forest) of MF F (T̃ ). The algorithm
then lets each fragment F 6∈ MF F pick one neighboring fragment F 0 ∈ MF F and merge
with it. This causes the actual merges performed in a phase of Controlled-GHS to
have the form of “stars” in the fragment forest F F , and prevents merges along long
chains, hence bounding the diameter of the resulting fragments.
The dominating sets are computed using a distributed implementation of pro-
cedure Small-Dom-Set, denoted Dist-SDS, applied separately to each tree T̃ in the
fragment forest F F . A key aspect in this computation is the use of a distributed al-
gorithm for computing a maximal independent set. Most distributed MIS algorithms
in the literature (e.g., [AGLP, PS2]) can be used for our purposes. In fact, our solu-
tion only requires to compute an MIS on a tree, so we can use a distributed version
of the algorithm of [GPS], which is optimal for trees. (This algorithm makes use of
O(log n)-bit messages and therefore can be used within our model.)
 SUBLINEAR TIME DISTRIBUTED MST ALGORITHM 311

Fig. 2. A phase of Controlled-GHS: the tree T of Figure 1b is broken into “small” trees
(represented by the solid edges) according to the MIS.

The algorithm of [GPS] (henceforth referred to as the GPS algorithm) has the
following properties.
Lemma 3.3 (see [GPS]). Applied in a given n-vertex tree G, Algorithm GPS
computes (in a synchronous manner) a maximal independent set (MIS) of G using
O(log n)-bit messages, and its time complexity is O(log∗ n).
Note that although procedure Dist-SDS is applied to the trees of the fragment
forest F F , it is actually executed on the original network itself. Hence the procedure
operates by simulating each fragment by a single representative, say, its root.
3.3.2. Analysis of controlled-GHS. The bounds on the number and diameter
of fragments are established by the next lemma. Given a fragment forest F F , let
Diam(F F ) = maxF ∈F F {Diam(F )}. Let F Fi denote the fragment forest produced
by the algorithm Controlled-GHS at the end of the ith phase. (F F0 is the initial set
of vertices.)
Lemma 3.4. In each phase i of Controlled-GHS,
1. the number of fragments at least halves, i.e., |F Fi | ≤ |F Fi−1 |/2, and
2. the maximum diameter of a fragment increases by a factor of at most 3
(possibly plus 2), i.e., Diam(F Fi ) ≤ 3Diam(F Fi−1 ) + 2.
Proof. The number of new fragments in each tree T = T (F ) of the fragment forest
F F at the end of a phase is equal to |M (T )|. By Lemma 3.2, |M (T )| ≤ |V (T )|/2.
Hence the same holds for the entire fragment forest, and claim 1 of the lemma follows.
Claim 2 is readily satisfied since the merges are star shaped.
Corollary 3.5. After running Controlled-GHS for I phases,
312 JUAN GARAY, SHAY KUTTEN, AND DAVID PELEG

1. the number of fragments in F FI is at most N (I) = 2nI , and

2. Diam(F FI ) ≤ d(I) = 3I − 1 for every fragment F .
Let us now turn to analyzing the time complexity of Controlled-GHS. We first
examine the performance of procedure Dist-SDS.
Lemma 3.6. When executed on a fragment forest F F , procedure Dist-SDS takes
time O(log∗ n) · Diam(F F ).
Proof. It is easy to see that if a fragment F is a leaf in the fragment forest F F ,
then it identifies itself as such, and subsequently marks itself Ľ0 , in time O(Diam(F )).
Similarly, fragments mark themselves Ľ1 and Ľ2 in time O(Diam(F )) as well. An-
other part that affects the time complexity is the MIS computation. By Lemma
3.3, the time complexity of the GPS algorithm is O(log∗ n). Note that since the pro-
cedure is executed on the original network itself, it is slowed down by a factor of
O(Diam(F F )). Hence the implementation of the GPS algorithm on the fragments of
F F is slowed down to O(log∗ n) · Diam(F F ) in our case.
The properties of the Controlled-GHS algorithm are now summarized by the
following graph decomposition lemma.
Lemma 3.7. When Algorithm Controlled-GHS is activated for I phases, it takes
O(3I · log∗ n) time and yields a fragment forest F FI of up to N (I) = n/2I fragments,
of diameter Diam(F FI ) ≤ d(I) = 3I − 1. Each fragment in the forest is a fragment
of an MST of the graph G.
Proof. By Lemma 3.6, each phase i, 1 ≤ i ≤ I, of Controlled-GHS takes time
at most Diam(F Fi−1 ) · O(log∗ n). By Corollary 3.5, this is at most 3i−1 · O(log∗ n).
Thus, the total time is given by
X
(3i−1 · O(log∗ n)) ≤ 3I · O(log∗ n) .
i≤I

The size and diameter properties of the resulting fragment forest follow directly from
Corollary 3.5.
The rather even graph decomposition obtained by Algorithm Controlled-GHS
may conceivably be useful for other purposes as well.
4. Part II: Edge elimination. The second part of our algorithm starts at the
point where we are given a fragment graph F̃l , whose vertex set V (F̃l ) is a fragment
forest F FI containing N ≤ N (I) fragments of the MST, and whose edge set E(F̃l ) is
a collection of interfragment edges, which are the remaining candidates for joining the
MST. We now proceed to reduce the total number of remaining interfragment edges
(to the necessary N − 1).
4.1. The pipeline algorithm. We need the following technical definition. For
a set of edges Q and a cycle-free subset U ⊆ Q, define Cyc(U, Q) as the set of all
edges e ∈ Q \ U such that U ∪ {e} contains a cycle.
We are now ready to describe our pipelined procedure, given in Figure 3.
4.2. Analysis. Our analysis hinges on two main properties of the procedure.
First, the edges reported by each intermediate node to its parent in the tree are
sent in nondecreasing weight order. Second, each intermediate node transmits edges
upwards in the tree continuously until it exhausts all the reportable edges from its
subtree; namely, once the set of candidates RC is empty, the node will learn of no
more reportable edges.
Let us first make the following straightforward but crucial observation.
 SUBLINEAR TIME DISTRIBUTED MST ALGORITHM 313

1. Build a breadth-first-search tree B on G, with a root r(B).

2. Throughout the execution, each node v on the tree maintains a
set Q of all the interfragment edges it knows of (either directly or
by “learning” from its children in the previous rounds), ordered
by nondecreasing edge weights. Initially this set contains only
the interfragment edges adjacent to it. It also maintains a set U
(initially empty) of all the edges it has already sent up to its parent
in the tree.
3. A leaf v starts sending edges upwards at pulse 0. An intermedi-
ate node v starts sending at the first pulse after it has received
messages from all its children.
4. At each pulse i, the node sends up to its parent in the tree the
lightest edge e in Q that has not been sent up in the previous
rounds up to round i − 1 (i.e., e 6∈ U ), and which does not close
a cycle with the edges of U . If no such edge exists then terminate
participation in the pipelining part of the procedure (i.e., go to
step 6).
More formally, the node computes the set of remaining candidates
(RC)

RC = Q \ (U ∪ Cyc(U, Q)).

If RC = ∅, then v sends a “terminating” message to its parent in

the tree and terminates its participation in the pipelining part of
the protocol; else, it sends up to its parent the lightest edge e in
RC.
5. The root r(B) computes locally the set S of the N − 1 edges par-
ticipating in the MST of the fragment graph F̃ from among the
edges it hears of from its children.
6. The root r(B) then broadcasts (over the tree B) the resulting set of
N − 1 interfragment edges (constituting the MST for the fragment
graph F̃ ) to all nodes in G.

Fig. 3. Procedure Pipeline.

Lemma 4.1. The edges reported by each intermediate node to its parent in the
tree form a forest.
Proof. This follows immediately from the rule used by the procedure to select the
next edge to be transmitted upwards.
Lemma 4.2. Every node v starts sending messages upwards at pulse Ĥ(v), where
Ĥ(v) is the height function defined as follows:

0 if v is a leaf ;
Ĥ(v) =
1 + maxu∈Child(v) (Ĥ(u)) otherwise.

Proof. The proof is straightforward by induction on the tree structure, from the
leaves upward.
Our main technical lemma concerns the properties of a node on the tree in some
round of the algorithm. Consider an intermediate node v at height H that has still
314 JUAN GARAY, SHAY KUTTEN, AND DAVID PELEG

not terminated its participation in the algorithm, at round t, for some t ≥ H. Note
that each of the children of v in the tree is of height H − 1 or lower, hence, by Lemma
4.2, all of them started transmission at round H − 1 or earlier. Call a child active if
it has not terminated yet (i.e., it has upcast an edge to v on round t − 1). Let

At (v) = {v1 , . . . , vp }

be the set of v’s active children at round t.

Lemma 4.3.
(a) At the beginning of round t, the candidate set RC examined by v contains
at least one candidate edge upcast by each of its active children from At (v).
(b) If v upcasts an edge of weight ω at round t, then all of the edges which
v was informed of at round t − 1 by its active children were of weight ω or
greater.
(c) If v upcasts an edge of weight ω at round t, then any later edge it will
learn of is of weight ω or greater.
(d) Node v upcasts edges in nondecreasing weight order.
Proof. We prove the lemma by induction on the height of the tree, starting from
the leaves upwards.
A leaf v has no (active or other) children, and therefore claims (a), (b), and (c)
hold vacuously. Claim (d) follows trivially from the rules of the procedure.
Let us now consider an intermediate node v, and assume that the claims hold for
each of its children. We need to prove the four claims for v. We start with claim (a).
Let U be the set of m edges upcast by v during the first m = t − H rounds it
has participated in (namely, rounds H, . . . , t − 1 if t > H). By Lemma 4.1, U forms
a forest in G. Consequently, break U into the trees U1 , . . . , U` in G, with xi = |Ui |,
where each such tree Ui has a vertex set V (Ui ) of exactly xi + 1 vertices, and

X
(3) xi = |U | = m.
i

Consider an active child u of v. Denote by D the set of edges upcast by u so

far (up to and including round t − 1). Since u was still active on round t − 1, it has
transmitted continuously to v since round Ĥ(u), which, as discussed before, is at most
H − 1. Therefore, we conclude that

(4) |D| ≥ m + 1.

Suppose, for the sake of contradiction, that none of the edges upcast by u is a
candidate in round t. In other words, for each edge e ∈ D, either e was upcast by v
earlier (namely, e ∈ U ), or e closes a cycle with the edges of U (namely, e ∈ Cyc(U )).
Thus, every such edge e has both of its endpoints in U . Furthermore, e cannot possibly
connect endpoints that belong to two different trees Ui and Uj (since in that case, e
would have been in neither U nor Cyc(U )).
This implies that the set D can be partitioned into sets D1 , . . . , D` such that all
the edges of Di are restricted to vertices V (Ui ) of the tree Ui , for 1 ≤ i ≤ `. Moreover,
notice that each such set Di is a forest, since the entire set D is a forest by Lemma
4.1.
The last two facts combined imply that

(5) |Di | ≤ |V (Ui )| − 1 = xi .

 SUBLINEAR TIME DISTRIBUTED MST ALGORITHM 315

Combining (3), (4), and (5) we get

X X
m + 1 ≤ |D| = |Di | ≤ xi = m,
i i

which is a contradiction. Hence claim (a) must hold.

Next we prove claim (b) as follows. Consider any active child u of v. Let e be
the edge upcast by u on round t − 1. (Note that e does not necessarily have to be in
RC.) Let e0 be some edge that was upcast by u at some round t0 ≤ t − 1 and is still
in the candidate set RC on round t (such an edge must exist by claim (a)). By the
inductive hypothesis of claim (d), ω(e) ≥ ω(e0 ). By the edge selection rule of node v,
ω(e0 ) ≥ ω, and claim (b) follows.
Next we note that claim (c) follows trivially from claim (b). Finally, claim (d)
follows trivially from claim (c) and the edge selection rule of the procedure.
Finally, we need to argue that nodes do not terminate the algorithm prematurely.
Lemma 4.4. After a node v has terminated its participation in the algorithm, it
will learn of no more reportable edges.
Proof. We need to argue that once the set RC becomes empty, no new candidate
edges will become known to v. We prove this fact by induction on the structure of
the tree, starting from the leaves upward. The inductive step follows directly from
claim (a) of Lemma 4.3, which guarantees that if RC is empty on round t, none of
v’s children have upcast it an edge in round t − 1, and hence all of them have already
terminated.
Lemma 4.5. The running time of procedure Pipeline is bounded by O(N +
Diam(G)), and its output is an MST for G.
Proof. The fact that the resulting tree is an MST follows from the fact that
the trees constructed in the first stage were fragments of the MST, and from the
correctness of the “red rule” employed for edge elimination in the procedure (cf. [T,
p. 71]). (Essentially the red rule says that an edge that is the heaviest on any cycle
is not a part of any MST.)
As for the running time, the bound is derived from the following facts. First,
the root of the tree receives at most N edges from each of its children. Second, the
children send these edges to the root in a fully pipelined fashion (namely, without
stopping until exhausting all the edges they know of). Finally, the root starts getting
such messages at time Diam(G) at the latest.
5. The complexity of the combined algorithm. Combining the two parts,
we get the following distributed algorithm for MST.
1. Perform Algorithm Controlled-GHS for I phases.
2. Perform Algorithm Pipeline.
Summarizing the results of the last two sections, we get the following theorem.
Theorem 5.1. There exists a distributed MST algorithm with time complexity
O(Diam(G) + nε · log∗ n) for ε = ln 3
ln 6 = 0.6131... .
Proof. The complexities of the two parts of our algorithm are as follows, for the
given parameter I specified for the first part:
Part I: 3I · O(log∗ n).
Part II: Diam(G) + 2nI .
The total time complexity is thus optimized when choosing I such that 3I = 2nI ,
namely, I = ln n I n ε ln 3
ln 6 . For this choice of I, we get 3 = 2I = n for ε = ln 6 , which yields
ε ∗
a total time complexity of O(Diam(G) + n · log n).
316 JUAN GARAY, SHAY KUTTEN, AND DAVID PELEG

Acknowledgments. It is a pleasure to thank Ambuj Singh and Jerry James for

useful comments. Thanks are also due to two anonymous referees for their comments,
which helped to significantly improve the readability of the paper.

REFERENCES

[ADDJ] I. Althöfer, G. Das, D. Dobkin, and D. Joseph, Generating sparse spanners for
weighted graphs, in Proc. 2nd Scandinavian Workshop on Algorithm Theory, Lec-
ture Notes in Comput. Sci. 447, Springer-Verlag, New York, 1990, pp. 26–37.
[A1] B. Awerbuch, Optimal distributed algorithms for minimum-weight spanning tree, count-
ing, leader election and related problems, in Proc. 19th ACM Symp. on Theory of
Computing, ACM, New York, 1987, pp. 230–240.
[A2] B. Awerbuch, Complexity of network synchronization, J. ACM, 32 (1985), pp. 804–823.
[AGLP] B. Awerbuch, A. Goldberg, M. Luby, and S. Plotkin, Network decomposition and
locality in distributed computation, in Proc. 30th IEEE Symp. on Foundations of
Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1989, pp. 364–
375.
[AGPV] B. Awerbuch, O. Goldreich, D. Peleg, and R. Vainish, A tradeoff between information
and communication in broadcast protocols, J. ACM, 37 (1990), pp. 238–256.
[AKP] B. Awerbuch, S. Kutten, and D. Peleg, Competitive distributed job load balancing,
Proc. 24th ACM Symp. on Theory of Computing, ACM, New York, 1992, pp. 571–
580.
[AP1] B. Awerbuch and D. Peleg, Network synchronization with polylogarithmic overhead,
in 31st IEEE Symp. on Foundations of Computer Science, IEEE Computer Society
Press, Los Alamitos, CA, 1990, pp. 514–522.
[AP2] B. Awerbuch and D. Peleg, Concurrent online tracking of mobile users, Proc. ACM
SIGCOMM Symposium on Communication, Architectures and Protocols, ACM, New
York, 1991, pp. 221–233.
[B] B. Bollobás, Extremal Graph Theory, Academic Press, New York, 1978.
[CT] F. Chin and H. F. Ting, An almost linear time and O(n log(n) + e) messages distributed
algorithm for minimum-weight spanning trees, in Proc. 26th IEEE Symp. on Founda-
tions of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1985,
pp. 257–266.
[G] E. Gafni, Improvements in the time complexity of two message-optimal election algo-
rithms, in Proc. 4th Symp. on Principles of Distributed Computing, ACM, New York,
1995, pp. 175–185.
[GHS] R. Gallager, P. Humblet, and P. Spira, A distributed algorithm for minimum-weight
spanning trees, in ACM Trans. Programming Lang. Systems, 5 (1983), pp. 66–77.
[GKP] J. Garay, S. Kutten, and D. Peleg, A sub-linear time distributed algorithm for
minimum-weight spanning trees, in Proc. 34th IEEE Symp. on Foundations of Com-
puter Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 659–668.
[GPS] A. V. Goldberg, S. Plotkin, and G. Shannon, Parallel symmetry breaking in sparse
graphs, in Proc. 19th ACM Symp. on Theory of Computing, ACM, New York, 1987,
pp. 315–324.
[L] N. Linial, Distributive graph algorithms—global solutions from local data, in Proc. 28th
IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press,
Los Alamitos, CA, 1987, pp. 331–335.
[MRR] J. M. McQuillan, I. Richer, and E. C. Rosen, The new routing algorithm for the
ARPANET, IEEE Trans. Comm., COM-28 (1980), pp. 711–719.
[P] D. Peleg, Time-optimal leader election in general networks, J. Parallel Distrib. Comput.,
8 (1990), pp. 96–99.
[PS1] D. Peleg and A. A. Schäffer, Graph spanners, J. Graph Theory, 13 (1989), pp. 99–116.
[PS2] A. Panconesi and A. Srinivasan, Improved distributed algorithms for coloring and net-
work decomposition problems, in Proc. 24th ACM Symp. on Theory of Computing,
ACM, New York, 1992, pp. 581–592.
[T] R. E. Tarjan, Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983.