论文标题
编码的分布式计算，具有数据和输出功能的预设分配
Coded Distributed Computing with Pre-set Assignments of Data and Output Functions
论文作者
论文摘要
编码的分布式计算可以通过引入冗余计算并创建多播机会来减少分布式计算系统的通信负载。但是，现有方案需要精致的数据放置和输出功能分配，当分布式节点获取数据而没有主节点的编排时，这是不可行的。在本文中，我们考虑了数据放置和输出功能分配是任意但预设的一般系统。我们提出了两个编码的计算方案，一声编码的传输（OSCT）和少量编码的传输（FSCT），以减少通信负载。这两个方案首先将节点组成簇，并将每个集群的传输分为多个回合，然后在每个回合中设计编码的传输，以最大程度地提高多播增益。 OSCT和FSCT之间的关键区别在于，前者使用一个单发传输，在该传输中，每个编码的消息可以由预期的节点独立解码，而后者允许每个节点共同解码多个接收到的符号以实现潜在的较大的多播收益。此外，根据Yu等人提出的下限，我们分别得出了足够的条件，以实现OSCT和FSCT的最佳性。这不仅可以恢复现有的最优结果，还包括某些情况，我们的计划是最佳的，而其他方案则不是最佳的。
Coded distributed computing can reduce the communication load for distributed computing systems by introducing redundant computation and creating multicasting opportunities. However, the existing schemes require delicate data placement and output function assignment, which is not feasible when distributed nodes fetch data without the orchestration of a master node. In this paper, we consider the general systems where the data placement and output function assignment are arbitrary but pre-set. We propose two coded computing schemes, One-shot Coded Transmission (OSCT) and Few-shot Coded Transmission (FSCT), to reduce the communication load. Both schemes first group the nodes into clusters and divide the transmission of each cluster into multiple rounds, and then design coded transmission in each round to maximize the multicast gain. The key difference between OSCT and FSCT is that the former uses a one-shot transmission where each encoded message can be decoded independently by the intended nodes, while the latter allows each node to jointly decode multiple received symbols to achieve potentially larger multicast gains. Furthermore, based on the lower bound proposed by Yu et al., we derive sufficient conditions for the optimality of OSCT and FSCT, respectively. This not only recovers the existing optimality results but also includes some cases where our schemes are optimal while others are not.
