TU3.R8.2

Multi-access Distributed Computing Models using Map-Reduce Arrays

Shanuja Sasi, Onur Günlü, Linköping University, Sweden; Sundar Rajan, Indian Institute of Science, India

Session:
Distributed Computing

Track:
13: Coded or distributed computation

Location:
Omega

Presentation Time:
Tue, 9 Jul, 14:45 - 15:05

Session Chair:
Petros Elia, Eurecom
Abstract
A novel distributed computing model called \textit{Multi-access Distributed Computing (MADC)} was recently introduced in [B. Federico and P. Elia, ``Multi-Access Distributed Computing,'' June 2022, [online] Available: http://www.arXiv:2206.12851]. The MADC models with Combinatorial Topology (CT) was studied, where there are $\Lambda$ mapper nodes and $K = {\Lambda \choose \alpha}$ reducer nodes with each reducer node connected to distinct $\alpha$ mapper nodes. In this paper, we represent MADC models via 2-layered bipartite graphs called Map-Reduce Graphs (MRGs), and a set of arrays called Map-Reduce Arrays (MRAs) inspired from the Placement Delivery Arrays (PDAs) used in the coded caching literature. The connection between MRAs and MRGs is established, thereby providing coded shuffling schemes for the MADC models using the structure of MRAs. Moreover, a set of $g-$regular MRAs is provided which corresponds to the existing scheme for MADC models with CT. One of the major limitations of the existing scheme for CT is that it requires an exponentially large number of reducer nodes for large $\Lambda$. This can be overcome by representing CT by MRAs, where coding schemes can be derived even if some of the reducer nodes are not present.
Resources