论文标题
主修分布式计算系统的编码计算
Coded Computing for Master-Aided Distributed Computing Systems
论文作者
论文摘要
我们考虑在分布式计算模型中运行的MapReduce型任务，该任务由$ {k} $ edge Computing在网络边缘分布的节点和一个帮助Edge节点来计算输出功能的主节点。主节点和边缘节点都配备了一些存储记忆和计算功能，通过多播网络连接。我们定义了在传输过程中为顺序实现所花费的通信时间（所有节点顺序发送符号）和并行实现（主节点可以分别在Edge Nodes的传输过程中发送符号）。我们提出了一种混合编码的分布式计算方案，该方案将系统分为两个子系统，在该系统中，将编码的分布式计算（CDC）策略应用于Songze li \ emph {et al。}，并将其应用于第一个子系统，并将新颖的Master-Aed CDC策略应用于第二个子系统。我们证明该方案是最佳的，即，在顺序和并行实现中达到了最小通信时间，并在整体通信时间，计算负载和主节点的存储容量之间建立了{\ emph {optimal}}信息理论权衡。它表明，将主节点与存储和计算功能结合在一起可以进一步缩短通信时间。对于顺序实现，我们推断两个子系统之间的大约最佳文件分配，这表明主节点应映射尽可能多的文件，以达到较小的通信时间。对于并行实现，如果主节点的存储和计算功能足够大（不需要存储和映射所有文件），则建议的方案在没有主节点的帮助的情况下最多需要系统最小通信时间的1/2。
We consider a MapReduce-type task running in a distributed computing model which consists of ${K}$ edge computing nodes distributed across the edge of the network and a Master node that assists the edge nodes to compute output functions. The Master node and the edge nodes, both equipped with some storage memories and computing capabilities, are connected through a multicast network. We define the communication time spent during the transmission for the sequential implementation (all nodes send symbols sequentially) and parallel implementation (the Master node can send symbols during the edge nodes' transmission), respectively. We propose a mixed coded distributed computing scheme that divides the system into two subsystems where the coded distributed computing (CDC) strategy proposed by Songze Li \emph{et al.} is applied into the first subsystem and a novel master-aided CDC strategy is applied into the second subsystem. We prove that this scheme is optimal, i.e., achieves the minimum communication time for both the sequential and parallel implementation, and establish an {\emph{optimal}} information-theoretic tradeoff between the overall communication time, computation load, and the Master node's storage capacity. It demonstrates that incorporating a Master node with storage and computing capabilities can further reduce the communication time. For the sequential implementation, we deduce the approximately optimal file allocation between the two subsystems, which shows that the Master node should map as many files as possible in order to achieve smaller communication time. For the parallel implementation, if the Master node's storage and computing capabilities are sufficiently large (not necessary to store and map all files), then the proposed scheme requires at most 1/2 of the minimum communication time of system without the help of the Master node.
