The Singular Optimality of Distributed Computation in LOCAL

In the ${\text{KT}}_0$ model (i.e., Knowledge Till radius 0), also called the clean network model [41], where nodes have initial local knowledge of only themselves (and not of their neighbors), it has been established that one can obtain (near) singularly optimal distributed algorithms, i.e., algorithms that have simultaneously optimal time and message complexity up to polylogarithmic factors, for many fundamental global problems¹¹1These problems require traversing the entire network to compute their solution and hence take $\mathrm{\Omega }(D)$ rounds, where $D$ is the network diameter. such as leader election, broadcast, Spanning Tree (ST), Minimum Spanning Tree (MST), minimum cut, and approximate shortest paths (under some conditions) [34, 40, 17, 26]. For problems such as leader election, broadcast, and ST, it has been shown that one can design a singularly optimal algorithm in the ${\text{KT}}_0$ model that takes $\tilde{O}(m)$ messages ($m$ is the number of edges of the network, and $\tilde{O}(\cdot )$ suppresses logarithmic factors) and $O(D)$ rounds ($D$ is the network diameter); both are tight (up to a $\text{polylog}(n)$ factor where $n$ is the number of nodes) due to matching lower bounds that hold even for Monte Carlo randomized algorithms [34]. In addition, MST also admits a singularly optimal algorithm [40, 17] with message complexity $\tilde{O}(m)$ and round complexity $\tilde{O}(D+\sqrt{n})$ (both bounds are tight up to polylogarithmic factors). The singular optimality of MST in the ${\text{KT}}_0$ model also implies the singular optimality of many other problems, such as approximate minimum cut and graph verification problems [12].

On the other hand, in the ${\text{KT}}_1$ model (i.e., Knowledge Till radius 1), in which each node has initial knowledge of itself and the identifiers²²2We stress that only knowledge of the identifiers of the neighbors is assumed, not other information such as the degree of the neighbors. of its neighbors, singular optimality of all the above fundamental problems is wide open. The ${\text{KT}}_1$ model arises naturally in many settings, e.g., in networks where nodes know the identifiers of their neighbors (as well as other nodes), e.g., on the Internet, where a node knows the IP addresses of other nodes. Similarly, in models such as the Congested Clique [27] and the $k$-machine model [32, 28], it is natural to assume that each processor knows the identifiers of all other processors. For the ${\text{KT}}_1$ CONGEST model (where messages are of small size, typically $O(\log n)$), King, Kutten, and Thorup (henceforth, KKT) [31] showed that one can solve several fundamental global problems (with the notable exception of BFS tree construction) such as broadcast, leader election, and spanning tree construction in message complexity of $\tilde{O}(n)$ ($n$ is the network size) which can be significantly smaller than $m$. (This is in contrast to the ${\text{KT}}_0$ model where $\mathrm{\Omega }(m)$ is a lower bound of the message complexity.) Randomization is crucial in obtaining this result, and the algorithm is not comparison-based.³³3Comparison-based algorithms can operate on identifiers only by comparing them, i.e., given two IDs, one can only determine whether one is less, greater, equal to the other. We note that Awerbuch, Goldreich, Peleg, and Vainish [2] show that $\mathrm{\Omega }(m)$ is a message lower bound for MST even in the ${\text{KT}}_1$ CONGEST model, for all deterministic algorithms (even non-comparison based) and all randomized (even Monte Carlo) comparison-based algorithms. The KKT result breaks the $\mathrm{\Omega }(m)$ message barrier in ${\text{KT}}_1$ CONGEST by using a randomized non-comparison-based technique that uses node IDs as inputs to hash functions.

While the message complexity of the KKT result is near-optimal (as $\mathrm{\Omega }(n)$ is a lower bound on the message complexity even in ${\text{KT}}_1$ – see, e.g., [38]), their round complexity is $\tilde{O}(n)$, which is far from the standard lower bound of $\mathrm{\Omega }(D)$ for the leader election, broadcast, and ST problems. An important open question is whether one can achieve singular optimality for the above problems in the ${\text{KT}}_1$ CONGEST model, i.e., whether there exists an algorithm running in $\tilde{O}(D)$ rounds and $\tilde{O}(n)$ messages. Another important and related question is whether the fundamental BFS tree construction can be solved in $\tilde{O}(n)$ messages (regardless of the number of rounds as long as it is a polynomial in $n$) in ${\text{KT}}_1$.

