The Singular Optimality of Distributed Computation in LOCAL

It has been shown that one can design distributed algorithms that are (nearly) singularly optimal, meaning they simultaneously achieve optimal time and message complexity (within polylogarithmic factors), for several fundamental global problems such as broadcast, leader election, and spanning tree construction, under the KT0 assumption. With this assumption, nodes have initial knowledge only of themselves, not their neighbors. In this case the time and message lower bounds are Ω(D) and Ω(m), respectively, where D is the diameter of the network and m is the number of edges, and there exist (even) deterministic algorithms that simultaneously match these bounds. On the other hand, under the KT1 assumption, whereby each node has initial knowledge of itself and the identifiers of its neighbors, the situation is not clear. For the KT1 CONGEST model (where messages are of small size), King, Kutten, and Thorup (KKT) 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 with Õ(n) message complexity (n is the network size), which can be significantly smaller than m. Randomization is crucial in obtaining this result. While the message complexity of the KKT result is near-optimal, its time complexity is Õ(n) rounds, which is far from the standard lower bound of Ω(D). An important open question is whether one can achieve singular optimality for the above problems in the KT1 CONGEST model, i.e., whether there exists an algorithm running in Õ (D) rounds and Õ (n) messages. Another important and related question is whether the fundamental BFS tree construction can be solved with Õ(n) messages (regardless of the number of rounds as long as it is polynomial in n) in KT1. In this paper, we show that in the KT1 LOCAL model (where message sizes are not restricted), singular optimality is achievable. Our main result is that all global problems, including BFS tree construction, can be solved in Õ (D) rounds and Õ (n) messages, where both bounds are optimal up to polylogarithmic factors. Moreover, we show that this can be achieved deterministically.