Fundamental Limits of Multi-User Distributed Computing of Linearly Separable Functions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915732862795776 |
|---|---|
| author | Namboodiri, K. K. Krishnan Peter, Elizabath Malak, Derya Elia, Petros |
| author_facet | Namboodiri, K. K. Krishnan Peter, Elizabath Malak, Derya Elia, Petros |
| contents | This work establishes the fundamental limits of the classical problem of multi-user distributed computing of linearly separable functions. In particular, we consider a distributed computing setting involving $L$ users, each requesting a linearly separable function over $K$ basis subfunctions from a master node, who is assisted by $N$ distributed servers. At the core of this problem lies a fundamental tradeoff between communication and computation: each server can compute up to $M$ subfunctions, and each server can communicate linear combinations of their locally computed subfunctions outputs to at most $Δ$ users. The objective is to design a distributed computing scheme that reduces the communication cost (total amount of data from servers to users), and towards this, for any given $K$, $L$, $M$, and $Δ$, we propose a distributed computing scheme that jointly designs the task assignment and transmissions, and shows that the scheme achieves optimal performance in the real field under various conditions using a novel converse. We also characterize the performance of the scheme in the finite field using another converse based on counting arguments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_10603 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fundamental Limits of Multi-User Distributed Computing of Linearly Separable Functions Namboodiri, K. K. Krishnan Peter, Elizabath Malak, Derya Elia, Petros Information Theory This work establishes the fundamental limits of the classical problem of multi-user distributed computing of linearly separable functions. In particular, we consider a distributed computing setting involving $L$ users, each requesting a linearly separable function over $K$ basis subfunctions from a master node, who is assisted by $N$ distributed servers. At the core of this problem lies a fundamental tradeoff between communication and computation: each server can compute up to $M$ subfunctions, and each server can communicate linear combinations of their locally computed subfunctions outputs to at most $Δ$ users. The objective is to design a distributed computing scheme that reduces the communication cost (total amount of data from servers to users), and towards this, for any given $K$, $L$, $M$, and $Δ$, we propose a distributed computing scheme that jointly designs the task assignment and transmissions, and shows that the scheme achieves optimal performance in the real field under various conditions using a novel converse. We also characterize the performance of the scheme in the finite field using another converse based on counting arguments. |
| title | Fundamental Limits of Multi-User Distributed Computing of Linearly Separable Functions |
| topic | Information Theory |
| url | https://arxiv.org/abs/2601.10603 |