WorksComputer Science
Linear Network Coding for Sum All-Reduce over Ring Networks
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 nodes and unit-capacity links, where each node holds a vector containing symbols, we prove that the number of time units required by any feasible linear code satisfies , giving a rate of at most . The bound is tight over every field. When , an interleaved reduce–multicast code achieves the bound; when and divides , a reduce–partial-multicast code does. When and does not divide , no coordinate-wise code—in particular, no reduce–multicast code—achieves the bound, while an explicit linear network code does.