---
abstract: 'A multi-cell mobile edge computing network is studied, in which each user wishes to compute the product of a user-generated data matrix with a network-stored matrix through data uploading, distributed edge computing, and output downloading. Assuming randomly straggling edge servers, this paper investigates the interplay among upload, compute, and download times in high signal-to-noise ratio regimes. A policy based on cascaded coded computing and on coordinated and cooperative interference management in uplink and downlink is proposed and proved to be approximately optimal for sufficiently large upload times. By investing more time in uplink transmission, the policy creates data redundancy at the edge nodes to reduce both computation times by coded computing, and download times via transmitter cooperation. Moreover, it allows computing times to be traded for download times.'
author:
- '[^1]'
bibliography:
- 'refer.bib'
title: 'Multi-Cell Mobile Edge Coded Computing: Trading Communication and Computing for Distributed Matrix Multiplication'
---

=2.1pt =2.1pt

[1.0]{}

Introduction
============

Mobile edge computing (MEC) is an emerging network architecture that enables cloud-computing capabilities at the edge nodes (ENs) of mobile networks[@MEC]. MEC makes it possible to offer mobile users applications, such as recommendation or gaming services, that require significant storage and computing resources, by task offloading. A key problem, which is the subject of this paper, is to understand the interplay and performance trade-offs between communication (in both uplink and downlink) and computing during the offloading process in multi-cell MEC networks (see Fig. \[sysModel\]).

To this end, this study focuses on the baseline problem of computing the product between user-generated data vectors $\mathbf{u}$’s and a network-stored matrix $\mathbf{A}$. Examples of applications include recommendation systems based on collaborative filtering, in which the user-generated data $\mathbf{u}$ corresponds to user profile vectors, while the network-side matrix $\mathbf{A}$ collects the profile vectors of a certain class of items, e.g., movies. Note that matrix $\mathbf{A}$ may be very large in practice, preventing a simple solution whereby users download and store the matrix for local computation. Matrix multiplication, as many other more complex computations[@bekkerman2011scaling], can be decomposed into subtasks and distributed across multiple servers. In MEC networks, the servers are embedded in distinct ENs, and hence distributed computation at the edge requires input data uploading via the uplink, computation at the ENs, and output result downloading via the downlink.

In the process discussed above, the overall latency is the sum of three components, namely, the times needed for uploading, for computing at the ENs, and for downloading. This paper is devoted to studying the interplay and trade-offs among these three components from an information-theoretic standpoint. The key idea is that investing more time in any one of the three steps may be instrumental in reducing the time needed for subsequent steps thanks to coded computing [@fundamental_tradeoff; @Speeding_Up; @songzestraggler; @jingjing; @stagglerexploit; @8006960; @improvedJingjing] and cooperative transmission [@7857805; @sengupta2017fog; @FanXu; @TaoCache]. As explained next, both coded computing and cooperative transmissions leverage forms of spatial redundancy.

![A multi-cell MEC network carrying out distributed matrix multiplication via uplink communication, edge computing, and downlink communications.](MEC_straggler5.eps){width="4.4in" height="2.4in"}

\[sysModel\]

Coded computing was introduced in [@Speeding_Up] for a master-slave system with ideal communication links and linear computations. It aims at reducing the average latency caused by distributed servers with random computing times, i.e., the problem of so-called *straggling servers*[@dean2013tail], through linear coding of the rows of matrix $\mathbf{A}$. Linear coding assigns each server a flexible number of encoded rows of matrix $\mathbf{A}$. Thanks to coding, specifically to Maximum Distance Separable (MDS) codes, assigning more coded rows at the servers reduces the number of servers that need to complete their computations in order to recover the desired outputs.

A simple way to ensure spatial redundancy is to assign repeatedly the same rows of matrix $\mathbf{A}$ across multiple ENs. While this does not provide the same robustness against stragglers as MDS coding, it allows ENs to compute common outputs, i.e., computation replication. This in turn makes it possible for the ENs to cooperate for transmission to the users in the downlink, which can reduce the download latency in an interference-limited system such as that in Fig. \[sysModel\]. This idea has been explored by [@8007057; @jingjing; @KKLMEC] for task offloading in multi-cell MEC systems and by [@li2019wireless] for data shuffling in wireless MapReduce systems. Note that the same idea has also been explored in the context of multi-cell caching systems for content delivery in [@7857805; @sengupta2017fog; @FanXu; @TaoCache].

In fact, in the MEC system of Fig. \[sysModel\], investing more time for uplink communication allows the same user-generated input vectors to be received by more ENs, which enhances spatial redundancy. The spatial redundancy generally introduces a heavier computation load, which in turn can increase the robustness against straggling servers via coded computing and reduce download latency by enhancing transmission cooperation opportunities at the ENs.

Based on these observations, this paper tackles the question: *Given an upload latency, what is the optimal trade-off between computing and download latencies?* We focus on the high signal-to-noise ratio (SNR) regime in order to highlight the role of interference management as enabled by spatial redundancy. The main prior works in this regard are [@jingjing] and [@KKLMEC]. The work [@jingjing] proposed a computing and downloading strategy by making the simplified assumption that the upload time is unconstrained so that the input vectors from all users are available at all ENs. The work [@KKLMEC], on the other hand, characterized the trade-off between upload and download latencies by assuming that the computing time at each EN is deterministic (in contrast to random) so that coded computing is not needed. Moreover, [@KKLMEC] adopts a general task model, rather than matrix multiplication as studied in this work.

In contrast to [@jingjing] and [@KKLMEC], in this paper, we parameterize the trade-off region between computing and download latencies in terms of the upload latency. We propose a joint task assignment, input upload, compute, and output download policy that generalizes that of [@jingjing] and [@KKLMEC], which is based on a cascade of MDS and repetition codes[@improvedJingjing], by accounting also for the more sophisticated coordination strategies proposed in [@FanXu]. Furthermore, we provide a converse result, which demonstrates that the achievable upload time is optimal, and the compute time and download time are within constant multiplicative gaps to their respective lower bounds.

Paper organization: Sec. \[problemformu\] presents the problem formulation and definitions. Main results are presented in Sec. \[mainresults\]. The proposed achievable schemes are summarized in Sec. \[AchievableScheme\].

Notations: $[a\!:\!b]$ denotes the set $\{a\!+\!1,a\!+\!2,\dots,b\}$, $[K]$ denotes the set $[1\!:\!K]$, and $(x)^+$ denotes $\max\{x,0\}$.

Problem Formulation {#problemformu}
===================

MEC Network Model
-----------------

As shown in Fig. \[sysModel\], we consider a multi-cell MEC network consisting of $K$ single-antenna ENs communicating with $M$ single-antenna users via a shared wireless channel. Denote by $\mathcal{K}\!=\!\{1,2,\ldots,K\}$ the set of ENs and by $\mathcal{M}\!=\!\{1,2,\ldots,M\}$ the set of users. Each EN is equipped with an edge server. Let $h^u_{ki}$ denote the uplink channel fading from user $i\!\in\!\mathcal{M}$ to EN $k\!\in\!\mathcal{K}$, and $h^d_{ik}$ denote the downlink channel fading from EN $k\!\in\! \mathcal{K}$ to user $i\!\in\!\mathcal{M}$, both of which are independent and identically distributed (i.i.d.) for all pairs $(i,k)$ according to some continuous distribution. All users and ENs can acquire the full channel state information about uplink channel $\mathbf{H}^u\!\triangleq\!\{h^u_{ki}\!:k\!\in\!\mathcal{K},i\!\in\!\mathcal{M}\}$ and downlink channel $\mathbf{H}^d\!\triangleq\!\{h^d_{ik}\!:i\!\in\!\mathcal{M},k\!\in\!\mathcal{K}\}$.

We consider the matrix-vector product computation task $\mathbf{v}\!=\!\mathbf{A}\mathbf{u}$, where $\mathbf{u}\!\in\!\mathbb{F}^{n\times1}_{2^B}$ is the user-generated input vector, $\mathbf{v}\!\in\!\mathbb{F}^{m\times 1}_{2^B}$ is the output vector, $\mathbf{A}\! \in\!\mathbb{F}^{m\times n}_{2^B}$ is a data matrix available at the network end, and $B$ is the size (in bits) of each element. Each user $i$ has $N$ input vectors $\mathbf{u}_{i,j}$, $j\!\in\![N]$, and wishes to compute the $N$ output vectors $$\label{output}
\mathbf{v}_{i,j}\!=\! \mathbf{A}{\mathbf{u}_{i,j}},~\text{for}~j\!\in\![N].$$ The matrix $\mathbf{A}$ is partially stored across the ENs, which conduct the product operations in a distributed manner. To this end, each EN $k$ has a storage capacity of $\mu m nB$ bits, and it can hence store a fraction $\mu\!\in\![\frac{1}{K},1]$ of the rows of matrix $\mathbf{A}$. Specifically, during an offline storage phase, an encoding matrix $\mathbf{E}_k\!\in\!\mathbb{F}^{\mu m\times m}_{2^B}$ is used to generate a coded matrix $\mathbf{A}_k\!=\!\mathbf{E}_k\mathbf{A}$, which is then stored at EN $k$, as in [@songzestraggler; @improvedJingjing].

Task Offloading Procedure
-------------------------

The task offloading procedure proceeds via task assignment, input uploading, edge computing, and output downloading.

### Task Assignment

A task assignment scheme is defined through sets $\{\mathcal{U}_{i,\mathcal{K}^{'}}\!:i\!\in\!\mathcal{M},\mathcal{K}^{'}\!\subseteq\! \mathcal{K}\}$, where $\mathcal{U}_{i,\mathcal{K}^{'}}\!\subseteq\!\{\mathbf{u}_{i,j}\}^N_{j=1}$ denotes the subset of input vectors from user $i$ that are assigned only to the subset of ENs $\mathcal{K}^{'}$ for computation. Since each input vector must be computed, we have the condition $\bigcup_{\mathcal{K}^{'}\!\subseteq \mathcal{K}} \mathcal{U}_{i,\mathcal{K}^{'}}\!=\!\{\mathbf{u}_{i,j}\}^N_{j=1}$ for $i\!\in\!\mathcal{M}$. Furthermore, by definition, we have the relation $\mathcal{U}_{i,\mathcal{K}^{'}}\!\bigcap \mathcal{U}_{i,\mathcal{K}^{''}}\!=\!\varnothing$ for $\mathcal{K}^{'}\!\neq\!\mathcal{K}^{''}$. The subset of input vectors from all users assigned to each EN $k$ is denoted as $\mathcal{U}_k\!=\!\bigcup_{{i}\in\mathcal{M},\,\mathcal{K}^{'}\!\subseteq \mathcal{K}:\,k\in\mathcal{K}^{'}} \mathcal{U}_{i,\mathcal{K}^{'}}$.

\[defenition1\] (Repetition Order) For a given task assignment scheme $\{\mathcal{U}_{i,\mathcal{K}^{'}}\}_{i\in\mathcal{M},\mathcal{K}^{'}\subseteq\mathcal{K}}$, the repetition order $r$, with $1\!\le\!r \!\le \!K$, is defined as average input data redundancy, i.e., the total number of input vectors assigned to the $K$ ENs (counting repetitions) divided by the total number of input vectors of the $M$ users, i.e., $r\!\triangleq\!\frac{\sum_{k\in\mathcal{K}}|\mathcal{U}_{k}|}{MN}$.

### Input Uploading

At run time, each user $i$ maps its input vectors $\{\mathbf{u}_{i,j}\}^N_{j=1}$ into a codeword $\mathbf{X}^u_i\!\triangleq\!\left(X^u_i(t)\right)^{T^{u}}_{t=1}$ of length $T^u$ symbols under the power constraint $(T^{u})^{-1}\mathbb{E}\big[||\mathbf{X}^u_i||^2\big]\!\le\! P^u$. Note that $X^u_i(t)\!\in\! \mathbb{C}$ is the symbol transmitted at time $t\!\in\![T^{u}]$. At each EN $k\!\in\!\mathcal{K}$, the received signal $Y^u_k(t) \!\in\! \mathbb{C}$ at time $t\!\in\![T^{u}]$ can be expressed as $Y^u_k(t)\!=\!\sum_{i \in \mathcal{M}}h^u_{ki}(t)X^u_i(t)\!+\!Z^u_{k}(t)$, where $Z^u_{k}(t)\!\sim\!\mathcal{CN}(0,1)$ denotes the noise at EN $k$. Each EN $k$ decodes the sequence $\left(Y^u_k(t)\right)^{T^u}_{t=1}$ into an estimate $\{\widehat{\mathbf{u}}_{i,j}\}$ of the assigned input vectors $\{\mathbf{u}_{i,j}\!:\mathbf{u}_{i,j}\!\in\!\mathcal{U}_k\}$.

### Edge Computing

After the uploading phase is completed, each EN $k$ computes the products of the assigned estimated input vectors in set $\mathcal{U}_{k}$ with its stored coded model $\mathbf{A}_k$. The computing time for EN $k$ to complete the computation of the corresponding $\mu m |\mathcal{U}_{k}|$ row-vector products is modeled as $$\label{computingtime}
T^c_k = \mu m |\mathcal{U}_{k}| \omega_k, ~\text{for}~k\in\mathcal{K}.$$ In (\[computingtime\]), random variable $\omega_k$ represents the time needed by EN $k$ to compute a row-vector product, and is modelled as an exponential distribution with mean $1/\eta$ (see, e.g., [@Speeding_Up; @songzestraggler; @8006960]). The MEC network waits until the fastest $q$ ENs, denoted as subset $\mathcal{K}_q\!\subseteq\!\mathcal{K}$, have finished their tasks before returning the results back to users in the downlink. The cardinality $|\mathcal{K}_q|\!=\!q$ is referred to as *the recovery order*. The rest of $K\!-\!q$ ENs are known as *stragglers*. The resulting (random) duration of the edge computing phase is hence given by $T^c=\max_{k\in\mathcal{K}_q} T^c_k$.

### Output Downloading

At the end of the edge computing phase, each EN $k\!\in\!\mathcal{K}_q$ obtains the coded outputs $\mathcal{V}_k\!\triangleq\!\left\{\mathbf{v}_{i,j,k}\!=\!\mathbf{A}_k\widehat{\mathbf{u}}_{i,j}\!:\mathbf{u}_{i,j}\!\in\!\mathcal{U}_{k}\right\}$. Every EN $k$ in $\mathcal{K}_q$ then maps $\mathcal{V}_k$ into a length-$T^d$ codeword $\mathbf{X}^{d}_k\!\triangleq\!\left(X^{d}_{k}(t)\right)^{T^{d}}_{t=1}$ with an average power constraint $(T^{d})^{-1}\mathbb{E}\big[||\mathbf{X}^d_k||^2\big]\!\le\! P^d$. For each user $i\!\in\!\mathcal{M}$, its received signal $Y^{d}_i(t) \!\in\! \mathbb{C}$ at time $t\!\in\![T^{d}]$ is given by $Y^{d}_i(t)\!=\!\sum_{k \in \mathcal{K}_q}h^d_{ik}(t)X^{d}_{k}(t)\!+\!Z^{d}_{i}(t)$, where $Z^{d}_{i}(t)\!\sim\!\mathcal{CN}(0,1)$ is the noise at user $i$. Each user $i$ decodes the sequence $(Y^{d}_i(t))^{T^d}_{t=1}$ to obtain an estimate $\{\widehat{\mathbf{v}}_{i,j,k}\}_{j\in[N],k\in\mathcal{K}_q}$ of the coded outputs, from which it obtains an estimate $\{\widehat{\mathbf{v}}_{i,j}\}_{j\in[N]}$ of its desired outputs. This is possible if the estimated coded outputs $\{\widehat{\mathbf{v}}_{i,j,k}\}_{j\in[N],k\in\mathcal{K}_q}$ contain enough information to guarantee the condition $H(\{\mathbf{v}_{i,j}\}_{j\in[N]}|\{\widehat{\mathbf{v}}_{i,j,k}\}_{j\in[N],k\in\mathcal{K}_q})\!=\!0$. The overall error probability is given as $\mathrm{P}_e\!\triangleq\!\mathbb{P}\big(\bigcup^{M~~N}_{i=1,j=1} \left\{\widehat{\mathbf{v}}_{i,j}\!\neq\!\mathbf{v}_{i,j}\right\}\!\big)$. A task offloading policy is said to be feasible when the error probability $\mathrm{P}_e\!\to\!0$ as $B\!\to\!\infty$.

Performance Metric
------------------

The performance of the considered MEC network is characterized by the latency triplet due to task uploading, computing, and downloading, which we measure in the high-SNR regime by following [@sengupta2017fog].

\[defenition2\] The normalized uploading time (NULT), normalized computing time (NCT), and normalized downloading time (NDLT) achieved by a feasible policy with repetition order $r$ and recovery order $q$ are defined, respectively, as

$$\begin{aligned}
\tau^{u}(r) &\triangleq \lim_{P_u\to\infty} \lim_{B\to\infty} \frac{\mathbb{E}_{\mathbf{H}^u}[T^u]}{ NnB/\log P^u}, \label{NULTtau}\\
\tau^c (r,q) &\triangleq \lim_{m\to\infty}\frac{\mathbb{E}\left[T^c\right]}{ Nm/\eta},\label{NCTtau}\\
\tau^{d}(r,q) &\triangleq \lim_{P_d\to\infty}\lim_{m\to\infty}\lim_{B\to\infty} \frac{\mathbb{E}_{\mathbf{H}^d}[T^d]}{NmB/\log P^d}. \label{NDLTtau}\end{aligned}$$

The definitions (\[NULTtau\]) and (\[NDLTtau\]) have been also adopted in [@KKLMEC], by normalizing the delivery times to those of reference interference-free systems (with high-SNR rates $\log P^u$ and $\log P^d$, respectively). Similarly, the computing time in definition (\[NCTtau\]) is normalized by the average time needed to compute over all the input vectors of a user. To avoid rounding complications, in definition (\[NCTtau\]) and (\[NDLTtau\]), we let the output dimension $m$ grow to infinity.

For a given NULT $\tau^u$, the compute-download latency region is defined as the union of the set for all NCT-NDLT pairs $(\tau^c, \tau^d)$, i.e., $$\begin{aligned}
\label{region}
\!\!\!\mathscr{T}^{*}(\tau^u)\!\triangleq\!\big\{\!(\tau^c, \tau^{d})\!: (\tau^u(r),\tau^c(r,q),\tau^{d}(r,q))~&\text{is achievable for}~\text{some $(r,q)$ and}\,\,\tau^u\!\le\!\tau^u(r),\nonumber\\
\!&~~~~~~~~~~~~~~\tau^{c}\!\ge\!\tau^{c}(r,q),~\text{and}~\tau^{d}\!\ge\!\tau^{d}(r,q)\big\}\!.\!\!\end{aligned}$$

\[remarkconvex\] (Convexity of compute-download latency region.) For an input data assignment policy $\{\mathcal{U}_{i,\mathcal{K}^{'}}\}_{i\in\mathcal{M},\mathcal{K}^{'}\subseteq\mathcal{K}}$ with a repetition order $r$, fix an input uploading strategy achieving NULT $\tau^u$. Consider two policies $\pi_1$ and $\pi_2$ that differ may in their computation and download pahses, and achieve NCT-NDLT pairs $\left(\tau^c_{1}, \tau^d_{1}\right)$ and $\left(\tau^c_{2}, \tau^d_{2}\right)$, respectively. For any ratio $\lambda\!\in\![0,1]$, there exists a policy that achieves the NCT-NDLT pair $\lambda\left(\tau^c_{1}, \tau^d_{1}\right) \!+\!(1\!-\!\lambda)\left(\tau^c_{2}, \tau^d_{2}\right)$ for the same NULT $\tau^u$. To this end, assuming $m$ is sufficiently large, matrix $\mathbf{A}$, correspondingly, all output vectors (\[output\]) are split horizontally so that $N\lambda m$ and $N(1\!-\!\lambda)m$ outputs are processed by using policies $\pi_1$ and $\pi_2$, respectively. By the linearity of the NCT (\[NCTtau\]) and NDLT (\[NDLTtau\]) with respect to the output size, the claimed pair of NCT and NDLT is achieved. This implies the region (\[region\]) is convex.

The region $\mathscr{T}^{*}(\tau^u)$ captures the trade-offs between computation and download communication latencies for a fixed upload communication latency. The region in (\[region\]) is convex thanks to time- and memory-sharing arguments in a manner similar to[@sengupta2017fog Lemma 1] (the same is not true for the region of achievable triplets $(\tau^u, \tau^c, \tau^d)$).

![(Bottom) Hybrid MDS-Repetition coding for matrix $\mathbf{A}$; (Top) Input uploading and edge computing.](MDS_Repetition.eps){width="3.8in" height="2.3in"}

\[mds\_repetition\]

Main Results {#mainresults}
============

In this section, we first present the inner and outer bounds on the compute-download latency region, and then discuss some consequences of the main results in terms of the tradeoffs among upload, compute, and download latencies. Then, we specialize the main results to a number of simple set-ups to illustrate the connections with existing works.

Key Ideas {#keyidea}
---------

We start by outlining the main ideas that underpin the proposed policy. For a repetition-recovery order pair $(r,q)$, as shown in Fig. \[mds\_repetition\], during task assignment, matrix $\mathbf{A}$ is encoded by a cascade of an MDS code of rate $1/\rho_1$ and a repetition code of rate $1/\rho_2$. As in [@Speeding_Up; @songzestraggler; @jingjing], MDS codes can alleviate the impact of stragglers on the computation latency by decreasing the admissible values for the number $q$ of non-straggling ENs. Repetition coding can instead reduce the download latency by enabling cooperative transmission among multiple ENs computing the same outputs[@jingjing; @KKLMEC], as discussed below.

In the input upload phase, each user divides its $N$ input vectors into $\binom{K}{r}$ subsets $\{\mathcal{U}_{i,\mathcal{K}^{'}}\}$, with each subset uploaded to a distinct subset $\mathcal{K}^{'}$ of $r$ ENs. Thus, as shown in Fig. \[mds\_repetition\], in the computing phase, each input vector of any user is computed by a subset of $p_1$ non-straggling ENs with $p_1$ being at least $r\!-(\!K\!-q)$ and at most $\min\{r,q\}$. Therefore, since each encoded row of $\mathbf{A}$ is replicated at a subset of $\rho_2$ ENs, after computation, each MDS-encoded row-vector product result for a user will be replicated at a subset of $p_2$ non-straggling ENs, with $p_2$ being at least $\max\{\rho_2\!-\! K\!+\!p_1,1\}$ and at most $\min\{p_1,\rho_2\}$.

In the output download phase, as proposed in [@FanXu], each subset of $p_2$ ENs computing the same coded outputs can first use zero-forcing (ZF) precoding to null the interfering signal caused by common outputs at a subset of $p_2-\!1$ undesired users. When the number of undesired users does not exceed $p_2-\!1$, i.e., when $M\!-\!1\!\le\!p_2-\!1$, by ZF precoding, each user only receives its desired outputs with all undesired outputs being cancelled out. When this condition is violated, i.e., when $M\!>\!p_2$, after ZF precoding, each output still causes interferences to $M\!-\!p_2$ undesired users. As detailed in [@FanXu], interference alignment can be applied in cascade to the ZF precoders in order to mitigate the impact of these interfering signals.

Bounds
------

The scheme summarized above and detailed in Sec. \[AchievableScheme\] achieves the following region.

\[achievableresults\] (Inner bound). For the described MEC network with $M$ users and $K$ ENs, each with storage capacity $\mu\!\in\![\frac{1}{K},1]$, the following communication-computation latency triplet $\big(\tau^{u}_a(r),$ $\tau^c_a(r,q),\tau^{d}_a(r,q)\big)$ is achievable

$$\begin{aligned}
\!\tau^{u}_a(r)&\!=\! \frac{(M\!-\!1)r \!+\! K}{K}, \label{achieveUpoad} \\
\!\tau^c_a(r,q)&\!=\!\frac{Mr\mu(H_k\!-\!H_{K-q})}{K}\!, \label{achievecompute}\\
\!\tau^d_a(r,q)&\!=\!\sum\limits^{\min\{r,q\}}_{p_1\!=r-\!K\!+q}\!\!\!\!\!B_{p_1}\!\!\left(\sum\limits^{l_{max}}_{p_2=l_{p_1}}\!\!\frac{B_{p_2}}{d^d_{p_1,M,p_2}}\!+\!
\!\frac{B_{l_{p_1}\!-1}}{d^d_{p_1,M,l_{p_1}\!-1}}\!\right)\!, \label{achievedownload}\end{aligned}$$

for any repetition order $r$ and recovery order $q$ in the set

$$\label{regionR}
\mathcal{R}\!\triangleq\!\big\{(r,q)\!:r\!\in\![K],q\!\in\![K],~\text{and}~ (r\!-\!K\!+\!q)\mu\!\ge\!1\big\},$$

where

$H_K\!=\!\sum^K_{k=1}\frac{1}{k}$, $B_{p_1}\!=\!\binom{q}{p_1}\binom{K-q}{r-p_1}\frac{1}{\binom{K}{r}}$, $B_{p_2}\!=\!\binom{p_1}{p_2}\binom{K-p_1}{\rho_2-p_2}\frac{\rho_1}{\binom{K}{\rho_2}}$, $B_{l_{p_1}\!-1}\!=\!1\!-\!\!\sum^{l_{max}}_{p_2=l_{p_1}}\!\!B_{p_2}$

;

$$\label{dofdd}
d^d_{p_1,M,p_2}=\left\{
\begin{aligned}
&1, &p_2\!\ge\!M~~~~\\
&\frac{\binom{p_1}{M-1}(M\!-\!1)}{\binom{p_1}{M-1}(M\!-\!1)+1},   &~~p_2\!=\!M\!-\!1\\
&\max\left\{d', \frac{p_2}{M}\right\},          &~~p_2\!\le\!M\!-\!2
\end{aligned}
~,\right.$$

with $d'\!\triangleq\!\max_{1\le t\le p_2}\frac{p_1-t+1}{M+p_1-2t+1}$;

$$\begin{aligned}
 \label{theoremcoderate}
\!\!\rho_2\!=\!\inf\!\bigg\{\rho\!:\!\!\binom{K}{\rho}\!-\!\binom{2K\!-\!r\!-\!q}{\rho}\!\ge\! \frac{1}{\rho_1}\binom{K}{\rho},\rho_1\rho\!=\!K\mu,\rho_1\!\in\!\big\{1,K\mu/(K\mu\!-\!1),K\mu/(K\mu\!-\!2)\cdots,K\mu\big\}\!\bigg\};\!\!\end{aligned}$$

and

$$\begin{aligned}
\label{replicationmin}
\!\!\!l_{p_1} \!\!=\! \inf\!\bigg\{l\!:\!\!\sum\nolimits^{l_{max}}_{p_2=l}\!\!B_{p_2}m\!\le\!m, l\!\in\![l_{min}\!:\!l_{max}], l_{max}\!=\!\min\{p_1,\rho_2\}, l_{min}\!=\!\max\{\rho_2\!-\! K\!+\!p_1,1\} \bigg\}.\!\end{aligned}$$

For an NULT $\tau^u\!=\!\tau^u_a(r)$ given in (\[achieveUpoad\]) for some $r$, an inner bound $\mathscr{T}_{in}(\tau^{u})$ on the compute-download latency region is given as the convex hull of the set $\big\{\!\left(\tau^c_a(r,q),\tau^d_a(r,q)\right)\!:\!q\!\in\!\big[\lceil\!\frac{1}{\mu}\!\rceil\!+\!K\!-\!r\!:\!K\big]\!\big\}$.

We also have the following converse.

\[lower\_bound\] (Converse). For the same MEC network, the set of all admissible pairs $(r,q)$ is included in the set $\mathcal{R}$ in (\[regionR\]). Furthermore, any feasible communication-computation latency triplet $\left(\tau^{u}(r),\tau^{c}(r,q),\tau^{d}(r,q)\right)$ for pairs $(r,q)$ in $\mathcal{R}$ is lower bounded as

$$\begin{aligned}
\!\tau^{u}(r)&\!\ge\! \tau^u_a(r),\!\label{lowerupload}\\
\!\tau^{c}(r,q)&\!\ge\!\tau^{c^*}\!(r,q)\!=\!\max\limits_{t\in[q-1]}\!\!\frac{(H_K\!-\! H_{K-q+t})(r\!-\!K\!+\!t)^{+}M\mu }{t}\!,\!\label{lowercompute} \\
\!\tau^{d}(r,q)&\!\ge\!\tau^{d^*}\!(r,q)\!=\!\max_{t\in\{1,\cdots,\min\{q,M\}\}}\!\!\!\frac{M\!-\!(M\!-\!t)(q\!-\!t)\frac{r}{K}\mu}{t}\!.\! \label{lowerdownload}\end{aligned}$$

For an NULT $\tau^u\!=\!\tau^u_a(r)$ in (\[achieveUpoad\]) for some $r$, an outer bound $\mathscr{T}_{out}(\tau^{u})$ of the compute-download latency region is given as the convex hull of set $\big\{\!\!\left(\tau^{c^*}\!\!(r,q),\tau^{d^*}\!\!(r,q)\right)\!\!:\!q\!\in\!\!\big[\lceil\!\frac{1}{\mu}\!\rceil\!+\!K\!-r\!:\!\!K\big]\!\big\}$.

*Proof:* By considering all possible task assignments and the effect of random stragglers, bound (\[lowerupload\]) is derived via genie-aided arguments; (\[lowercompute\]) is derived by some basic inequalities; The proof of (\[lowerdownload\]) follows and generalizes steps in [@sengupta2017fog Eq. (63)-(65)]. The detailed proof is available in the Appendix. Fig. \[latencytriples\] plots the derived inner and outer bounds on the compute-download latency region $\mathscr{T}^{*}(\tau^{u})$ for $M\!\!=\!\!K\!\!=\!\!10$ and for two different values of $\tau^u$. First, we observe that, *as $q$ increases, the NDLT is reduced at the expense of an increasing NCT*: A larger $q$ enables more opportunities for transmission cooperation at the ENs during output downloading, while increasing, on average, the time required for $q$ ENs to complete their tasks. Furthermore, comparing Fig. \[bR\] with Fig. \[sR\], we also see that *allowing for a longer upload time increases the compute-download latency region*. This is because more information is uploaded to ENs over a larger latency $\tau^u$. Thus, on the one hand, users can wait for fewer ENs to finish their computing tasks, reducing the NCT; and, on the other hand, the increased duplication of outputs also increases opportunities for transmission cooperation to reduce the NDLT.

Optimality
----------

\[gapLemma\] (Optimality). For a given $r\!\in\![1,K]$, it is not possible to reduce the achievable NULT $\tau^u_a(r)$ in (\[achieveUpoad\]) while still guaranteeing the feasibility of a triplet $\left(\tau^{u}_a(r),\tau^{c},\tau^{d}\right)$. Furthermore, for a sufficiently large NULT $\tau^u\!\ge\!\tau^u_a(K\!-\!n_1)$ and small recovery order $q\!\le\!K(1\!-\!1/n_2)\!+\!1$, with integers $0\!\le\!n_1\!\!<\!q/2$ and $n_2\!\ge\!1$, the multiplicative gap between the achievable NCT in (\[achievecompute\]) and its lower bound $\tau^{c^*}$ in (\[lowercompute\]) satisfies the inequality $\tau^{c}/\tau^{c^*}\!\le\!(1\!+\!n_1) (1\!+\!n_2)$. Finally, for a sufficiently large NULT $\tau^u\!\ge\!\tau^u_a(K\!-\!n)$, with integer $n\!\ge\! 0$, the multiplicative gap between the achievable NDLT in (\[achievedownload\]) and its lower bound $\tau^{d^*}$ in (\[lowerdownload\]) satisfies the inequality $\tau^d/\tau^{d^*}\!\le\!2(1\!+\!n\mu)$, and hence, if $r\!=\!K$, we have $\tau^d/\tau^{d^*}\!\le\!2$.

The multiplicative gaps in Fig. \[latencytriples\] are consistent with Lemma \[gapLemma\], since $\tau^c/\tau^{c^*}\!=\!3.61\!<\!22$ at $(r,q)\!=\!(9,10)$ (i.e., $n_1\!=\!1$ and $n_2\!=\!10$) and $\tau^d/\tau^{d^*}\!=\!1.32\!<\!3.2$ at $(r,q)\!=\!(9,3)$ (i.e., $n\!=\!1$).

Special Cases
-------------

In the special case when $r\!=\!K$, hence ignoring limitations on the uplink transmission, the achievable NDLT (\[achievedownload\]) reduces to the normalized communication delay in [@jingjing Eq. (13)], when using only ZF precoding in downlink. Furthermore, when setting $q\!=\!K$, hence ignoring stragglers[’]{} effects, and $\mu\!=\!1$, i.e., ignoring ENs[’]{} storage constraint, the achievable NDLT (\[achievedownload\]) reduces to $\tau^d\!=\!M/\min\{K,M\}$, which recovers the communication load in [@8007057 Remark 5], and the NDT with cache-aided EN cooperation in [@sengupta2017fog Eq. (25)].

Details on The Proposed Policy {#AchievableScheme}
==============================

Consider $\mu\!\in\!\!\{1/K,2/K,\cdots\!,1\}$[^2], a repetition order $r\!\in\![K]$, and a recovery order $q\!\in\![K]$ in the feasible set $\mathcal{R}$ in (\[regionR\]). Note that each input vector is replicated on at least $r\!-\!(K\!-\!q)$ non-stragglers, so set $\mathcal{R}$ ensures that any subset of $r\!-\!K\!+\!q$ ENs can store at least $m$ coded rows of $\mathbf{A}$ to multiply each input.

### Task Assignment {#achieveuploadscheme}

Following the discussion in Sec. \[keyidea\], each EN $k$ is assigned $M\binom{K\!-\!1}{r-\!1}N/\binom{K}{r}\!=\!MNr/K$ inputs corresponding to subsets $\{\mathcal{U}_{i,\mathcal{K}^{'}}\!: i\!\in\!\mathcal{M}, \mathcal{K}^{'}\!\subseteq\!\mathcal{K}, |\mathcal{K}^{'}|\!=\!r, k\!\in\!\mathcal{K}^{'}\}$.

### Input Uploading {#uploadtime}

For uplink transmissions, each user needs to communicate with all $\binom{K}{r}$ subsets of ENs of cardinality $r$. Therefore, the uplink channel is an X-multicast channel with $M$ transmitters, $K$ receivers, and size-$r$ multicast group. As proved in [@DOfNiesen Theorem 2], its optimal per-receiver DoF is given by $d^{u}_{r}\!=\!Mr\!/(Mr\!+\!K\!\!-\!r)$. The per-receiver rate of this channel in the high SNR regime can be approximated as $d^{u}_{r}\!\times\!\log\!P_u\!+\!o(\log\!P_u)$, so the uploading time can be approximately expressed as $T^u\!=\!\frac{MNr}{K}nB/(d^{u}_{r}\log\!P_u\!+o(\log\!P_u))$. Let $P_u\!\to\!\infty$ and $B\!\to\!\infty$, by Definition \[defenition2\], the NULT at repetition order $r$ is obtained as in (\[achieveUpoad\]).

### Edge Computing

Following Sec. \[keyidea\], the cascaded MDS-repetition code rate pair satisfies $\rho_1\!\!\in\!\!\left\{1,K\mu/(K\mu\!-\!1),K\mu/(K\mu\!-\!2),\cdots,K\mu\right\}$ and $\rho_2\!\!=\!\!K\mu/\rho_1$ under the constraint of the total storage size $k\mu$. Then, we split the coded matrix $\mathbf{A}_c$ into $\binom{K}{\rho_2}$ submatrices $\{\mathbf{A}_{c,\mathcal{K}^{''}}\!\}$, each stored at a distinct subset $\mathcal{K}^{''}\!$ of $\rho_2$ ENs. Then, as shown in Fig. \[mds\_repetition\], any subset of $r\!-\!K\!+\!q$ non-straggling ENs must store at least $m$ encoded rows to compute all outputs, which is ensured by condition $\rho_1m\!-\!\binom{K\!-(r\!-\!K\!+q)}{\!\rho_2\!}\rho_1m/\binom{\!K\!}{\!\rho_2\!}\!\ge\!m$ given in (\[theoremcoderate\]). Further, in order to create more spatial redundancy, the parameter $\rho_2$ is maximize as in (\[theoremcoderate\]) under the recovery condition. As an example, in Fig. \[downlinkchannel\], for $K\!\!=\!\!M\!\!=\!\!5$, $m\!=\!40$, $\mu\!\!=\!\!3/5$, $q\!\!=\!\!3$, and $r\!\!=\!\!4$, by (\[theoremcoderate\]), we have $(\rho_1,\rho_2)\!=\!(3/2,2)$ such that $\mathbf{A}$ is encoded into $60$ rows and then split into $\binom{5}{2}\!\!=\!\!10$ submatrices, each with $6$ rows replicated at $2$ ENs. By the given task input assignment $\{\mathcal{U}_{i,\mathcal{K}^{'}}\}$, each EN $k$ computes $MNr\mu m/K$ row-vector products. Thus, by Definition \[defenition2\] and [@arnold2008first Eq. (4.6.6)], the NCT is given by $\tau^c(r,q)\!=\lim\limits_{m\to\infty}\!\frac{\mathbb{E}\left[\left\{\frac{MNr\mu m}{K}\omega_k\right\}_{q:K}\right]}{Nm/\eta}
\!=\!\frac{Mr\mu\mathbb{E}\left[\{\omega_k\}_{q:K}\right]\!\eta}{K}
\!=\!\frac{Mr\mu(H_k\!-\!H_{K-q})}{K}$.

![Illustration of downlink transmission for $K\!=\!M\!=\!5$, $\mu\!=\!3/5$, $m\!=\!40$, $N\!=\!5$, $q\!=\!3$, $r\!=\!4$, and $(\rho_1,\rho_2)\!=\!(3/2,2)$. The MISO broadcast channel and X-channel are formed to transmit outputs of $\{\mathbf{u}_{i,1}\}^5_{i=1}$ back to the users. This figure only shows the pattern of MISO broadcast channels for transmitting $\{\mathbf{a}_{25}\mathbf{u}_{i,1},\cdots,\mathbf{a}_{30}\mathbf{u}_{i,1}\}^5_{i=1}$. Outputs of $\{\mathbf{u}_{i,2}\}^5_{i=1},\{\mathbf{u}_{i,3}\}^5_{i=1},\cdots,\{\mathbf{u}_{i,5}\}^5_{i=1}$ are transmitted in a similar way.](downlinkchannel.eps){width="4.1in" height="2.5in"}

\[downlinkchannel\]

### Output Downloading

Following Sec. \[keyidea\], for each user, the number of input vectors computed by $p_1$ non-straggling ENs equals $\binom{K\!-q}{r-p_1}N/\binom{K}{r}\!=\!\big(B_{p_1}/\binom{q}{p_1}\big)N$. Furthermore, the number of encoded rows of $\mathbf{A}$ replicated at $p_2$ non-straggling ENs is $\binom{K-p_1}{\rho_2-p_2}\rho_1m/\binom{K}{\rho_2}\!=\!\big(B_{p_2}/\binom{p_1}{p_2}\big)m$. Thus, as discussed in Sec. \[keyidea\], when $p_2\!\ge\!M$, each subset of $p_2$ ENs computing the same $M\big(B_{p_1}/\binom{q}{p_1}\big)N\big(B_{p_2}/\binom{p_1}{p_2}\big)m$ outputs can cooperatively transmit these outputs to $M$ users via ZF precoding. In contrast, when $p_2\!<\!M$, each subset of $p_2$ ENs partitions each common output into $\binom{M-1}{p_2-1}$ submessages, and first use ZF precoding to null the interference caused by each submessage at a distinct subset of $p_2\!-\!1$ undesired users. Then, by cascading ZF precoding with asymptotic interference alignment, the rest of the interfering signals from each subset of $t-\!1$ ENs can be aligned into a distinct subspace at each user. For example, for $p_2\!=\!M\!-\!1$, each submessage only causes interference to one user, so all interfering signals at each user can be aligned into one common subspace. The resulting downlink is a cooperative-X channel with $p_1$ transmitters, $M$ receivers, and size-$p_2$ cooperation group. By [@FanXu Lemma 1], an achievable per-receiver DoF of this channel is given as (\[dofdd\]). Similar to the calculation of NULT in Sec. \[uploadtime\], by Definition \[defenition2\], the NDLT for each user to download the outputs replicated at $p_2$ non-stragglers is given by $$\tau^d_{p_1,p_2}\!=\!\frac{B_{p_1}B_{p_2}/\binom{q}{p_1}}{d^d_{p_1,M,p_2}}. \label{p_1,p_2}$$

Due to the MDS coding, the total number of coded outputs available on the $p_1$ ENs may exceed the number $m$ needed to recover the outputs of each input vector. Denote by $l_{p_1-1}$, $\max\{\rho_2\!-\!K\!+\!p_1,1\}\!\le\!l_{p_1-1}\!\le\!\min\{p_1,\rho_2\}$, the minimum degrees of replication of needed coded outputs on the $p_1$ ENs, it is determined by (\[replicationmin\]), so the number of needed coded outputs replicated at $l_{p_1}\!\!-\!1$ ENs equals $M(B_{p_1}/\binom{q}{p_1})NB_{l_{p_1}\!-1}m$, where $B_{l_{p_1}-1}\!=\!1\!-\!\!\sum^{l_{max}}_{p_2=l_{p_1}}\!\!B_{p_2}$. Note that $B_{l_{p_1}\!-\!1}m/\binom{p_1}{l_{p_1}\!-1}$ can be seen as an integer for infinitely large $m$ since $\big(\!B_{l_{p_1}\!-1}m\!\!\!\mod{\!\binom{p_1}{l_{p_1}\!-1}}\big)/m\!\le\!\binom{p_1}{l_{p_1}\!-1}/m\!\to\! 0$ as $m\!\to\!\infty$. Hence, any exclusive subset of $l_{p_1}\!-\!1$ ENs can cooperatively transmit $\big(B_{p_1}/\binom{q}{p_1}\big)N\big(B_{l_{p_1}\!-1}/\binom{p_1}{l_{p_1}\!-1}\big)m$ common outputs to each of $M$ users, so the downlink channel is also a cooperative-X channel with $p_1$ transmitters, $M$ receivers, and cooperation group size $l_{p_1}\!-\!1$. Similar to (\[p\_1,p\_2\]), the NDLT for each user to download the outputs replicated at $l_{p_1}\!\!-\!1$ non-stragglers is given by $$\tau^d_{p_1,l_{p_1}-1}\!=\!\frac{B_{p_1}B_{l_{p_1}-1}/\binom{q}{p_1}}{d^d_{p_1,M,l_{p_1}-1}}.$$ Therefore, by considering all the inputs computed by $p_1$ ENs, with $p_1$ from $r\!-\!(K\!-\!q)$ to $\min\{r,q\}$, and all the outputs replicated at $p_2$ ENs, with $p_2$ from $l_{p_1-1}$ to $\min\{p_1,\rho_2\}$, and by summing all download times, the NDLT is obtained in (\[achievedownload\]).

For example, in Fig. \[downlinkchannel\], for inputs $\{\mathbf{u}_{i,1}\}^5_{i=1}$ computed by $p_1\!\!=\!\!2$ ENs, there are $30$ outputs $\{\mathbf{a}_{25}\mathbf{u}_{i,1},\ldots,\mathbf{a}_{30}\mathbf{u}_{i,1}\}^5_{i=1}$ replicated at $p_2\!=\!2$ ENs. These $30$ outputs can be cooperatively transmitted back to the users via ZF precoding, resulting in a 2-transmitter 5-receiver MISO broadcast channel that is a special case of cooperative-X channels under full transmitter cooperation. As a result, an NDLT of $3/40$ is achieved. After this round of transmission, users still need $34\!\times\!5\!=\!170$ outputs inside the blue dashed rectangle in Fig. \[downlinkchannel\], which can be transmitted by the 2 ENs via interference alignment. The downlink is a 2-transmitter 5-receiver X channel that is a special case of cooperative-X channels with size-$1$ cooperation group, yielding the NDLT of $51/100$. Thus, the NDLT for outputs of $\{\mathbf{u}_{i,1}\}^5_{i=1}$ is $3/40\!+\!51/100\!=\!117/200$. Then, the input vectors $\{\mathbf{u}_{i,2}\}^5_{i=1},\{\mathbf{u}_{i,3}\}^5_{i=1}$ are also computed by $p_1\!\!=\!\!2$ ENs, their outputs can be transmitted in a similar way, which achieves an NDLT of $(117/200)\!\times\!2\!=\!117/100$. Likewise, for the inputs $\{\mathbf{u}_{i,4}\}^5_{i=1},\{\mathbf{u}_{i,5}\}^5_{i=1}$ computed by $p_1\!\!=\!\!3$ ENs, the 3-transmitter 5-receiver cooperative X-channel with size-$2$ cooperation group, and 3-transmitter 5-receiver X-channel are formed to transmit the total $400$ outputs, yielding an NDLT of $(21/100\!+\!77/300)\!\times\! 2\!=\!14/15$. Thus, in this example, the total NDLT at $(r,q)\!=\!(4,3)$ is $14/15\!+\!(117/200)\!\times\!3\!=\!1613/600$.

### Inner Bound of Compute-Download Latency Region

For an NULT $\tau^u\!=\!\tau^u_a(r)$ given in (\[achieveUpoad\]) for some $r\!\in\!\mathcal{R}$, where $\mathcal{R}$ is given by (\[regionR\]), the feasible values of recovery order $q$’s should satisfy $\lceil\frac{1}{\mu}\rceil\!+\!K\!-r\!\le\!q\!\le\!K$. The non-integer $q$ can be rewritten as $q\!=\!\lambda\lceil q\rceil\!+\! (1\!-\!\lambda)\lfloor q\rfloor$ for some $\lambda\!\in\![0,1]$. Based on Remark \[remarkconvex\], we can combine our proposed policies at $(r,\lceil q\rceil)$ and $(r,\lfloor q\rfloor)$ via time- and memory-sharing methods to achieve the NCT-NDLT pair $\left(\tau^{c}_a(r,q),\tau^{d}_a(r,q)\right)\! = \!\lambda \left(\tau^{c}_a(r,\lceil q\rceil),\tau^{d}_a(r,\lceil q\rceil)\right) \!+ (1\!-\!\lambda)\!\left(\tau^{c}_a(r,\lfloor q\rfloor),\tau^{d}_a(r,\lfloor q\rfloor)\right)$. In fact, for any two integer-valued $q_1$ and $q_2$, any convex combination of achievable pairs $(\tau^{c}_a(r,q_1),\tau^{d}_a(r,q_1)$ and $(\tau^{c}_a(r,q_2),\tau^{d}_a(r,q_2))$ can also be achieved. So an inner bound $\mathscr{T}_{in}(\tau^{u})$ of the compute-download latency region is given as the convex hull of set $\big\{\!\left(\tau^{c}_a(r),\tau^d_a(r,q)\right)\!:\!q\!\in\!\big[\lceil\frac{1}{\mu}\rceil\!+\!K\!-\!r\!:\! K\big]\big\}$.

Appendix: Converse Proofs {#appendix-converse-proofs .unnumbered}
=========================

In this appendix, we prove the lower bounds in Theorem \[lower\_bound\] and the multiplicative gaps in Lemma \[gapLemma\]. For a repetition-recovery order pair $(r,q)$, as discussed, each input will be replicated on at least $r\!-\!(K\!-\!q)$ non-stragglers. The condition $(r-\!K\!+q)\mu\!\ge\!1$ must be satisfied such that any subset of $r\!-\!K\!+\!q$ non-stragglers are able to provide sufficient information to compute the outputs of all users. This proves that no pair $(r,q)$ is feasible outside the feasible set $\mathcal{R}$ in (\[regionR\]). Consider an arbitrary user input assignment policy $\big\{\mathcal{U}_{i,\mathcal{K}^{'}}\!: i\!\in\!\mathcal{M},\mathcal{K}^{'}\!\subseteq\!\mathcal{K}, |\mathcal{K}^{'}|\!=\!r\big\}$. The input vectors from user $i$ assigned to EN $k$ are denoted as set $\mathcal{I}_{i,k}\!\triangleq\!\big\{\mathcal{U}_{i, \mathcal{K}^{'}}\!\big\}_{\mathcal{K}^{'}\subset\mathcal{K}:k\in\mathcal{K}^{'}}$ for $i\!\in\!\mathcal{M}$ and $k\!\in\!\mathcal{K}$, and the size of $\mathcal{I}_{i,k}$ is denoted as $\gamma_{i,k}NnB$ bits, where the ratio $\gamma_{i,k}$ satisfies $$\begin{aligned}
&\sum\limits_{k\in\mathcal{K}}\gamma_{i,k} = r ,~ i \in\mathcal{M} \label{cons111}\\
&~0\le \gamma_{i,k} \le 1,~i \in\mathcal{M},~\text{and}~k\in\mathcal{K}. \label{cons222}\end{aligned}$$ In the rest of this appendix, we first derive the lower bounds on the NULT, NCT, and NDLT for a particular task assignment policy $\big\{\mathcal{U}_{i,\mathcal{K}^{'}}\!\big\}$ with repetition-recovery order $(r,q)\!\in\!\mathcal{R}$. Then, we minimize these lower bounds over all feasible task assignment policies to obtain the minimum NULT $\tau^{u^*}$, NCT $\tau^{c^*}$, and NDLT $\tau^{d^*}$. Then, for a fixed lower bound of NULT at $r\!\in\!\big[\lceil\frac{1}{\mu}\rceil,K\big]$, by convexity of the compute-download latency region, an outer bound of this region is given as described in Theorem \[lower\_bound\].

Lower Bound and Optimality of NULT
----------------------------------

For a particular task assignment policy $\big\{\mathcal{U}_{i,\mathcal{K}^{'}}\!\big\}$, we use genie-aided arguments to derive a lower bound on the NULT. Specifically, for any EN $k$ and user $i_o$, consider the following three disjoint subsets of task input vectors (or messages): $$\begin{aligned}
\mathcal{W}_{r} &= \{\mathcal{U}_{i, \mathcal{K}^{'} }: i\in\mathcal{M}, k\in\mathcal{K}^{'}\},\\
\mathcal{W}_{t} &= \{\mathcal{U}_{i, \mathcal{K}^{'} }:i=i_o,k\notin \mathcal{K}^{'} \},\\
\overline{\mathcal{W}} &= \{\mathcal{U}_{i,\mathcal{K}^{'}}: i\ne i_o~\text{and}~k\notin \mathcal{K}^{'}\}.\end{aligned}$$ The set $\mathcal{W}_{r}$ indicates the input messages from all users assigned to EN $k$ or all input messages that EN $k$ needs to decode, which satisfies $|\mathcal{W}_{r}|\!=\!\sum_{i\in\mathcal{M}}\gamma_{i,k}NnB$. The set $\mathcal{W}_{t}$ indicates the input messages from user $i_o$ assigned to all ENs in $\mathcal{K}$ excluding EN $k$, which satisfies $|\mathcal{W}_{t}|\!=\!(1\!-\!\gamma_{i_o,k})NnB$. The last set $\overline{\mathcal{W}}$ indicates all input messages from users in $\mathcal{M}$ excluding user $i$ assigned to ENs in $\mathcal{K}$ excluding EN $k$.

Let a genie provide the messages $\overline{\mathcal{W}}$ to all ENs, and additionally provide messages $\mathcal{W}_{r}$ to ENs in $\mathcal{M}/\{k\}$. The received signal of EN $j$ can be represented as $$\begin{aligned}
\mathbf{y}_j &= \sum\limits^{M}_{i=1,i\ne i_o}\mathbf{H}^u_{ji}\mathbf{X}_{i} + \mathbf{H}^u_{ji_o}\mathbf{X}_{i_o}+\mathbf{Z}^u_j,
$$ where the diagonal matrices $\mathbf{H}^u_{ji}$, $\mathbf{X}_{i}$, and $\mathbf{Z}^u_j$ denotes the channel coefficients from user $i$ to EN $j$, the signal transmitted by user $i$, and the noise received at EN $j$, respectively, over the block length $T^u$. The ENs in $\mathcal{M}/\{k\}$ have messages $\overline{\mathcal{W}}\!\cup\!\mathcal{W}_{r}$, which include the input messages that EN $k$ should decode and input messages transmitted by all users excluding user $i_o$. By this genie-aided information, each EN $j\!\in\!\mathcal{M}/\{k\}$ can construct the transmitted symbols $\{\mathbf{X}_i\!:i\!\ne\!i_o\}$ and subtract them from the received signal. So we can rewrite the signal received at EN $j\!\ne\!k$ as $$\label{equation1122}
\bar{\mathbf{y}}_j = \mathbf{y}_j - \sum\limits_{i\in\mathcal{M}/\{i_o\}}\mathbf{H}^u_{ji}\mathbf{X}_{i} = \mathbf{H}^u_{ji_o}\mathbf{X}_{i_o} + \mathbf{Z}^u_j.$$ Each EN $j\!\in\!\mathcal{M}/\{k\}$ needs to decode the input messages in subset of $\mathcal{W}_{t}$ assigned to it, denoted as $\mathcal{W}^j_{t}$. By Fano[’]{}s inequality and (\[equation1122\]), we have $$\label{fano1}
H(\mathcal{W}^j_{t}|\mathbf{y}_j,\overline{\mathcal{W}},\mathcal{W}_{r}) \le T^u \epsilon, ~~j\in\mathcal{M}/\{i\}.$$ Since EN $k$ can decode the input messages $\mathcal{W}_{r}$ assigned to it, by Fano[’]{}s inequality, we also obtain $$\label{Fano11}
H(\mathcal{W}_{r}|\hat{\mathbf{y}}_k,\overline{\mathcal{W}}) \le  T^u\epsilon .$$ Then, EN $k$ can construct the transmitted symbols $\{\mathbf{X}_i\!:i\!\ne\!i_o\}$ based on genie-aided messages $\overline{\mathcal{W}}$ and its decoded messages $\mathcal{W}_{r}$, and subtract them from its received signal, obtaining

$$\bar{\mathbf{y}}_k = \mathbf{y}_k - \sum\limits_{i\in\mathcal{M}/\{i_o\}}\mathbf{H}^u_{ki}\mathbf{X}_{i} = \mathbf{H}^u_{ki_o}\mathbf{X}_{i_o} + \mathbf{Z}^u_k.$$

Reducing the noise in the constructed signal $\bar{\mathbf{y}}_k$ and multiplying it by $\mathbf{H}^u_{ji_o}\left(\mathbf{H}^u_{ki_o}\right)^{-1}$, we obtain $$\bar{\mathbf{y}}^{j}_k  = \mathbf{H}^u_{ji_o}\left(\mathbf{H}^u_{ki_o}\right)^{-1} \bar{\mathbf{y}}_k =  \mathbf{H}^u_{ji_o}\mathbf{X}_{i_o} + \hat{\mathbf{Z}}^u_j,$$ where $\hat{\mathbf{Z}}^u_j$ is the reduced noise. By (\[equation1122\]), we see that $\bar{\mathbf{y}}^{j}_k $ is a degraded version of $\bar{\mathbf{y}}_j $ for EN $j\!\in\!\mathcal{M}/\{i\}$. Hence, for the messages that ENs in $\mathcal{M}/\{i\}$ can decode, EN $k$ must also be able to decode them, and we have $$\label{fano2}
\!\!\!H(\mathcal{W}^j_{t}|\hat{\mathbf{y}}_k,\!\overline{\mathcal{W}},\!\mathcal{W}_{r})\!\le\! H(\mathcal{W}^j_{t}|\mathbf{y}_j,\!\overline{\mathcal{W}},\!\mathcal{W}_{r})\! \le\! T^u \epsilon, j\!\!\in\!\!\mathcal{M}\!/\!\{i\}\!.\!\!$$ Using genie-aided information, receiver cooperation, and noise reducing as discussed above can only improve channel capacity. Thus, we obtain the following chain of inequalities,

$$\begin{aligned}
&|\mathcal{W}_{r}|+|\mathcal{W}_{t}|\nonumber\\
&= H(\mathcal{W}_{r},\mathcal{W}_{t}) \nonumber\\
&\stackrel{(a)}{=}\!H(\mathcal{W}_{r},\mathcal{W}_{t}|\overline{\mathcal{W}})\nonumber\\
&\stackrel{(b)}{=}\!I(\mathcal{W}_{r},\mathcal{W}_{t};\hat{\mathbf{y}}_k|\overline{\mathcal{W}}) + H(\mathcal{W}_{r},\mathcal{W}_{t}|\hat{\mathbf{y}}_k,\overline{\mathcal{W}})\nonumber\\
&\stackrel{(c)}{=}\!I(\mathcal{W}_{r},\mathcal{W}_{t};\hat{\mathbf{y}}_k|\overline{\mathcal{W}}) + H({\mathcal{W}_{r}|\hat{\mathbf{y}}_k,\overline{\mathcal{W}}})+H({\mathcal{W}_{t}|\hat{\mathbf{y}}_k,\mathcal{W}_{r},\overline{\mathcal{W}}})\nonumber\\
& \le I(\mathcal{W}_{r},\mathcal{W}_{t};\hat{\mathbf{y}}_k|\overline{\mathcal{W}})+ H({\mathcal{W}_{r}|\hat{\mathbf{y}}_k,\overline{\mathcal{W}}})\!+\! \!\!\!\sum\limits_{j\in\mathcal{M}/\{k\}}\!\!\!\!\!H({\mathcal{W}^j_{t}|\hat{\mathbf{y}}_k,\mathcal{W}_{r},\overline{\mathcal{W}}})\nonumber\\
&\stackrel{(d)}{\le} I(\mathcal{W}_{r},\mathcal{W}_{t};\hat{\mathbf{y}}_k|\overline{\mathcal{W}}) +  T^u \epsilon+ \sum\limits_{j\in\mathcal{M}/\{k\}} T^u\epsilon\nonumber\\
&\stackrel{(e)}{\le}  I(\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_{a_i},\mathbf{x}_{i_o}:\hat{\mathbf{y}}_i|\overline{\mathcal{W}}) + M T^u\epsilon \nonumber\\
&\stackrel{(f)}{\le}T^u \log P_u  + M T^u\epsilon,  \label{inequality}\end{aligned}$$

where (a) is due to the independence of messages, (b) and (c) are based on the chain rule, (d) follows Fano[’]{}s inequalities (\[Fano11\]) and (\[fano2\]), (e) uses the data processing inequality, and (f) follows the DoF bound of MAC channels. Dividing (\[inequality\]) by $NnB\!/\!\log\!P_u$, and let $P_u\!\to\!\infty$ and $\epsilon\!\to\!0$ as $B\to\infty$, we have $$\begin{aligned}
\!\!\!\tau^u\!&\ge\!\frac{|\mathcal{W}_{r}|\!+\!|\mathcal{W}_{t}|}{NnB}\!=\!\sum\limits_{i\in\mathcal{M}}\!\!\gamma_{i,k} \!+\! 1\!-\gamma_{i_o,k}\! = \!\sum_{i\in\mathcal{M}/\{i_o\}}\!\!\!\gamma_{i,k}\!  +\!1.\!\!\end{aligned}$$ Hence, the NULT for a particular task assignment $\boldsymbol{\gamma}\!\triangleq\![\gamma_{i,k}]_{i\in\mathcal{M},k\in\mathcal{K}}$ satisfies $\tau^u \!\ge\! \sum_{i\in\mathcal{M}/\{i_o\}}\!\gamma_{i,k} \!+\! 1$ for $k\!\in\!\mathcal{K},i_o\!\in\!\mathcal{M}$, i.e., the minimum NULT for task assignment policy $\boldsymbol{\gamma}$ is lower bounded by

$$\tau^{u^*}(r,\boldsymbol{\gamma}) \ge \max\limits_{ k\in\mathcal{K},\forall i_o\in\mathcal{M}}~ \sum_{i\in\mathcal{M}/\{i_o\}}\gamma_{i,k}  + 1.$$

Furthermore, the minimum NULT over all feasible task assignment is given as $\tau^{u^*}\!(r)\!=\!\min\limits_{\boldsymbol{\gamma}}\tau^{u^*}\!(r,\boldsymbol{\gamma})$, i.e., it can be lower bounded by the optimal solution of the optimization problem

$$\begin{aligned}
\mathcal{P}_1:\quad&\min\limits_{\boldsymbol{\gamma}}~\max\limits_{ k\in\mathcal{K},\forall i_o\in\mathcal{M}}~ \sum_{i\in\mathcal{M}/\{i_o\}}\gamma_{i,k}  + 1 \nonumber\\
\mathnormal{s.t.}&\quad (\ref{cons111}), (\ref{cons222}).\nonumber\end{aligned}$$

By defining a new variable $\lambda_{k,\bar{i}_o}\!=\!\sum\limits_{i\in\mathcal{M}/\{i_o\}}\gamma_{i,k}$, Problem $\mathcal{P}_1$ can be transformed into

$$\begin{aligned}
\mathcal{P}_2:\quad&\min\limits_{\boldsymbol{\lambda}}~\max\limits_{ k\in\mathcal{K},\forall i_o\in\mathcal{M}} \lambda_{k,\bar{i}_o} + 1 \nonumber\\
\mathnormal{s.t.}&\quad \sum_{k \in\mathcal{K}}\lambda_{k,\bar{i}_o} = r(M-1), ~ i_o\in\mathcal{M} \\
                 &\quad ~0\le \lambda_{k,\bar{i}_o} \le M-1,~ k \in\mathcal{K}.\end{aligned}$$

We can easily prove that the optimal solution to $\mathcal{P}_2$ is given by $\lambda^*_{k,\bar{i}_o}\!=\!r(M\!-\!1)/K$ for $k\!\in\!\mathcal{K}$ and $i_o\!\in\!\mathcal{M}$, which is unique and can be proved by contradiction. In turn, we use $\{\lambda^*_{k,\bar{i}_o}\}$ to construct a feasible solution to $\mathcal{P}_1$ by letting $\gamma^*_{i,k}\!=\!\lambda^*_{k,\bar{i}_o}/(M\!-\!1)$ for $i\!\in\!\mathcal{M}$ and $k\!\in\!\mathcal{K}$, and hence obtain the optimal solution to $\mathcal{P}_1$ as $\gamma^*_{i,k}\!=\!r/K$. Therefore, at repetition order $r$, the minimum NULT $\tau^{u^*}(r)$ is lower bounded by

$$\label{lowerbound_tauu}
\tau^{u^*}(r)\ge \frac{r(M-1)+K}{K}.$$

The lower bound of NULT in Theorem \[lower\_bound\] is thus proved. It is seen that (\[lowerbound\_tauu\]) is the same as (\[achieveUpoad\]) in Theorem \[achievableresults\], so the achievable NULT in (\[achieveUpoad\]) is optimal, which proves the optimality of upload times stated in Lemma \[gapLemma\].

Lower Bound and Multiplicative Gap Analysis of NCT {#binaryconverseup}
--------------------------------------------------

### Lower bound

Let $\{X_k\}_{q:K}$ denote the $q$-th smallest value of $K$ variables $\{X_k\}^{K}_{k=1}$ and $q\!:\!K$ denote the index of $q$-th smallest variable. For a particular task assignment policy $\big\{\mathcal{U}_{i,\mathcal{K}^{'}}\!\big\}$ satisfying (\[cons111\]) and (\[cons222\]) and a recovery order $q$, the computing time when the $q$-th fastest EN finishes its assigned tasks is lower bounded by $$\begin{aligned}
T^c_{q:K} &= \bigg\{\!\mu m\sum\limits_{i\in\mathcal{M}}\gamma_{i,k}N \omega_k\!\bigg\}_{\!\!q:K}\nonumber\\
&\stackrel{(g)}{\ge}  \max\limits_{t\in[q-1]}\bigg\{\!\mu m \bigg\{\sum\limits_{i\in\mathcal{M}}\gamma_{i,k}N \bigg\}_{\!\!t:K}\!\!\!\cdot\left\{\omega_k\right\}_{q-t:K}\!\bigg\},\end{aligned}$$ where $(g)$ follows the fact that for $K$ product values like the form $\{x_ky_k\}^K_{k=1}$, there must exist $q$ values whose product term (either $x_k$ or $y_k$) is not larger than that of $\{x_ky_k\}_{q:K}$. We thus have $\{x_ky_k\}_{q:K}\!\ge\!\{x_k\}_{t:K}\{y_k\}_{q-t:K}$, $t\!\in\![q\!-\!1]$. Taking the expectation on $T^c_{q:K}$, we have

$$\begin{aligned}
\mathbb{E}\left[ T^c_{q:K} \right] & \ge \mathbb{E}\left[\max\limits_{t\in[q-1]}\bigg\{\!\mu m \bigg\{\sum\limits_{i\in\mathcal{M}}\gamma_{i,k}N \bigg\}_{\!\!t:K}\!\!\!\cdot\left\{\omega_k\right\}_{q-t:K}\!\bigg\}\right]\nonumber \\
& \stackrel{(h)}{\ge} \max\limits_{t\in[q-1]}\bigg\{\!\mu m \bigg\{\sum\limits_{i\in\mathcal{M}}\gamma_{i,k}N \bigg\}_{\!\!t:K}\!\!\!\cdot\mathbb{E}\left[\left\{\omega_k\right\}_{q-t:K}\right]\!\bigg\} \nonumber\\
& \stackrel{(i)}{=} \max\limits_{t\in[q-1]}\frac{(H_K - H_{K-q+t})\mu m}{\eta} \left\{\sum\limits_{i\in\mathcal{M}}\gamma_{i,k}N \right\}_{\!\!t:K},\end{aligned}$$

where (h) follows $\mathbb{E}\big[\max\limits_{t}x_t\big]\!\ge\!\max\limits_{t}\mathbb{E}\left[x_t\right]$, (i) uses the $(q\!-\!t)$-th order statistic of $K$ i.i.d exponential random variables. The second term denotes the $t$-th smallest value among $K$ EN workload sizes. By (\[cons111\]) and (\[cons222\]), for $\forall i\!\in\!\mathcal{M}$, we let $\gamma_{i,k}\!=\!1$, $k\!=\!t\!+\!1\!:\!K,t\!+\!2\!:\!K,\cdots,K\!:\!K$, so the sum of the $t$ smallest values (i.e., $1\!:\!K$, $\cdots$,$t\!:\!K$) is lower bounded by $(r\!-\!K\!+\!t)^{+}NM$. Since the second term also represents the largest value among those $t$ smallest EN workload sizes, so this term can be further lower bounded by the average value $(r\!-\!K\!+\!t)^{+}NM/t$. So the average time for the $q$ fastest ENs to finish their tasks is lower bounded by $T^c(r,q)\!\ge\!\max\limits_{t\in[q-1]}\frac{(H_K - H_{K-q+t})\mu m}{\eta}\frac{(r-\!K\!+t)^{+}NM}{t}$. Normalizing it by $Nm/\eta$, the lower bound of the NCT is given by $$\tau^{c^*}(r,q)\ge \max\limits_{t\in[q-1]}\frac{(H_K - H_{K-q+t})(r-\!K\!+t)^{+}M\mu }{t}. \label{low_compu}$$

### Multiplicative gap

The multiplicative gap between the achievable NCT in Theorem \[achievableresults\] and the lower bound (\[low\_compu\]) satisfies $$\begin{aligned}
\frac{\tau^c(r,q)}{\tau^{c*}(r,q)} &\le \min\limits_{t\in[q-1]}\frac{Mr\mu(H_k\!-\!H_{K-q})t}{K(H_K - H_{K-q+t})(r-\!K\!+t)^{+}M\mu}\nonumber \\
&\le \min\limits_{t\in[q-1]} \frac{t}{(r-\!K\!+t)^{+}} \cdot\left(1+\frac{H_{K-q+t}\!-\!H_{K-q}}{H_K - H_{K-q+t}}\right)\nonumber\\
&\le \frac{q/2}{(r-\!K\!+q/2)^{+}} \cdot \left(1+\frac{\sum^{K-q/2}_{K-q+1}1/i}{\sum^{K}_{K-q/2+1}1/i}\right)\nonumber\\
&\le \frac{q/2}{(r-\!K\!+q/2)^{+}} \cdot \left(1+\frac{\frac{q}{2}\frac{1}{K-q+1}}{\frac{q}{2}\frac{1}{K}}\right) \nonumber\\
&= \frac{q/2}{(r-\!K\!+q/2)^{+}} \cdot \left(1+\frac{K}{K-q+1}\right).\end{aligned}$$ When $r\!\ge\!K\!-\!n_1$ and $q\!\le\!K(1\!-\!1/n_2)\!+\!1$ with integers $0\!\le\!n_1\!<\!q/2$ and $n_2\!\ge\!1$, we have $\frac{q/2}{(r-\!K\!+q/2)^{+}}\!\le\!\frac{q/2}{q/2-n_1}\!\le\!n_1\!+\!1$ and $K/(K\!-q+\!1)\!\le\!n_2$, respectively, and consequently, we have $\tau^c/\tau^{c*}\!\le\!(1\!+n_1 )(1\!+n_2)$. Since the upload time is optimal and increases strictly with $r$, the repetition order satisfies $r\!\ge\!\!K\!-n_1$ when the upload time $\tau^u\!\ge\!\tau^u_a(K\!-\!n_1)$.

Lower Bound and Multiplicative Gap Analysis of NDLT {#binaryconverseup}
---------------------------------------------------

### Lower bound

For a particular task assignment policy $\big\{\mathcal{U}_{i,\mathcal{K}^{'}}\!\big\}$ satisfying (\[cons111\]) and (\[cons222\]), and a particular subset of $q$ ENs denoted as $\mathcal{K}_q\!\subseteq\!\mathcal{K}$ whose outputs are available, each EN $k\!\in\!\mathcal{K}_q$ is assigned $r_{i,k}N$ input vectors from each user $i\!\in\!\mathcal{M}$ and can store $\mu m$ rows of $\mathbf{A}$. Since each user $i$ wants $mN$ row-vector product results $\{\mathbf{v}_{i,j}\!=\!\mathbf{A}_{m\times n}\mathbf{u}_{i,j}\}_{j\in[N]}$, it is equivalent to state that each EN $k$ can store $r_{i,k}\mu$ fractional outputs desired by each user $i$, denoted as $\mathcal{S}_{i,k}\!\triangleq\!\{\mathbf{A}_k\mathbf{u}_{i,j}\!:\mathbf{u}_{i,j}\!\in\!\mathcal{U}_{i,\mathcal{K}^{'}},k\!\in\!\mathcal{K}^{'}\}$ and with size $|\mathcal{S}_{i,k}|\!=\!\gamma_{i,k}\mu NmB$ bits, where $\gamma_{i,k}$ satisfies (\[cons111\]) and (\[cons222\]). Thus, the policy $\big\{\mathcal{U}_{i,\mathcal{K}^{'}}\!\big\}_{i\in\mathcal{M},k\in\mathcal{K}}$ with an available EN set $\mathcal{K}_q$ is equivalent to a particular computation results distribution $\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{K}_q}$. Let $\mathcal{M}_t\!\subseteq\!\mathcal{M}$ denote an arbitrary subset of $t$ users and $\mathcal{Q}_{q-t}\!\subseteq\!\mathcal{K}_q$ denote an arbitrary subset of $q\!-\!t$ ENs. Also, we have $\mathcal{M}_{M-t}\!=\!\mathcal{M}/\mathcal{M}_t$ and $\mathcal{Q}_t\!=\!\mathcal{K}_q/\mathcal{Q}_{q-t}$. For a particular computation results distribution $\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{K}_q}$, we adopt the arguments proved in [@sengupta2017fog Lemma 6] to derive the lower bound of the NDLT, i.e., intuitively, *given any subset of $t$ signals received at $t\!\le\!\min\{q,M\}$ users, denoted as $\{Y_i\}_{i\in\mathcal{M}_t}$, and the stored computation results information of $q-t$ ENs, denoted as $\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q-t}}$, all transmitted signals $\{X_{k}\}_{k\in\mathcal{K}}$ and all the desired outputs $\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]}$ can be resolved in the high-SNR regime.* First, we have the following equality,

$$\begin{aligned}
&MNmB \!= \! H\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]}\right) \nonumber\\
      \!&= \! I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{Y_i\}_{i\in\mathcal{M}_t},\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}\right) \!+ \! H\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]}|\{Y_i\}_{i\in\mathcal{M}_t},\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}\right).\label{ineq1}\end{aligned}$$

For the first term, following steps in [@sengupta2017fog Eq. (64)], we have

$$\begin{aligned}
&I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{Y_i\}_{i\in\mathcal{M}_t},\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}\right) \nonumber\\
&=I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{Y_i\}_{i\in\mathcal{M}_t}\right) + I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}|\{Y_i\}_{i\in\mathcal{M}_t}\right)\nonumber\\
&\le I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{Y_i\}_{i\in\mathcal{M}_t}\right) +
I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}},\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M}_t,j\in[N]}|\{Y_i\}_{i\in\mathcal{M}_t}\right)\nonumber\\
&=I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{Y_i\}_{i\in\mathcal{M}_t}\right) +
I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M}_t,j\in[N]}|\{Y_i\}_{i\in\mathcal{M}_t}\right)
\nonumber\\
&~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\!+\!I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}},|\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M}_t,j\in[N]},\{Y_i\}_{i\in\mathcal{M}_t}\right)\nonumber\\
&\le I\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]};\{Y_i\}_{i\in\mathcal{M}_t}\right) +
H\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M}_t,j\in[N]}|\{Y_i\}_{i\in\mathcal{M}_t}\right)
\nonumber\\
&~~~+H\left(\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}|\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M}_t,j\in[N]},\{Y_i\}_{i\in\mathcal{M}_t}\right)
-H\left(\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}|\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]},\{Y_i\}_{i\in\mathcal{M}_t}\right)\nonumber\\
&\!\stackrel{(j)}{\le}\!h\left(\{Y_i\}_{i\in\mathcal{M}_t}\right)-h\left(\{Y_i\}_{i\in\mathcal{M}_t}|\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]}\right) +
tNmB\epsilon  + H\left(\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}|\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M}_t,j\in[N]}\right)\nonumber\\
& \stackrel{(k)}{\le} tT\log\left(2\pi e(\Lambda P^d+1)\right) -  h\left(\{n_i\}_{i\in\mathcal{M}_t}|\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]}\right)  +
tNmB\epsilon  + \sum\limits_{k\in\mathcal{Q}_{q\!-\!t}}H\left(\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M}}|\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M}_t,j\in[N]}\right)\nonumber\\
& \stackrel{(l)}{\le}\!tT\log\left(2\pi e(\Lambda P^d+1)\right) -  tT\log\left(2\pi e \right) +
tNmB\epsilon  + \sum\limits_{k\in\mathcal{Q}_{q\!-\!t}}\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}H\left(\mathcal{S}_{i,k}\right)\nonumber\\
&\le tT\log\left(\Lambda P^d+1\right) + tNmB\epsilon  + \sum\limits_{k\in\mathcal{Q}_{q\!-\!t}}\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}\gamma_{i,k}\mu NmB, \label{ineq2}
 \end{aligned}$$

