Graph-Theoretic Limits of Distributed Computation: Entropy, Eigenvalues, and Chromatic Numbers
We address the problem of the distributed computation of arbitrary functions of two correlated sources, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>X</mi><mn>1</mn></msub...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-07-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/27/7/757 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | We address the problem of the distributed computation of arbitrary functions of two correlated sources, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>X</mi><mn>1</mn></msub></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>X</mi><mn>2</mn></msub></semantics></math></inline-formula>, residing in two distributed source nodes, respectively. We exploit the structure of a computation task by coding source characteristic graphs (and multiple instances using the <i>n</i>-fold OR product of this graph with itself). For regular graphs and general graphs, we establish bounds on the optimal rate—characterized by the chromatic entropy for the <i>n</i>-fold graph products—that allows a receiver for asymptotically lossless computation of arbitrary functions over finite fields. For the special class of cycle graphs (i.e., 2-regular graphs), we establish an exact characterization of chromatic numbers and derive bounds on the required rates. Next, focusing on the more general class of <i>d</i>-regular graphs, we establish connections between <i>d</i>-regular graphs and expansion rates for <i>n</i>-fold graph products using graph spectra. Finally, for general graphs, we leverage the Gershgorin Circle Theorem (GCT) to provide a characterization of the spectra, which allows us to derive new bounds on the optimal rate. Our codes leverage the spectra of the computation and provide a graph expansion-based characterization to succinctly capture the computation structure, providing new insights into the problem of distributed computation of arbitrary functions. |
|---|---|
| ISSN: | 1099-4300 |