Topologies for Multi-Access Distributed Computing Models

A novel distributed computing model called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Multi-access Distributed Computing (MADC)</i> was recently introduced in the literature. The MADC models with Combinatorial Topology (CT) were studied, where there are A mapper nodes and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> = (Λ α) reducer nodes with each reducer node connected to distinct α 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). The connection between MRAs and MRGs is established, thereby exploring new topologies and providing coded shuffling schemes for the MADC models with MRGs using the structure of MRAs. A novel <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Nearest Neighbor Connect-MRG (NNC-MRG)</i> is explored and a coding scheme is provided for MADC models with NNC-MRG. Moreover, CT is generalized to Generalized Combinatorial-MRG (GC-MRG). A set of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">g</i>–regular MRAs is provided which corresponds to the existing scheme for MADC models with CT and extended those to generate another set of MRAs to represent MADC models with GC-MRG. One of the major limitations of the existing scheme for CT is that it requires an exponentially large number of reducer nodes and input files for large Λ. 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. Another way of tackling this is by using a different MRG, specifically NNC-MRG, where the number of reducer nodes and files required are significantly smaller compared to CT.