Similarly, for the MST problem, the KKT algorithm also showed that one can achieve $\tilde{O}(n)$ message complexity, but it is not time-optimal – it can take significantly more than $\tilde{\mathrm{\Theta }}(D+\sqrt{n})$ rounds, which is a time lower bound for MST that applies even for Monte Carlo randomized algorithms [12]. In subsequent work, Mashreghi and King [35] presented a trade-off between messages and time for MST: a Monte Carlo algorithm that uses $\tilde{O}(\frac{n^{1+ϵ}}{ϵ}\log \log n)$ messages and runs in $O(n/ϵ)$ time for any $1>ϵ\ge \log \log n/\log n$. This algorithm also takes $\mathrm{\Omega }(n)$ time. Hence another natural and fundamental open question is whether we can design an MST algorithm in the ${\text{KT}}_1$ CONGEST model that is singularly optimal, i.e., runs in $\tilde{\mathrm{\Theta }}(D+\sqrt{n})$ rounds, while using $\tilde{\mathrm{\Theta }}(n)$ messages. We note that a singularly optimal algorithm for such a problem is far from certain. Robinson [43] showed a message complexity lower bound for constructing a $(2k-1)$-spanner in the ${\text{KT}}_1$ CONGEST model, which implies that obtaining singularly optimal algorithms for graph spanners of $O(n^{1+1/k+ϵ})$ edges, for any constant $ϵ>0$, is impossible in polynomial time. However, for many fundamental graph problems, including broadcast, ST, leader election, and MST, the quest for singularly optimal algorithms is still unresolved.

Gmyr and Pandurangan [24] presented several results that show that tradeoffs between time and messages in the ${\text{KT}}_1$ CONGEST model are possible for various fundamental problems. (See also the related results of [19].) The time-message tradeoff results are based on a uniform and general approach which involves constructing a sparsified spanning subgraph of the original graph – called a danner (i.e., “diameter-preserving spanner”) – that trades off the number of edges with the diameter of the sparsifier. A key ingredient of this approach is a distributed randomized algorithm that, given a graph $G$ and any $\delta \in [0,1]$, with a high probability constructs a danner that has diameter $\tilde{O}(D+n^{1-\delta })$ and $\tilde{O}(\min \{m,n^{1+\delta }\})$ edges in $\tilde{O}(n^{1-\delta })$ rounds while using $\tilde{O}(\min \{m,n^{1+\delta }\})$ messages, where $n$, $m$, and $D$ are the number of nodes, edges, and the diameter of the input graph $G$, respectively. Using a danner, they show that the leader election, broadcast, and ST problems can be solved in $\tilde{O}(D+n^{1-\delta })$ rounds using $\tilde{O}(\min \{m,n^{1+\delta }\})$ messages for any $\delta \in [0,1]$. Another important consequence of the danner construction is that the MST and connectivity problems can be solved in $\tilde{O}(D+n^{1-\delta })$ rounds using $\tilde{O}(\min \{m,n^{1+\delta }\})$ messages for any $\delta \in [0,0.5]$. In addition to getting any desired tradeoff (by plugging in an appropriate $\delta$), one can get a time-optimal algorithm by choosing $\delta =0.5$, which results in a distributed MST algorithm that runs in $\tilde{O}(D+\sqrt{n})$ rounds and uses $\tilde{O}(\min \{m,n^{3/2}\})$ messages. (Note that this result is time-optimal but not message-optimal.) While these results improve over prior bounds in the ${\text{KT}}_1$ CONGEST model [31, 35, 2], they do not answer the question of whether singularly optimal algorithms exist for fundamental global problems in the ${\text{KT}}_1$ CONGEST model, nor do they show that the tradeoff bounds are tight.

The work of Bitton et al. [7] is the most similar in spirit to this work and raises and answers the same questions but for local problems. By local problems, we mean problems with $t$-round algorithms for small $t$ (say, polylogarithmic in $n$) in the LOCAL model. In particular, they ask the following question: Given a LOCAL algorithm that runs in $t$ rounds, is it possible to design an algorithm that takes $O(t)$ rounds while sending only $O(n^{1+ϵ})$ messages for an arbitrarily small constant $ϵ>0$? They point out that this question can be resolved if one can construct an $\alpha$-spanner of $G$ with $O(1)$ stretch and $O(n^{1+ϵ})$ edges in $O(1)$ rounds sending $O(n^{1+ϵ})$ messages. They also point out that, despite the extensive literature on distributed spanner construction algorithms, it is not known whether such a LOCAL spanner construction algorithm exists.

They then present message-reduction schemes for LOCAL algorithms under the ${\text{KT}}_1$ assumption⁴⁴4Actually, their results also hold in a somewhat weaker model where edges have unique IDs which are known to both endpoints. that preserve their asymptotic time complexity. They point out that the gossip-based algorithms of [8, 25] imply that a $t$-round algorithm in the LOCAL model can be transformed into an algorithm in the LOCAL model that runs in $O(t\log n+{\log }^{2}n)$ rounds and $O(nt\log n+n{\log }^{2}n)$ messages. Then they show how to transform a $t$-round LOCAL algorithm into an $O(t)$-round algorithm that uses $O(t{n}^{1+ϵ})$ messages for an arbitrarily small constant $ϵ>0$. We refer to [7] for more details.

