Capacity limits found for distributed linear computations over fields
Capacity of Generic Symmetric Distributed Linear Computation: The Geometry of Relations
Information Theory
Summary
When several users each see parts of data and send messages to a server that wants to calculate something new from all the data, understanding how much communication is needed is tricky. The authors studied this problem when the data and calculations are all linear and defined over a large finite field. They found exact formulas for the minimal communication needed based on how the data and computations relate geometrically. This work tells us the best possible communication efficiency for these types of distributed calculations.
What this means in practice
- •For distributed system engineers: Design communication-efficient protocols for computing linear functions across multiple data sources with known capacity limits.
- •For network coding developers: Create coding schemes that minimize total message size in distributed linear computations by applying alignment and geometric insights.
A theory result. No direct application yet.
Authors
Hua Sun
Abstract
In distributed linear computation, $K$ users observe linear functions of common finite-field data and send separate messages to a server that wants another linear function. We characterize the generic capacity $C$, the minimum total number of field symbols sent per computed instance, when all observations and the demand have dimension $ν$, the data have dimension $μ$, and the coefficients of these linear functions are drawn independently and uniformly from the field and stay fixed during coding, with the field size growing through arbitrary prime powers. For fixed $K$, $C/ν$ depends only on $τ=μ/ν$: the curve has finitely many linear pieces for at most three users, infinitely many pieces approaching one value of $τ$ for four users, and a rational part between two sequences of linear pieces for five or more users. The geometry of the relation space, formed by the linear relations among the observations and the demand, determines three things: the shape of the curve, which relations the coding scheme aligns, and the entropy inequalities used in the converse. Generically, the user subspaces of this space are either balanced, where the capacity lies on a single rational curve, or split into two balanced components, a sparse and a dense one, which produces the linear pieces. Achievability uses asymptotic set alignment, in which monomial precoders confine the combined observation differences to a small set. The converse uses the same geometry to lower-bound the sum of the users' remaining observation entropies in terms of the remaining data entropy.