论文标题
在通用网络上的级联编码分布式计算的组合设计
A Combinatorial Design for Cascaded Coded Distributed Computing on General Networks
论文作者
论文摘要
已经开发了用于大大减少现代分布式计算系统中的通信负载的编码方法。特别是，Li等人引入的编码分布式计算（CDC）。可以有效地交易计算资源，以减少MAPREDUCE中的通信负载，例如计算系统。对于更通用的级联CDC，在r节点上重复进行MAP计算，以显着降低计算Q Q降低功能s时间的节点之间的通信负载。在本文中，我们为级联的CDC提出了一种新型的低复杂性组合设计，其中1）确定输入文件和输出功能分配，2）需要较少的输入文件和输出功能数量，而3）在各种网络上运行，在该网络中，节点具有不同的存储和计算能力。我们提供了计算通信权衡的分析表征，我们从中表明提出的方案可以胜过Li等人提出的最新计划。对于同质网络。此外，当网络是异质的时，我们表明提出的方案的性能可以比其同质对应物更好。此外，在固定输入文件和输出功能分配时，提出的方案在信息理论匡威绑定的恒定因素内是最佳的。
Coding theoretic approached have been developed to significantly reduce the communication load in modern distributed computing system. In particular, coded distributed computing (CDC) introduced by Li et al. can efficiently trade computation resources to reduce the communication load in MapReduce like computing systems. For the more general cascaded CDC, Map computations are repeated at r nodes to significantly reduce the communication load among nodes tasked with computing Q Reduce functions s times. In this paper, we propose a novel low-complexity combinatorial design for cascaded CDC which 1) determines both input file and output function assignments, 2) requires significantly less number of input files and output functions, and 3) operates on heterogeneous networks where nodes have varying storage and computing capabilities. We provide an analytical characterization of the computation-communication tradeoff, from which we show the proposed scheme can outperform the state-of-the-art scheme proposed by Li et al. for the homogeneous networks. Further, when the network is heterogeneous, we show that the performance of the proposed scheme can be better than its homogeneous counterpart. In addition, the proposed scheme is optimal within a constant factor of the information theoretic converse bound while fixing the input file and the output function assignments.