An implication of the work of [8, 25] is that local problems admit (nearly) singularly optimal algorithms. For example, fundamental local problems such as MIS (Maximal Independent Set), coloring, and maximal matching admit $O(\log n)$-round algorithms, and hence one can design algorithms for these problems that run in $O({\log }^{2}n)$ rounds and $O(n{\log }^{2}n)$ messages in ${\text{KT}}_1$ LOCAL. It is important to point out that the above results do not help in designing singularly optimal algorithms for global problems, which require $\mathrm{\Omega }(D)$ rounds. This is the focus of this paper.

The motivating question underlying this work is understanding the status of various fundamental global problems in the ${\text{KT}}_1$ model – whether they are singularly optimal or exhibit trade-offs (and, if so, to quantify the trade-offs). In particular, an important open question is whether one can design a randomized (non-comparison-based) algorithm for broadcast or for leader election that takes $\tilde{O}(D)$ time and $\tilde{O}(n)$ messages in the ${\text{KT}}_1$ CONGEST model. Also, King et al. [31] ask whether it is possible to construct an ST in $o(n)$ rounds with $o(m)$ messages. As mentioned earlier, algorithms that are message-optimal, i.e., taking $\tilde{O}(n)$ messages, take $O(n)$ rounds. The situation is also wide open from a lower bound point of view: no lower bound is known on one measure conditional on the other measure being optimal. In particular, even $o(n)$-rounds message-optimal algorithms are not known.

Another important and related question is whether the fundamental BFS tree construction can be solved in $\tilde{O}(n)$ messages (in polynomial number of rounds) in ${\text{KT}}_1$. We note that the polynomial rounds restriction is necessary since the KKT result has an important implication for the ${\text{KT}}_1$ CONGEST model in general. Using this result, one can show that any problem can be solved in the ${\text{KT}}_1$ CONGEST model using $\tilde{O}(n)$ messages, provided exponentially many rounds are allowed [43]. This algorithm uses the KKT result to first construct a spanning tree and uses the “time encoding” trick to upcast the entire graph topology up the tree. In the “time encoding” trick, clock ticks are used to encode information, and a node can convey a lot of information by being silent for many clock ticks and then sending a bit at an appropriately chosen clock tick.

The main question that we address in this paper is whether singularly optimal algorithms for the above-mentioned fundamental global problems are possible in the ${\text{KT}}_1$ LOCAL model (where the size of a message is not restricted). Surprisingly, the answer is yes! Note that this is not obvious. In particular, the KKT algorithm to construct a spanning tree (even) in the LOCAL model takes $\tilde{O}(n)$ rounds in the worst case. On the other hand, one can construct a BFS tree and aggregate the entire topology in $O(D)$ rounds which is time optimal, but it is not known how to construct a BFS tree in $\tilde{O}(n)$ messages in ${\text{KT}}_1$ LOCAL.

We start with the correctness. We claim that in each phase $i\ge 1$, the lexicographically-first minimal outgoing edge set $O_i$ is correctly (and distributedly) computed. The correctness of the BFS tree computation follows straightforwardly from that claim. Let us prove the claim now. Each frontier node (say $v$) obtains its 2-hop neighborhood information due to the neighborhood property of the ($\kappa$, 2)-cover: one of the cover $v$ is contained in also contains all nodes in the 2-hop neighborhood of $v$. Then, $v$ pings this cover cluster tree (and others) during phase $i$, and during the second stage, the information of $v$’s 2-hop neighborhood (including which nodes are in the BFS) is gathered and then sent to $v$. (Note that sufficient runtime is given to the two stages by Proposition 1, and although $v$ receives different messages from the different cover cluster trees it belongs to, it can simply take the message containing the most information on $v$’s 2-hop neighborhood.) From this information, $v$ can compute which incident edge is in the lexicographically-first minimal outgoing edge set: for each neighbor $w$ of $v$, such that $w$ is not in the BFS, $v$ computes the lexicographically-first incident edge to $w$ with a BFS endpoint, and whether that edge is incident to $v$.

