Paperlane

no. 16 · Tuesday 17 November 2026

Linear Network Coding for Sum All-Reduce over Ring Networks

Yi Chen, Zhuoqi Tu and Shenghao Yang

math.IT

Abstract

Sum All-Reduce is a fundamental collective communication primitive in which each node holds a local vector and every node must recover the componentwise sum of all vectors. In distributed training, this operation is often implemented over a ring topology using a reduce–multicast scheme. We study sum All-Reduce on directed rings via linear network coding, which includes reduce–multicast as a special case. We give a necessary and sufficient feasibility condition in terms of the coding matrices. For a ring with $N\geq 3$ nodes and unit-capacity links, where each node holds a vector containing $K$ symbols, we prove that the number of time units $T$ required by any feasible linear code satisfies $T\ge\max\bigl\{K+N-2,\ \lceil\frac{2(N-1)}{N}K\rceil\bigr\}$, giving a rate $K/T$ of at most $N/(2(N-1))$. The bound is tight over every field. When $K\ge N$, an interleaved reduce–multicast code achieves the bound; when $K<N$ and $K$ divides $N$, a reduce–partial-multicast code does. When $K<N$ and $K$ does not divide $N$, no coordinate-wise code—in particular, no reduce–multicast code—achieves the bound, while an explicit linear network code does.

fields
Information Theory
pdf ↗ page arXiv:2611.21190 ↗