Capacity limits for distributed linear computation depend on subspace cross-ratio

Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio

Information Theory

Summary

This paper studies how much information multiple users need to send so a server can compute a certain combined value without error. It focuses on a small, basic case where users observe some linear relationships of common data, and the server wants another linear combination. The authors show that the minimum communication needed depends on a geometric property called the cross-ratio of four lines, not just on basic dimensions of the data. They also find different communication limits depending on the prime number underlying the data field and the specific linear combination the server wants.

What this means in practice

  • For data storage engineers: Optimize exact repair protocols for storage nodes in distributed MDS codes based on subspace configurations to minimize communication costs.
  • For network coding developers: Design more efficient linear coding schemes for distributed function computation by considering subspace geometry beyond dimension counting.

A theory result. No direct application yet.

Authors

Hua Sun

Abstract

$K$ users each observe a fixed linear function of common data over a finite field of characteristic $p$, and a server must recover another fixed linear function with zero error from one message sent by each user. The capacity, the minimum total number of symbols the users send per computed instance, depends only on the configuration of subspaces formed by these linear functions. We study the instance in which three users observe $\boldsymbol{a}$, $\boldsymbol{b}$ and $\boldsymbol{a}+\boldsymbol{b}$ and the server wants $\boldsymbol{a}+λ\boldsymbol{b}$. The four functions span four lines in a plane with cross-ratio $λ$, the smallest instance of the four subspace problem of representation theory. It is the smallest configuration whose capacity is not determined by the dimensions of the subspaces formed by sums and intersections: these dimensions are the same for every $λ$, but the capacity depends on the cross-ratio and on the prime subfield. For the harmonic cross-ratios, $λ=-1$, $λ=2$ or $2λ=1$, it is $2$: every zero-error code reveals $(\boldsymbol{a},\boldsymbol{b})$ to the server, so no code beats having two users send their observations. For $λ$ outside the prime subfield it is the cut-set bound $3/2$, achieved by codes linear over the prime subfield, while codes linear over the field need $2$. For the other $λ$ in the prime subfield it lies in $[3p/(2p-1),2]$, so no code at any block length approaches the cut-set bound. The qualitative separation persists under vanishing error for uniform data: the cut-set bound is tight exactly for $λ$ outside the prime subfield. The four-line instance is also exact repair of one node of a $[4,2]$ MDS storage code, and the results translate to that setting.