Optimal Bandwidth for All-Linear-Reduce Operation

Due to the increasing size of datasets and complexity of models, distributed machine learning is becoming increasingly important. Among the various components of distributed machine learning frameworks, the all-reduce operation holds significant importance, particularly in terms of communication costs among computing nodes. The all-reduce operation distributes to all nodes one or more reductions of data symbols from all nodes. This operation is used in distributed machine learning for aggregating data from computing nodes during the training and synchronizing the results among all computing nodes. This paper considers a distributed system consisting of computing nodes which are connected with each other via one-hop links. The data symbols are encoded and stored in the computing nodes. This paper focuses on the so-called all-linear-reduce operation which distributes to all nodes one or more linear combinations of data symbols from all nodes. This paper aims to determine the optimal bandwidth for the linear all-reduce operation, for an arbitrarily given distributed system. We propose a universal all-linear-reduce operation, which has been proven to achieve the optimal bandwidth in some cases.