The round complexity is straightforward; computing the ($\kappa$, 2)-sparse neighborhood cover takes $O({\log }^{3}n)$ rounds by Lemma 6, and the $O(D)$ phases each take $O(\log n)$ rounds. We now bound the message complexity. First, computing the ($\kappa$, 2)-sparse neighborhood cover uses $O(n{\log }^{3}n)$ messages by Lemma 6. As for the BFS tree computation, we separate messages into two types: the BFS exploration messages, and the messages sent over the cover cluster trees (for the pinging, broadcasts and convergecast). The former travel only along minimal outgoing edge sets, which guarantees each non-root node receives such a message once, joins the BFS and never receives such a message again. Thus over all phases, at most $n$ BFS exploration messages are sent. For the latter, we first claim that we can bound the number of convergecasts and broadcasts executed per cover cluster tree over the algorithm by $O(\log n)$. Indeed, each cluster cover tree has diameter $O(\log n)$ due to our choice of $\kappa$, and thus its vertices can be contained in at most $O(\log n)$ layers of the BFS tree. Moreover, messages are sent over a cover cluster tree in a given phase if and only if one of its nodes is a frontier node (due to the pinging behavior) in that phase. As such, messages are sent over a given cover cluster tree during at most $O(\log n)$ phases, and within each such phase at most $O(1)$ convergecasts and broadcasts are executed, thus proving the claim. (In the above counting, we use the fact that the pinging operation sends less messages than a convergecast.) Given the claim, Proposition 1 and since each node belongs to $O({\log }^{2}n)$ different cover cluster trees by Lemma 5, the message complexity due to the second type of messages is $O(n{\log }^{3}n)$.$◀$

The above (near) singularly-optimal BFS algorithm can be transformed into a randomized leader election algorithm via an additional $\mathrm{\Theta }(\log n)$ factor in the message complexity as follows. Assuming nodes have some good estimate (i.e., within a constant factor) of the network size $n$, $\mathrm{\Theta }(\log n)$ candidates are picked uniformly at random. Then, these candidates each start an independent execution of the above BFS algorithm, and messages of different executions are differentiated by simply adding to the messages the candidate’s ID.

Note also that the above (near) singularly-optimal BFS algorithm can be made deterministic, but at the cost of higher logarithmic factors in both time and message complexities. We leave out the details however, because the deterministic solution given in the subsequent section is strictly more efficient in both time and message complexities. Instead, we give a brief sketch. The crucial point is that the randomized sparse neighborhood cover construction given in Section 2.3 is the only randomized component used in the above BFS construction. We can replace it with a message-efficient deterministic sparse neighborhood cover construction to obtain a message-efficient deterministic BFS construction algorithm. More concretely, one can combine the $(O({\log }^{3}n),W)$-sparse neighborhood cover construction of [21] (that takes as parameter any positive integer $W$) with the simulation of [8, 25] (as described in more detail in both Sections 1 and 4). Doing so gives a deterministic $(O({\log }^{3}n),W)$-sparse neighborhood cover construction algorithm that takes $O(W{\log }^{11}n)$ rounds and $O(n{\log }^{11}n)$ messages, and such that each cluster tree has depth $O({\log }^{3}n)$ and each edge appears in at most $O({\log }^{4}n)$ cluster trees. Moreover, if used in the above BFS construction algorithm, the resulting time and message complexities are respectively $O(D{\log }^{3}n+{\log }^{11}n)$ and $O(n{\log }^{11}n)$.

We define $H$ as the union of the links added to $E_v$, for each node $v$. Since the algorithm terminates in $O(\log n)$ iterations, it follows that the set of activated links $E_v$ of each node $v$ is of size $O(\log n)$, which implies the claimed upper bound on the number of edges in $H$.

It is shown in [25] that a node can exchange rumors with all its neighbors by activating the links in $H$ according to the schedule in the last iteration of the algorithm. As mentioned above, the number of rounds in iteration $i$ is $4i$, and hence the last iteration takes $O(\log n)$ rounds. In other words, the edges of $H$ ensure the existence of a path of length $O(\log n)$ between $v$ and each one of its neighbors, which shows that $H$ is a spanner with stretch $O(\log n)$. $◀$

To construct a BFS tree on the network $G$, we first initiate the construction of a BFS tree $T_H$ on $H$ by executing the simple flooding-based algorithm starting at the designated root node $s$. According to Lemma 9, this takes $O(D\log n)$ rounds and the number of messages sent is $O(|E(H)|)=O(n\log n)$. Then, we convergecast the entire topological information of each node starting at the leaves in $T_H$ up to the root $s$, thus enabling $s$ to locally compute a BFS tree $T$ on $G$. Finally, $s$ broadcasts the topological information of $T$ over the edges of $T_H$, which ensures that each node learns its parents and children in $T$. Since the broadcast and convergecast on $T_H$ both take $O(D\log n)$ rounds and $O(n\log n)$ messages, the complexity of constructing a BFS tree is dominated by the cost of constructing the spanner $H$, which yields the following:

If, instead of constructing a BFS tree, our goal is to elect a unique leader among the nodes, we leverage the deterministic ${\text{KT}}_0$ CONGEST leader election algorithm of [34], which, on general networks requires $O(D\log n)$ rounds and $O(m\log n)$ messages. When executing this algorithm on the spanner $H$ instead, Lemma 9 yields the following result: