

























Coded distributed computing (CDC) was introduced to greatly reduce the communication load for MapReduce computing systems. Such a system has $K$ nodes, $N$ input files, and $Q$ Reduce functions. Each input file is mapped by $r$ nodes and each Reduce function is computed by $s$ nodes. The architecture must allow for coding techniques that achieve the maximum multicast gain. Some CDC schemes that achieve optimal communication load have been proposed before. The parameters $N$ and $Q$ in those schemes, however, grow too fast with respect to $K$ to be of great practical value. To improve the situation, researchers have come up with some asymptotically optimal cascaded CDC schemes with $s+r=K$ from symmetric designs. In this paper, we propose new asymptotically optimal cascaded CDC schemes. Akin to known schemes, ours have $r+s=K$ and make use of symmetric designs as construction tools. Unlike previous schemes, ours have much smaller communication loads, given the same set of parameters $K$, $r$, $N$, and $Q$. We also expand the construction tools to include almost difference sets. Using them, we have managed to construct a new asymptotically optimal cascaded CDC scheme.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。