where, in step $(j)$, $\{Y_i\}$ are continuous random variables, the third term uses Fano[’]{}s inequality, the fourth term is because dropping the condition increases the entropy, the last term in last step is 0 since the storage information $\{\mathcal{S}_{i,k}\}$ are the functions of $\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M}_t,j\in[N]}$; In step $(k)$, the first term uses [@sengupta2017fog Lemma 5], and note that $\Lambda$ defined in [@sengupta2017fog Lemma 5] is a constant only depending on downlink channel coefficients in $\mathbf{H}^d$. For the second term, by [@sengupta2017fog Lemma 6] that proves the adopted argument, we have $$\begin{aligned}
\!\!\!H\left(\{\mathbf{v}_{i,j}\}_{i\in\mathcal{M},j\in[N]}|\{Y_i\}_{i\in\mathcal{M}_t},\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}\right)
\!\le\!tNmB\epsilon\!+\!T\log\det\left( \mathbf{I}_{M-t} +\tilde{\mathbf{H}}^d(\tilde{\mathbf{H}}^d)^{H}\right)\!,\!\! \label{ineq3}\end{aligned}$$ where the $(M\!-\!t)\!\times\!(M\!-\!t)$ matrix $\tilde{\mathbf{H}}^d$ defined in [@sengupta2017fog Lemma 6] only depends on the channel matrix $\mathbf{H}^d$, and $\mathbf{I}_{M\!-\!t}$ is a $(M\!-\!t)\!\times\!(M\!-\!t)$ identity matrix. The expressions of $\tilde{\mathbf{G}}$ and $\Lambda$ are omitted here since they can be treated as constants.

