标题： 关于环形网络中编码分布式计算的最优性 显示英文标题

标题： On the Optimality of Coded Distributed Computing for Ring Networks

摘要： 我们考虑一个基于环形通信网络的编码分布式计算问题，其中 $N$个计算节点以环形拓扑排列，每个节点只能与距离常数 $d$以内的邻居进行通信。 为了缓解交换中间值时的通信瓶颈，我们提出了新的编码分布式计算方案，这些方案利用了环形拓扑和冗余计算（即每个映射函数由 $r$个节点计算）。 考虑了两种典型情况：全收集（所有节点需要从所有输入文件映射的所有中间值）和全对全（每个节点需要从其他节点获取一组不同的中间值）。 对于全收集情况，我们提出了一种基于连续逆向拼车的新编码方案，其中节点传输每个包含两个消息的编码数据包，这两个消息沿同一路径向相反方向传输。 理论反证证明，当 $N\gg d$时，我们的方案在通信负载、计算负载 $r$ 和广播距离 $d$之间达到了最优权衡。 对于全对全情况，我们没有简单地重复全收集方案，而是根据中间值与目标节点的接近程度来精确传递中间值，以减少不必要的传输。 我们推导了最优通信负载的信息论下限，并证明在 $N\gg r$时，我们的方案在循环放置下是渐近最优的。 最优性结果表明，在基于环的网络中，冗余计算$r$仅在减少通信负载方面带来加性增益，而广播距离$d$则带来乘性增益。 显示英文摘要

摘要： We consider a coded distributed computing problem in a ring-based communication network, where $N$ computing nodes are arranged in a ring topology and each node can only communicate with its neighbors within a constant distance $d$. To mitigate the communication bottleneck in exchanging intermediate values, we propose new coded distributed computing schemes for the ring-based network that exploit both ring topology and redundant computation (i.e., each map function is computed by $r$ nodes). Two typical cases are considered: all-gather where each node requires all intermediate values mapped from all input files, and all-to-all where each node requires a distinct set of intermediate values from other nodes. For the all-gather case, we propose a new coded scheme based on successive reverse carpooling where nodes transmit every encoded packet containing two messages traveling in opposite directions along the same path. Theoretical converse proof shows that our scheme achieves the optimal tradeoff between communication load, computation load $r$, and broadcast distance $d$ when $N\gg d$. For the all-to-all case, instead of simply repeating our all-gather scheme, we delicately deliver intermediate values based on their proximity to intended nodes to reduce unnecessary transmissions. We derive an information-theoretic lower bound on the optimal communication load and show that our scheme is asymptotically optimal under the cyclic placement when $N\gg r$. The optimality results indicate that in ring-based networks, the redundant computation $r$ only leads to an additive gain in reducing communication load while the broadcast distance $d$ contributes to a multiplicative gain.