The Local Information Cost of Distributed Graph Spanners
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2020
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914646271721472 |
|---|---|
| author | Robinson, Peter |
| author_facet | Robinson, Peter |
| contents | 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.) |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2003_09895 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The Local Information Cost of Distributed Graph Spanners Robinson, Peter Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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.) |
| title | The Local Information Cost of Distributed Graph Spanners |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2003.09895 |