Substituting (\[ineq2\]) and (\[ineq3\]) into (\[ineq1\]), we have

$$\begin{aligned}
\!\!\!M NmB\!\le\!tT\log\left(\Lambda P^d+1\right) + 2tNmB\epsilon \! +\!\!\sum\limits_{k\in\mathcal{Q}_{q\!-\!t}}\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}\!\!\! \! \gamma_{i,k}\mu NmB\!+\! T\log\det\! \left( \mathbf{I}_{M-t}\!+\!\tilde{\mathbf{H}}^d(\tilde{\mathbf{H}}^d)^{H}\right)\!,\!\!\end{aligned}$$

Moving $T$ to the left side and dividing by $\frac{NmB}{\log P^d}$, we have

$$\begin{aligned}
\frac{T}{NmB/\log P^d}\ge \frac{M\!-\!\sum\limits_{k\in\mathcal{Q}_{q\!-\!t}}\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}\!\!\gamma_{i,k}\mu\!-\!2t\epsilon}{t}
\cdot\!\frac{t\log P^d}{t\log\left(\Lambda P^d\!+\!1\right)\!+\!\log\det\left( \mathbf{I}_{M-t} \!+\!\tilde{\mathbf{H}}^d(\tilde{\mathbf{H}}^d)^{H}\right)}.\end{aligned}$$

Taking $P^d\to\infty$ and $\epsilon\to 0$ as $B\to\infty$, the NDLT under the output distribution $\{\mathcal{S}_{i,k}\}_{i\in\mathcal{M},k\in\mathcal{Q}_{q\!-\!t}}$ is lower bounded by $$\tau^{d^*}\!(\mathcal{K}_{q},\mathcal{Q}_{q-t},r) \ge  \frac{M\!-\!\!\sum\limits_{k\in\mathcal{Q}_{q\!-\!t}}\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}\!\!\!\gamma_{i,k}\mu}{t},~ \forall \mathcal{Q}_{q-t}\subseteq\mathcal{K}_q.\!\!$$ Note that the adopted argument holds for any subset of $q\!-\!t$ ENs. Thus, by tasking the sum over all possible subset $\mathcal{Q}_{q-t}\subseteq\mathcal{K}_q$, we have $$\begin{aligned}
\binom{q}{q\!-\!t}\tau^{d^*}(\mathcal{K}_{q},q-t,r)& \ge \sum\limits_{\mathcal{Q}_{q-t}\subseteq\mathcal{K}_q} \!\!\!\frac{M\!-\!\!\sum\limits_{k\in\mathcal{Q}_{q\!-\!t}}\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}\!\!\!\gamma_{i,k}\mu}{t}\nonumber\\
& = \frac{\binom{q}{q-t}M\!-\!\!\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}\sum\limits_{\mathcal{Q}_{q-t}\subseteq\mathcal{K}_q}\sum\limits_{k\in\mathcal{Q}_{q\!-\!t}}\!\!\!\gamma_{i,k}\mu}{t}\nonumber\\
& = \frac{\binom{q}{q-t}M\!-\!\!\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}\binom{q-1}{q-t-1}\sum\limits_{k\in\mathcal{K}_q}\!\!\gamma_{i,k}\mu}{t}.\!\!\end{aligned}$$ For the particular policy $\big\{\mathcal{U}_{i,\mathcal{K}^{'}}\!\big\}$ with repetition order $r$ and satisfying (\[cons111\]) and (\[cons222\]), this lower bound also holds for any subset $\mathcal{K}_{q}$ since $K\!-\!q$ stragglers occur randomly, by taking the sum over all possible subsets $\mathcal{K}_{q}\subseteq\mathcal{K}$, we have

$$\begin{aligned}
\!\!\!\!\binom{\!K\!}{\!q\!}\!\binom{\!q\!}{\!q\!-\!t\!}\tau^{d^*}\!(q,q\!-\!t,r)
& \ge  \sum\limits_{\mathcal{K}_{q}\subseteq\mathcal{K}}\!\!\!\frac{\binom{q}{q-t}M\!-\!\!\sum\limits_{i\in\mathcal{M}_{\!M\!-\!t}}\!\!\!\!\binom{q-1}{q-t-1}\!\!\sum\limits_{k\in\mathcal{K}_q}\!\!\gamma_{i,k}\mu}{t}\nonumber\\
& = \frac{\binom{K}{q}\binom{q}{q-t}M\!-\!\!\!\sum\limits_{i\in\mathcal{M}_{\!M\!-\!t}}\!\!\!\binom{q-1}{q-t-1}\!\sum\limits_{\mathcal{K}_{q}\subseteq\mathcal{K}}\sum\limits_{k\in\mathcal{K}_q}\!\!\gamma_{i,k}\mu}{t}\nonumber\\
& = \frac{\binom{K}{q}\binom{q}{q-t}M\!-\!\!\!\sum\limits_{i\in\mathcal{M}_{M\!-\!t}}\!\!\!\binom{q-1}{q-t-1}\binom{K-1}{q-1}\!\!\sum\limits_{k\in\mathcal{K}}\!\!\gamma_{i,k}\mu}{t}\nonumber\\
& \stackrel{(m)}{=}\frac{\binom{K}{q}\binom{q}{q-t}M\!\!-\!(\!M\!\!-\!t)\binom{q-1}{q-t-1}\binom{K-1}{q-1}r\mu}{t},\!\!\label{eq46}\end{aligned}$$

where $(m)$ is due to (\[cons111\]). Remanaging (\[eq46\]), the lower bound of NDLT at the pair $(r,q)$ is given by

$$\begin{aligned}
\tau^{d^*}(q,q-t,r)&\ge \frac{M-(M\!-\!t)(q-t)\frac{r}{K}\mu}{t}, \label{tau_t}\end{aligned}$$

Since the argument we adopt to derive (\[tau\_t\]) holds for $1\!\le\!t\!\le\!\min\{q,M\}$, the lower bound of NDLT at $(r,q)$ can be optimized as $$\label{lowerbound_taud}
\tau^{d^*}(r,q)\ge \max_{t\in\{1,\cdots,\min\{q,M\}\}}\frac{M-(M\!-\!t)(q-t)\frac{r}{K}\mu}{t}.$$

### Multiplicative gap

By (\[achievedownload\]), the achievable NDLT is upper bounded by

$$\begin{aligned}
\tau^d&=\sum\limits^{\min\{r,q\}}_{p_1=r-K+q}B_{p_1}\left(\sum\limits^{l_{max}}_{p_2=l_{min}}\frac{B_{p_2}}{d^d_{p_1,M,p_2}}\!+\!\frac{B_{l_{p_1}\!-\!1}}{d^d_{p_1,M,l_{p_1}\!-\!1}}\right)\nonumber\\
&\stackrel{(m)}{\le}\sum\limits^{\min\{r,q\}}_{p_1=r-K+q}B_{p_1}\frac{\sum\limits^{l_{max}}_{p_2=l_{min}}\!B_{p_2}\!+\!B_{l_{p_1}\!-\!1}}{d^d_{p_1,M,1}}\nonumber\\
&\stackrel{(n)}{\le}\sum\limits^{\min\{r,q\}}_{p_1=r-K+q}\binom{q}{p_1}\binom{K-q}{r-p_1}\frac{1}{\binom{K}{r}}\cdot\frac{1}{d^d_{r-K+q,M,1}}\nonumber\\
&=\frac{1}{d^d_{r-K+q,M,1}},\end{aligned}$$

where $(m)$ is because $d^d_{p_1,M,p_2}$ increases with $p_2$ [@gckkl Lemma 1] and $(n)$ is because $d^d_{p_1,M,1}\!=\!p_1/(p_1\!+\!M\!-\!1)$ increases with $p_1$. By (\[lowerbound\_taud\]), we have $\tau^{d^*}(r,q)\!\ge\!M/\min\{q,M\}$, so the multiplicative gap satisfies

$$\begin{aligned}
\frac{\tau^d}{\tau^{d^*}}&\le\frac{\min\{q,M\}}{d^d_{r-K+q,M,1}} =\frac{\min\{q,M\}(r\!-\!K\!+\!q\!+\!M\!-\!1)}{(r\!-\!K\!+\!q)M}.\end{aligned}$$

If $q\!\le\!M$, we have $\frac{\tau^d}{\tau^{d^*}}\!\le\!\frac{q}{r-K+q}(\frac{q}{M}\!+\!\frac{M-1}{M}\!-\!\frac{K-r}{M})\!\le\!\frac{2q}{r-K+q}\!\le\!\frac{2q}{q-n}\!\le\!2(n\mu\!+\!1)$ for $r\!\ge\!K\!-\!n$; Otherwise, we have $\frac{\tau^d}{\tau^{d^*}}\!\le\!1\!+\!\frac{M-1}{r-K+q}\!\le\!1\!+\!\frac{q-1}{q-n}\!\le\!2\!+\!(n\!-\!1)\mu$ for $r\!\ge\!K\!-\!n$. Here, integers $n$ satisfies $n\!\le\!q\!-\!\frac{1}{\mu}$ due to $(r\!-\!K\!+\!q)\mu\!\ge\!1$. In summary, since $2(n\mu\!+\!1)\!>\!2\!+\!(n\!-\!1)\mu$, we have $\frac{\tau^d}{\tau^{d^*}}\!\le\!2(n\mu\!+\!1)$ for $r\!\ge\!K\!-\!n$. Furthermore, when the upload time $\tau^u\!\ge\!\tau^u_a(K\!-n)$, the repetition order satisfies $r\!\ge\!K\!-\!n$. Thus, when $r\!=\!K$, or equivalently, $\tau^u\!\ge\!\tau^u_a(K)$, we have $\frac{\tau^d}{\tau^{d^*}}\!\le\!2$.

### Outer Bound of Compute-Download Latency Region

By the feasible set $\mathcal{R}$ in (\[regionR\]) and the convexity of $\mathscr{T}^{*}(\tau^{u})$ in Remark \[remarkconvex\], for an NULT $\tau^u\!=\!\tau^u_a(r)$ in (\[achieveUpoad\]) for some $r$, an outer bound $\mathscr{T}_{out}(\tau^{u})$ of the compute-download latency region is given as the convex hull of set $\big\{\!\!\left(\tau^{c^*}\!\!(r,q),\tau^{d^*}\!\!(r,q)\right)\!\!:\!q\!\in\!\!\big[\lceil\!\frac{1}{\mu}\!\rceil\!+\!K\!-r\!:\!\!K\big]\!\big\}$.

[^1]: A short version is to appear in IEEE ISIT 2020. The work by K. Li and M. Tao is supported by the National Natural Science Foundation of China under Grant 61941106 and the National Key R$\&$D Project of China under Grant 2019YFB1802702. The work by J. Zhang and O. Simeone is funded by the European Research Council under the European Union’s Horizon 2020 Research and Innovation Programme (Grant Agreement No. 725731).

[^2]: For general $u\!\in\![\frac{1}{K},1]$ satisfying $K\mu\!=\!\beta \lceil K\mu\rceil\!+\!(1\!-\!\beta)\lfloor K\mu\rfloor$, we can use memory- and time-sharing methods to achieve the linear combinations of the latency triplets achieved at integers $\lceil K\mu\rceil$ and $\lfloor K\mu\rfloor$ for a fixed $r$.
