2020/03/22 by Peter M. Robinson, Robinson, Peter
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2003.09895
openalex publication_date 2020/03/22 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
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 KT1 model, where each node has initial knowledge of its neighbors' IDs, we prove that Ω((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(n1+(1)/(t) + ε) edges, where ε= O( 1/t2 ). More concretely, we show that any O(poly(n))-time spanner algorithm must send at least Ω(\tfrac1t2 n^1+1/2t) bits. Previously, only a trivial lower bound of Ω(n) bits was known for this problem. (See PDF for the full abstract.)