The Local Information Cost of Distributed Graph Spanners

We introduce the \emph{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 KT1 model, where each node has initial knowledge of its neighbors' IDs, we prove that $Ω(\frac{\text{LIC}_γ(P)}{\logτ\log n})$ bits are required for solving a graph problem $P$ 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 KT1 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 $2t-1$ that consists of at most $O(n^{1+\frac{1}{t} + ε})$ edges, where $ε= O( {1}/{t^2} )$. More concretely, we show that any $O(\text{poly}(n))$-time spanner algorithm must send at least $\tildeΩ(\tfrac{1}{t^2} n^{1+{1}/{2t}})$ bits. Previously, only a trivial lower bound of $\tilde Ω(n)$ bits was known for this problem. (See PDF for the full abstract.)