论文标题
基于放置递送阵列的级联编码的分布式计算方案
Cascaded Coded Distributed Computing Schemes Based on Placement Delivery Arrays
论文作者
论文摘要
li {\ it et al}。引入了编码分布式计算（CDC）方案，以减少一般分布式计算框架（例如MapReduce）中的通信负载。他们还提出了级联的CDC方案，其中每个输出函数被多次计算，并证明了此类方案在计算负载和通信负载之间实现了基本的权衡。但是，当计算节点数量较大时，这些方案需要大量的输入文件和输出功能。在本文中，通过使用放置递送阵列（PDA）的结构，我们构建了几类无限类的CDC方案。我们还表明，所有新方案中的输出函数数量仅是计算节点数量的一个因素，而我们的新方案中的输入文件数量远小于由Li {\ it等人}得出的CDC方案中的输入文件的数量。
Li {\it et al}. introduced coded distributed computing (CDC) scheme to reduce the communication load in general distributed computing frameworks such as MapReduce. They also proposed cascaded CDC schemes where each output function is computed multiple times, and proved that such schemes achieved the fundamental trade-off between computation load and communication load. However, these schemes require exponentially large numbers of input files and output functions when the number of computing nodes gets large. In this paper, by using the structure of placement delivery arrays (PDAs), we construct several infinite classes of cascaded CDC schemes. We also show that the numbers of output functions in all the new schemes are only a factor of the number of computing nodes, and the number of input files in our new schemes is much smaller than that of input files in CDC schemes derived by Li {\it et al}.
