We define all-to-all encode, a collective communication operation serving as a primitive in decentralized computation and storage systems. Consider a scenario where every processor initially has a data packet and requires a linear combination of all data packets; the linear combinations are distinct from one processor to another, and are specified by a generator matrix of an error correcting code. We use a linear network model, in which processors transmit linear combinations of their data and previously received packets, and adopt a standard synchronous system setting to analyze its communication cost. We provide a universal algorithm which computes any matrix in this model by only varying intermediate coefficients, and prove its optimality. When the generator matrix is of the Vandermonde or Lagrange type, we further optimize the communication efficiency of the proposed algorithm.

翻译：我们定义了全方位编码,即集体通信操作,在分散化计算和储存系统中作为原始的计算和储存系统。考虑一种假设情景,即每个处理器最初有一个数据包,需要所有数据包的线性组合;线性组合从一个处理器到另一个处理器,由错误校正代码的生成器矩阵指定。我们使用线性网络模型,处理器在其中传输其数据和先前收到的包的线性组合,并采用标准同步系统设置来分析其通信成本。我们提供了一种通用算法,仅用不同的中间系数计算该模型中的任何矩阵,并证明其最佳性。当生成器矩阵是范德蒙德或拉格兰德型时,我们进一步优化了拟议算法的通信效率。