Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners

We introduce the local information cost (LIC), which quantifies the amount of information that nodes in a network need to learn when solving a graph problem. We show that the local information cost presents a natural lower bound on the communication complexity of distributed algorithms. For the synchronous CONGEST KT 1 model, where each node has initial knowledge of its neighbors' IDs, we prove that Ω LIC ( ) log log bits are required for solving a graph problem with a -round algorithm that errs with probability at most . Our result is the first lower bound that yields a general trade-off between communication and time for graph problems in the CONGEST KT 1 model.

We demonstrate how to apply the local information cost by deriving a lower bound on the communication complexity of computing a spanner with multiplicative stretch 2 -1 that consists of at most ( 1+ 1 + ) edges, where = 1/ 2 . More concretely, we show that any (poly( ) )-time spanner algorithm must send at least Ω 1 2 1+1/2 bits. Previously, only a trivial lower bound of Ω ( ) bits was known for this problem.

A consequence of our lower bound is that achieving both time-and communication-optimality is impossible when designing a distributed spanner algorithm. In light of the work of King, Kutten, and Thorup (2015), this shows that computing a minimum spanning tree can be done significantly faster than finding a spanner when considering algorithms with ˜ ( ) communication complexity. Our results also imply time complexity lower bounds for these problems in the node-capacitated clique of Augustine, Ghaffari, Gmyr, Hinnenthal, Scheideler, Kuhn, and Li (2019), and in the push-pull gossip model with limited bandwidth, as studied by Haeupler, Mohapatra, and Su (2018).

• A short version of this paper appeared in the proceedings of the 32th ACM-SIAM Symposium on Discrete Algorithms (SODA'21).