Sharper Asymptotically Optimal CDC Schemes via Combinatorial Designs

MaRDI QIDQ6443088zbMATH OpenFDO

Authors Yingjie Cheng, Gaojun Luo, Xiwang Cao, Martianus Frederic Ezerman, San Ling

Publication date 9 July 2023

Abstract: 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.

This page was built for publication: Sharper Asymptotically Optimal CDC Schemes via Combinatorial Designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443088)