Fundamental Limits of Distributed Linearly Separable Computation under Cyclic Assignment
Fundamental Limits of Distributed Linearly Separable Computation under Cyclic Assignment
复制标题
DOI：
10.1109/isit54713.2023.10206661
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Wenjiang Huang;Kai Wan;Hua Sun;Mingyue Ji;R. Qiu;G. Caire
中科院分区：
文献类型：
--
作者：
Wenjiang Huang;Kai Wan;Hua Sun;Mingyue Ji;R. Qiu;G. Caire
研究了循环分配下的分布式线性可分计算问题。这是一个广泛存在于协作分布式梯度编码、实时绘制、线性变换等领域的问题。在分布式计算系统中，主机要求N个分布式工作者从K个数据集中计算一个线性可分函数。任务函数可以表示为K个消息的Kc线性组合，其中每个消息是一个数据集的一个单独函数的输出。同时也考虑了掉队效应，使得从每个Nr个工作者的回答中，主人应该恢复任务。计算成本被定义为分配给每个工作者的数据集的数量，而通信成本被定义为应该接收的(编码的)消息的数量。目标是描述计算和通信成本之间的最佳折衷。文献中已经提出了各种分布式计算方案，但即使在循环分配下，该问题的(阶)最优性仍然是开放的。本文提出了一种新的基于干扰对齐的循环分配算法，该算法在循环分配条件下是接近最优的。
Distributed Linearly Separable Computation problem under the cyclic assignment is studied in this paper. It is a problem widely existing in cooperated distributed gradient coding, real-time rendering, linear transformers, etc. In a distributed computing system, a master asks N distributed workers to compute a linearly separable function from K datasets. The task function can be expressed as Kc linear combinations of K messages, where each message is the output of one individual function of one dataset. Straggler effect is also considered, such that from the answers of each Nr worker, the master should recover the task. The computation cost is defined as the number of datasets assigned to each worker, while the communication cost is defined as the number of (coded) messages which should be received. The objective is to characterize the optimal tradeoff between the computation and communication costs. Various distributed computing scheme were proposed in the literature with a well-known cyclic data assignment, but the (order) optimality of this problem remains open, even under the cyclic assignment. This paper proposes a new computing scheme with the cyclic assignment based on interference alignment, which is near optimal under the cyclic assignment.