A Computation-Communication Tradeoff Study for

Mobile Edge Computing Networks

Kuikui Li, Meixia Tao, Zhiyong Chen
Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai, P. R. China
Email: {kuikuili, mxtao, zhiyongchen}@sjtu.edu.cn

Uplink Downlink
Abstract—In this paper, we exploit computation replication to
User 1 User 1
reduce the communication time for task offloading in mobile
edge computing networks, by introducing a tradeoff between Input W1 EN 1 Output Z
a
computation load, and communication latency defined as a
User 2 User 2
pair of the normalized uploading time (NULT) and normalized
downloading time (NDLT). The key idea of replication is to Input W2 EN 2 Output Z
a
let mobile users offload their tasks to multiple edge nodes for
User 3 User 3
repetitive execution so as to enable the transmission cooperation
in computed results downloading, and consequent interference Input W3
EN 3
Output Z
a
mitigation across users. We develop an achievable communication Fig. 1. A three-user three-server MEC network. This figure only shows
latency pair at a given computation load, where the NULT is the case that computation load r = 3. The uplink channel is the multicast
optimal and the NDLT is within a multiplicative gap of 2 to an interference channel whose per-receiver DoF is 1 achieved via TDMA, while
information theoretic lower bound. We show that in the specific the downlink is the MISO broadcast channel with full transmitter cooperation
interval, the NDLT can be traded by the computation load in an whose per-receiver DoF is 1 achieved by using zero-forcing precoding. Solid
inversely proportional function. circle denotes that the channels inside it carry the same information.

I. I NTRODUCTION Our work attempts to address the above question by proposing

a novel task offloading scheme with computation replication.
Mobile edge computing (MEC) has emerged as a promising The main idea of computation replication is to let mobile users
paradigm to assist mobile users in offloading heavy computa- offload their computation tasks to multiple ENs for repeated
tional tasks to edge servers for execution [1]. The completion execution so as to enable the multiple ENs to cooperatively
of task offloading consists of two delivery phases, where transmit the computed results back to users in the downlink.
mobile users first upload the input data of tasks to MEC This transmission cooperation can neutralize interferences
servers via the uplink channel, and then download the com- across users, and hence reduce the downloading time.
puted results through the downlink channel [2]–[4]. However, We illustrate the advantage of computation replication
wireless network is becoming interference-limited due to the through an example in 3-user 3-server MEC networks. First,
finite bandwidth resource. It forces the data delivery to be the consider that each user offloads its task to all 3 servers for
bottleneck of task offloading, especially for many emerging repeated computing. As shown in Fig. 1, in the uploading
mobile applications requiring large amounts of data transfer phase, each user takes turn to multicast its task input to all
over wireless networks, like virtual and augmented reality 3 ENs, consuming 3 time slots in total. In the downloading
[5]. The severe interference can significantly increase the total phase, all the ENs have the same message to transmit, and
delivery time consumed in these types of task offloading. the downlink channel thus becomes a virtual MISO broadcast
Motivated by this issue, our work aims to design a novel channel, and all computed results can be delivered to users
task offloading scheme to reduce the communication latency within 1 time slot by using zero-forcing precoding [6]. For the
in multi-user multi-server MEC networks. In specific, we baseline scheme where each task is offloaded to an individual
consider an MEC network, where a set of N mobile users EN, both uplink and downlink channels are 3-user interference
offload computationally heavy tasks to a set of M computing- channels [7]. Both task uploading and downloading can be
enabled edge nodes (ENs). Each task has an input data denoted completed within 2 time slots by using interference alignment.
as Wj and an output data denoted as W fj , j = 1, 2, · · · , N . It is seen that by computation replication, the downloading
We define the computation load r as the average number of time is reduced from 2 time slots to 1 time slot while the
ENs to compute a task, i.e., the degrees of the replication for uploading time is increased from 2 time slots to 3 time
executing a task. The communication latency is defined as the slots. For those computation tasks whose output data size is
transmission time pair, denoted as (τ u , τ d ), for uploading the much larger than the input data size or the input data size
task inputs and downloading the computed outputs. It naturally is negligible, computation replication can bring significant
arises the following fundamental question: benefits in reducing the overall communication latency. This
• Given a computation load r, what is the minimum achiev- example only presents a particular case r = 3 for M=N= 3. A
able communication latency (τ u , τ d ) for completing task general case for any feasible computation load r in the MEC
offloading in such MEC systems? network with M servers and N users is studied in this work.
 Contributions. We consider binary offloading where the server and they all communicate with all users via a shared
computation tasks are not dividable. For a given computation wireless channel. Denote by M = {1, 2, . . . , M } the set of
load r, we propose a task assignment scheme where each task ENs and N = {1, 2, . . . , N } the set of users. The commu-
is offloaded to r different ENs for repeated computing, and nication link between each EN and each user experiences
each EN has an even assignment of N r
M tasks. By utilizing the both channel fading and an additive white Gaussian noise. Let
duplicated computation results on multiple ENs, transmission hij (gji ) denote the uplink (downlink) channel fading from
cooperation can be exploited in the data downloading phase user j ∈ N (EN i ∈ M) to EN i ∈ M (user j ∈ N ). It is
to mitigate multi-user interferences via interference neutraliza- assumed to be independent and identically distributed (i.i.d.)
tion, and hence improve the transmission rate of the downlink as some continuous distribution.
channel. The main distinction in the communication latency The network is time-slotted. At each time slot, each user
(τ u , τ d ) analysis lies at the degree of freedom (DoF) analysis generates an independent computation task to be offloaded to
of circular cooperative interference-multicast channels. We the ENs for execution. The computation task on each user j,
obtain the optimal per-receiver DoF for the uplink channel, and for j ∈ N , is characterized by the input data to be computed,
an order-optimal achievable per-receiver DoF for the downlink denoted as Wj , with size |Wj | = L bits, the computed output
channel. Based on these DoF regions, we develop an order- data, denoted as Wfj , with size |W e bits1 . We consider the
fj | = L
optimal achievable communication latency pair at computation binary computation task offloading model [2], which requires
load r, where the NULT is optimal compared to a lower bound a task to be executed as a whole. It is suitable for simple tasks
obtained by using genie-aided arguments, and the NDLT is that are tightly integrated in structure and are not separable.
within a multiplicative gap of 2 to a lower bound obtained B. Task Offloading Procedure
based on the optimal DoF of MISO broadcast channels.
Before the task offloading procedure begins, the system
Moreover, we reveal that the NDLT is an inversely propor-
needs to decide which EN or which set of ENs should each
tional function in the interval MM+N N
≤ r ≤ M, which presents
task be assigned to for execution. We denote by Ti the set of
the computation-communication tradeoff. We further reveal
that the decrease of NDLT is also at the expense of the increase S to EN i, i ∈ M. Every task must be computed,
tasks assigned
so we have i∈M Ti = {W1 , · · · , WN }.
in the NULT, which thus forms another NULT-NDLT tradeoff.
Related works. The idea of computation replication has Definition 1. For a given task assignment scheme {Ti }, the
been utilized in distributed computer systems, like MapReduce computation load r, 1 ≤ r ≤ M , is defined as the total number
and Spark, to enable coded multicast opportunities for data of tasks computed at all the M ENs, normalized by the number
shuffling across servers [8], or alleviate the random server of tasks N , i.e., P
|Ti |
straggling to shorten the response time [9], [10]. These frame- r , i∈M (1)
works are different from the task uploading and downloading N
procedures between users and ENs in wireless MEC systems. Similar to [8], the computation load r can be interpreted as
Our work is an attempt to exploit this idea in MEC systems the average number of ENs to compute each task and hence
to enable data-level transmission cooperation in downloading is a measure of computation repetition.
the computed results to mitigate the interference across users Given a feasible task assignment strategy {Ti }, the overall
in wireless networks. This is motivated by the interference offloading procedure contains two delivery phases, an input
neutralization technique enabled by transmitter cooperation in data uploading phase and an output data downloading phase.
interference networks [6], [11]. 1) Uploading phase: Each user j employs an encoding
Note that transmitter cooperation has been utilized in our function to map its task inputs Wj and channel coeffi-
previous work [12] that considers partial offloading where cients H , [hij ]i∈M,j∈N to a length-T u codeword Xj ,
u

each task can be divided arbitrarily, and the uplink and (Xj (t))Tt=1 , where Xj (t) ∈ C is the transmitted symbol at
downlink channels are cooperative X-multicast channels. In time t ∈ [T u ]. Each codeword has an average power constraint
this paper, we consider binary offloading, and the uplink and of Pu , i.e., T1u ||Xj || ≤ Pu . Then, the received signal Yi (t) ∈ C
downlink channels become circular cooperative interference- of each EN i at time t ∈ [T u ] is given by
N
multicast channels. Moreover, [12] aims to minimize the total Yi (t) =
X
hij (t)Xj (t) + Zi (t), ∀i ∈ M, (2)
communication and computation time, and hence cannot give j=1
a formulation on the relationship between computation load where Zi (t) ∼ CN (0, 1) is the noise at EN i. Each ENui uses
and communication latency in MEC systems. a decoding function to map received signals (Yi (t))Tt=1 and
Notations: [a : b] denotes the set {a + 1, a + 2, . . . , b}, [K] channel coefficients H to the estimate {Ŵj : Wj ∈ Ti } of its
denotes the set {1, 2, . . . , K}. assigned task inputs. The 
error probability is given by

II. P ROBLEM F ORMULATION [ n o
Peu = max P  Ŵj 6= Wj  . (3)
i∈M
A. MEC Network Model Wj ∈Ti

We consider an MEC network consisting of M single- 1 Note that the extension to the general case where each task has distinct
antenna ENs and N single-antenna users, as shown in Fig. input (or output) data size causes the uploading (or downloading) times for
1 with M = N = 3. Each EN is equipped with a computing different tasks unaligned, which is intractable for further analysis.
 Our goal is to characterize the optimal communication
2) Downloading phase: After receiving the assigned task latency pair at any given feasible computation load r.
input data and executing them at the server, n each EN oi III. M AIN R ESULTS
obtains the output data of its assigned tasks, Wfj : Wj ∈ Ti ,
Theorem 1. (Inner bound).
An achievable communication
and begins to transmit these computed results back to users.
latency pair τau (r), τad (r) at an integer computation load
The computed results downloading is similar to the task
r ∈ [M ], for binary task offloading in the MEC network with
uploading operation. Briefly, each EN encodes the task outputs
n o
fj : Wj ∈ Ti and channel coefficients G , [gji ]j∈N ,i∈M M ENs and N users, is givenby
W Nr

u
into a codeword of block length T d over the downlink in- τa (r) = min 1 + ,N , (8)
M
terference channel, with an average power constraint of Pd . 
N N

Each user j decodes its desired task output data W fj from its τad (r) = min 1 + , , (9)
ˆ M r
received signals and G, and obtain the estimate Wf j . The error
when M N
∈ Z+ . If M N
is not an integer, we can always find δ1
probability is given by and δ2 such that M N +δ1 N
  −δ2 is the closest integer to M and the
ˆ above results still hold by replacing N with N+δ1 and M with
Ped = max P W f j 6
= W
f j . (4)
j∈N M− δ2 . An inner bound of the optimal communication latency
 
region, denoted as Tin , is given by the union of all achievable


A task offloading policy, denoted as {Wj,Φ }, L, L e , r , with
computation load r consists of a sequence of task assignment latency pairs (τ u (r), τ d (r)) at all integer computation load r’s
schemes {Wj,Φ }, task input uploading schemes with time T u , satisfying τ u (r) ≥ τau (r) and τ d (r) ≥ τau (r) for ∀r ∈ [M ].
and task output downloading schemes with time
T d , indexed We prove the achievability of Theorem 1 in Section IV.
by the task input and output data size pair L, L
e . It is said to
Theorem 2. (Outer bound).

The optimal communication la-
be feasible when the error probabilities Pe and Ped approach
u ∗ ∗
tencynpair τ u (r), τ d (r) at any feasibleo computation load
to zero when L → ∞ and L e → ∞. PM
r ∈ r : i=1 ai = N r, ai ∈ [0 : N ], ∀i ∈ M 2 , for binary task
C. Performance Metric offloading in the MEC network with M ENs and N users, is
We characterize the performance of the considered MEC lower bounded by  
network by the computation load r as well as the asymptotic ∗ Nr
τ u (r) ≥ min 1 + ,N , (10)
communication times for task input uploading and output M
downloading. ∗ N
τ d (r) ≥ . (11)
min{M, N }
Definition 2. The normalized uploading time (NULT) and An outer bound of the optimal communication latency region,
normalized downloading time (NDLT) for a given feasible denoted as Tout , is given by the union of all latency pairs
task offloading policy with computation load r are defined, (τ u (r), τ d (r)) at all feasible computation load r’s satisfying
respectively, as 
Nr

N
u
EH [T u ] τ (r) ≥ +1, N , τ d (r) ≥ (12)
τ u (r) , lim lim , (5) M min{M, N }
Pu →∞ L→∞ L/ log Pu n P o
M
for ∀r ∈ r : i=1 ai = N r, ai ∈ [0 : N ], ∀i ∈ M .
EH [T d ]
τ d (r) , lim lim . (6)
Pd →∞ L→∞
e L/
e log Pd The full proof of Theorem 2 is given in Section V. Here,
we give the main idea of converse proof. First, we use genie-
The NULT (or NDLT) definition follows the NDT defined in
aided arguments to derive a lower bound on the NULT of
[13]. Note that L/logPd (or L/logP
e d ) is the reference time to
any given feasible task assignment with computation load r.
transmit the task input (or output) data of L (or L) e bits for one
Then, we optimize the lower bound over all feasible task
task in a Gaussian point-to-point baseline system in the high
assignment schemes to obtain the minimum NULT for a given
SNR regime. Thus, an NULT (or NDLT) of τ u (r) (or τ d (r))
computation load r. For NDLT, since the downlink channel
indicates that the time required to upload (or download) the
capacity in this problem cannot exceed that of a virtual MISO
tasks of all users is τ u (r) (or τ d (r)) times of this reference
broadcast channel with N single-antenna receivers and a M -
time period.
antenna transmitter, so we have the lower bound of NDLT in
Definition 3. A communication latency pair (τ u (r), τ d (r)) at (11). By comparing the achievable NULT and NDLT to their
a computation load r is said tobe achievable if there exists a lower bounds, we prove the optimality of NULT and the gap


feasible task offloading policy {Wj,Φ }, L, L , r . The opti-
e of NDLT, which are given below.
mal communication latency region is the closure  of the set of Corollary 1. (Gap of NULT, NDLT). At a computation load
all achievable communication latency pairs (τ u (r), τ d (r) r ∈ [M ], the achievable NULT in (8) is optimal, and the
at all possible computation load r’s, i.e.,
2 Note that different from the achievable inner bound in Theorem 1, the outer
T (r) , closure τ u (r), τ d (r) : ∀ τ u (r), τ d (r) is achievable,



bound in converse proof given in Section V holds for any feasible r for binary
∀r ∈ [1, M ]} . (7) offloading, and this feasible region contains the integer set {r : r ∈ [M ]}.
achievable NDLT in (9) is within a multiplicative gap of 2 2.2

to its minimum. 2
r=1
1.8 increasing r
The proof of Corollary 1 is also given in Section V.
Fig. 2 shows the inner bound Tin and outer bound Tout of

NDLT (τd)
1.6
2 Inner bound
1.4
the optimal communication latency region in the MEC network Outer bound
with M = N = 10. 1.2

Now, we demonstrate how the computation load r affect- 1

r=1 increasing r r = 9 (r = 10)
s the achievable communication latency (τau (r), τad (r)). By 0.8
2 4 6 8 10 12
NULT (τu)
discussing the min function terms in Eq. (8) and Eq. (9),
Fig. 2. The inner bound Tin and outer bound Tout of the optimal
we have the monotonicity of the achievable computation- communication latency T in the MEC network with M = N = 10. The
communication function (τau (r), τad (r)): achievable NULT is optimal while the gap of NDLT is within 2.
• The NULT τau (r) increases strictly with the computation
It is further seen from Fig. 2 that the achievable inner bound
load r for 1 ≤ r ≤ M − M
N , and then keeps a constant N is composed of three sections corresponding to three different
for M − MN ≤ r ≤ M .
N MN intervals of the computation load, and the lower envelop of the
• The NDLT τad (r) keeps a constant 1+M for 1 ≤ r ≤ M+N ,
inner bound at 5 ≤ r ≤ 9 presents the tradeoff between NULT
and then is inversely proportional to the computation
MN and NDLT, which is in an inversely proportional form.
load r for M+N ≤r≤M.
Remark 1. The achievable computation-communication func-

N2 N
 IV. ACHIEVABLE TASK O FFLOADING S CHEME
tion (τau (r), τad (r)) has two corner points 1+ M+N , 1+ M
 
N2 MN 1) Task uploading: Consider that the system parameters M
and N, M N−M , corresponding to r = M+N and r = M−M N, N
respectively. They are explained as follows: and N satisfy M ∈ Z+ such that N r = M n holds for ∀r ∈ [M ],
where r is the integer computation load and n is an integer
• For input data uploading, before r increases to M − M N, in [N ]. By doing so, in the proposed task assignment method,
the NULT is increasing since more traffic is introduced we let each task be executed at exactly r different ENs and let
in the uplink. When r grows to more than M − M N , there each EN execute n distinct tasks with even load. Note that if
is no need to increase the NULT since all tasks can be N
M is not an integer, we can inject δ1 (≥ 0) tasks, or let δ2 (≥ 0)
uploaded by using TDMA within N time slots. ENs idle and use the remaining ENs for task offloading, such
MN
• For output data downloading, before r increases to M+N , N +δ1 N
that M −δ2 is the integer closest to M , denoted as n1 . In this
the increasing transmission cooperation gain brought by way, we still have (N +δ1 )r = (M −δ2 )rn1 for ∀r ∈ [M −δ2 ],
computation replication cannot exceed the fixed interfer- and can use the new N +δ1 and M −δ2 to replace N and M
ence alignment gain in terms of the NDLT reduction, to obtain the corresponding analytical results.
and hence only interference alignment is utilized and the
MN To ensure even task assignment on each EN, we perform
NDLT keeps fixed. When r grows to more than M+N , the
circular assignment. Specifically, the set of tasks assigned to
transmission cooperation gain is larger than the fixed
EN i ∈ M is given by
interference alignment gain, transmitter cooperation is 
thus utilized in data downloading and the NDLT begins Ti = Wj+1 : j ∈ [(i−1)n : (in−1)] (mod N ) . (13)
to decrease with r. An example of the task uploading for M = N = 4 and r = 3
is shown in Fig. 3.
It can be easily proved that M− M MN
N ≥ M +N due to M , N ≥ 2. Given the above task assignment in (13), the uplink channel
Hence, we have the following remark to reveal the tradeoff formed by uploading the N tasks to their corresponding ENs is
between computation load and communication latency, and referred to as the circular interference-multicast channel with
illustrate the interaction between the NULT and NDLT. multicast group size r. This channel is different from the X-
Remark 2. It is concluded that there exists a computation- multicast channel with multicast group size r defined in [14],
communication tradeoff in the specific interval of the com- [15], where any subset
of r receivers can form a multicast
putation load, namely, the achievable NDLT τad (r) can be group, resulting in M r multicast groups,
and each transmitter
decreased in an inversely proportional way by increasing the needs to communicate with all the M r multicast groups. In
computation load in the interval MM+N
N
≤ r ≤ M . In addition, our considered circular interference-multicast channel, there
in this tradeoff, the NDLT is decreased also at the expense of are only N multicast groups which are performed circularly
the increase in NULT, which thus forms another NULT and by the M receivers and each transmitter only needs to com-
NDLT tradeoff. Hence, computation replication can signifi- municate with one multicast group. The optimal per-receiver
cantly shorten the communication latency for offloading the DoF of this uplink channel is given as follows.
applications whose computed results delivery time dominates Lemma 1. The optimal per-receiver DoF of the circular
the entire offloading time, such as AR applications of which interference-multicast channel with N transmitters and M
N
the output data size is much larger than the input data size. receivers satisfying M ∈ Z+ and multicast group size r is
 Uplink Downlink

User 1 EN 1 User 1 a DoF of Nr for each user, and then compare it with the per-
Z Z
a receiver DoF of NM +M achieved by only using interference


User 2 EN 2 User 2
Z alignment. Please refer to Appendix B for the full proof.
Z
a
User 3 EN 3 User 3 The traffic load for each user to download its task output
Z 
Z
a data is L bits. Hence, by [13, Remark 3] and [14, Remark 1],
load r is given by
User 4 User 4
Z
EN 4
Z
the NDLT for each user at computation
a 
aZ


1 N N
Fig. 3. Illustration of even task assignment for M = N = 4 and r = 3. τad (r) = = min +1, , r ∈ [M ]. (17)
The tasks circularly assigned to 4 ENs are {W1 , W2 , W3 }, {W4 , W1 , W2 }, DoFrd M r
{W3 , W4 , W1 }, and {W2 , W3 , W4 }. The uplink channel is the circular Based on Eq. (15) and Eq. (17), we thus have the achievable
interference-multicast channel whose per-receiver DoF is 34 , while the down-
link is the circular cooperative interference channel whose per-receiver DoF is communication latency pair (τau (r),τad (r)) at an integer com-
3
4
. Solid circle denotes that the channels inside it carry the same information. putation load r ∈ [M ] for binary offloading. An inner bound

given by aZ  of the optimal communication latency regionu can be given by

  the union of all achievable latency pairs (τ (r), τ d (r)) at all
Nr r
DoFru = max , , r ∈ [M ]. (14) integer computation load r’s satisfying
Nr + M M
τ u (r) ≥ τau (r), τ d (r) ≥ τau (r), ∀r ∈ [M ]. (18)
Proof: First, we use partial interference alignment scheme
proposed in [7] to achieve a DoF of NN r
r+M for each receiver. V. C ONVERSE P ROOF OF O UTER B OUND
r
Then, we compare it to the DoF of M achieved by TDMA.
The detailed achievable scheme and optimality proof are given A. Lower bound of NULT
in Appendix A. We prove the lower n bound of NULT at any feasible com- o
The traffic load for each EN to receive its assigned tasks is putation load r ∈ r : PM a = N r, a ∈ [0 : N ], ∀i ∈ M ,
Nr i=1 i i
M L bits. Based on [13, Remark 3] and [14, Remark 1], the u∗
 Nr
NULT for each EN at computation load r can be calculated as i.e., τ (r) ≥ min M +1, N . First, we use genie-aided
Nr   arguments to derive a lower bound on the NULT of any given
u M Nr
τa (r) = = min + 1, N , r ∈ [M ]. (15) feasible task assignment with a computation load r. Then,
DoFru M we construct an optimization problem and solve its optimal
2) Results downloading: After computing all offloaded solution to acquire the lower bound on the minimum NULT
tasks, ENs begin to transmit the computed results back to of all feasible task assignment schemes.
users via downlink channels. Recall that each task is computed Given a computation load r. Consider an arbitrary task
at r different ENs and each EN i has the computed results assignment scheme where the number of tasks assigned to
of n different tasks Ti , as given in (13). Each user j wants each EN i is denoted as a , ∀i ∈ M, and satisfies
i
the computed results W fj for ∀j ∈ N , which is owned in r M
X
different ENs. Multiple ENs with the same computed results ai = N r, (19)
can exploit transmission cooperation to neutralize interferences i=1
across users [6], [11]. The computation results downloading ai ∈ [0 : N ], i ∈ M. (20)
for M = N = 4 and r = 3 is shown in Fig. 3. We refer to
Note that we only need consider ai > 0 case since ai =
the downlink channel formed by downloading the N tasks as
0 means no task is assigned to EN i and we can remove
the circular cooperative interference channel with transmitter
EN i from the EN set M, which will not change the results.
cooperation group size r. This channel is different from the
Consider the following three disjoint subsets of task input data
cooperative X channel with transmitter cooperation group size
(or messages):
r defined in [14], [16], where any subset
of r transmitters can
form a cooperation group, resulting in M
groups in total, and Wr = {Wj,Sj : j ∈ N , i ∈ Sj }, (21)
r
each transmitter cooperation group has messages to send to all Wt = {Wj,Sj : j = to , i ∈
/ Sj }, (22)
receivers. In our considered downlink channel, there are only W = {Wj,Sj : j 6= to and i ∈ / Sj }, (23)
N cooperation groups which are performed circularly by the where Wj,Sj denotes the input message of the task from user
M transmitters and each group only needs to communicate j assigned to all ENs in subset Sj , and to denotes one of the
with one receiver. An achievable per-receiver DoF of this users that do not offload their tasks to EN i, i.e., Wr ∩Wt = ∅.
downlink channel is given as below. It is seen that the set Wr indicates the messages that EN i need
Lemma 2. An achievable per-receiver DoF of the circular decode, i.e., |Wr | = ai ; The set Wt is a nonempty set with
cooperative interference channel with M transmitters and cardinality |Wt | = 1 when EN i is not assigned all N tasks,
N
N receivers satisfying M ∈ Z+ and transmitter cooperation i.e., ai < N , since user to exists in this case; Otherwise, we
group size r is given by   have Wt = ∅ for ai = N . We will show that set Wr ∪Wt has
M r
DoFrd = max , , r ∈ [M ], (16) the maximum number of messages that can be decoded by EN
N +M N
i.
and it is within a multiplicative gap of 2 to the optimal DoF.
Let a genie provide the messages W to all ENs, and
Proof: We first use interference neutralization to achieve additionally provide messages Wr to ENs in M/{i}. The
received signal of EN i can be represented as where (a) is due to the independence of messages, (b) and (c)
M
X follow from the chain rule, (d) uses Fano’s inequalities (27)
ŷi = Hij xj + Hito xto + ẑi , (24) and (30), (e) is the data processing inequality, and (f) uses the
j=1,6=to DoF bound of the MAC channel. By dividing on logLPu , and
where Hij , xj , zi are diagonal matrices representing the chan- taking Pu → ∞ and  → 0, we have τ u ≥ |Wr | + |Wt | =
nel coefficients between user j and EN i, signal transmitted min{ai + 1, N }.
by user j, noise received at EN i, over the block length T u , Thus, for any given feasible task assignment a , [ai ]i∈M ,
respectively. Note that we reduce the noise at EN i from zi to the NULT satisfies τ u ≥ min{ai + 1,N } for ∀i ∈ M, i.e.,
ẑi by a fixed amount such that its received signal yi can be the minimum NULT for this given task assignment is lower
replaced by ŷi . The ENs in M/{i} have messages W ∪Wr , bounded by
which do not include the message of user to . Using these
 
∗

genie-aided information, each EN k ∈ M/{i} can compute τ u (r, a) ≥ max min{ai +1, N } = min max ai +1, N . (37)
i∈M i∈M
the transmitted signals {xj : j 6= to } and subtract them from u∗
Therefore, the minimum NULT τ (r) for all feasible task
the received signal. Thus, the received signal of EN k 6= i can ∗ ∗
assignment schemes is given by τ u (r) = min τ u (r, a). It
be rewritten as a
XN can be lower bounded by the optimal solution of the following
ȳk = yk − Hkj xj = Hkto xto + zk . (25) integer programming problem, 
j=1,6=to
P1 : min min max ai + 1, N
Since the message Wt is intended for some ENs in M/{i}, a i∈M
denoted as Rt , the ENs in Rt can decode it. By Fano’s M
X
inequality and (25), we have s.t. ai = N r
H(Wt |yk , W, Wr ) ≤ T u , k ∈ Rt . (26) i=1

Consider EN i, it can decode messages Wr intended for it. ai ∈ [0 : N ], i ∈ M. (38)

By Fano’s inequality, we have By relaxing the integer constraint ai ∈ [0 : N ] into a real-value
H(Wr |ŷi , W) ≤ |Wr |T u . (27) constraint 0 ≤ ai ≤ N , the optimal solution is still a lower
∗
bound of the minimum NULT τ u (r). Since the objective
Using genie-aided messages W and decoded messages Wr ,
is equivalent to minimizing the term max ai , the optimal
EN i can compute the transmitted signals {xj : j 6= to }, and ∀i∈M
subtract them from the received signal. We thus have solution can be obtained easily as a∗i = N r
M , ∀i ∈ M. Hence,
XN the minimum NULT is lower  bounded by 
ȳi = ŷi − Hij xj = Hito xto + ẑi . (28) u∗ Nr
τ (r) ≥ min + 1, N . (39)
j=1,6=to M
By reducing noise and multiplying the constructed signal ȳi The proof of the lower bound of NULT is thus completed.
at EN i by Hkto H−1
ito , we have Comparing (39) with (8) in Theorem 1, we see that they are
0
ȳik = Hkto H−1
ito ȳi = Hkto xto + ẑk , (29) the same. Thus, the proposed equal task assignment and task
0 uploading scheme in Section IV-1 is optimal.
where ẑk represents the reduced noise. It is seen that ȳik is a
degraded version of ȳk at EN k in Rt , so EN i must be able B. Lower bound and gap of NDLT
to decode the messages that ENs in Rt can decode. Thus, we
Let xi denote the signal transmitted by each EN i, and yj
have
the signal received at each user j, over the block length T d .
H(Wt |ŷi , W, Wr ) ≤ H(Wt |yk , W, Wr ) ≤ T u , i ∈ Rt . Consider the N computed results decoded by N users, we
(30) have the following chain of inequalities,
All the above changes including genie-aided information, f1 , · · · , W
NLe = H(W fN ) (40)
receiver cooperation, and noise reducing can only improve ca-
pacity. Therefore, we have the following chain of inequalities, f1 , · · ·, W
= I(W fN : y1 , · · ·, yN )+H(W
f1 , · · ·, W
fN |y1 , · · ·, yN )
(a) (41)
(|Wr | + |Wt |)L = H(Wr , Wt ) = H(Wr , Wt |W) (31)
(g) N
X
(b)
= I(Wr , Wt : ŷi |W) + H(Wr , Wt |ŷi , W) (32) ≤ I(W
f1 , · · · , W
fN : y1 , · · · , yN )+ fj |yj )
H(W (42)
(c) j=1
= I(Wr , Wt : ŷi |W) + H(Wr |ŷi , W) + H(Wt |ŷi , Wr , W) (h)
(33) ≤ I(x1 , x2 , · · · , xM : y1 , · · · , yN ) + N T d  (43)
(d) (i)
≤ I(Wr , Wt : ŷi |W) + |Wr |T u  + T u  (34) ≤ min{M, N }T d log Pd + N T d , (44)
(e) where (g) follows from H(W f1 , · · · , W
fN |y1 , · · · , yN ) ≤
≤ I(x1 , x2 , · · · , xai , xto : ŷi |W) + (|Wr | + 1)T u  (35) N
P N
P
(f ) H(Wfj |y1 , · · · , yN ) ≤ H(Wfj |yj ), (h) follows from
≤ T u log Pu + (|Wr | + 1)T u , (36) j=1 j=1
the data processing inequality and Fano’s inequality, and (i)
uses the capacity bound of the MISO broadcast channel with sets of column vectors of V̄j and V, denoted as V̄j and V,
a M -antenna transmitter and N single-antenna receivers. By respectively, are given as below
dividing on logLPd , and taking Pd → ∞ and  → 0, we have
e V̄j =
  
N  
τd ≥
Y
αtq
. (45)  H̄tq w : αtq∈ [0 : s−1]
min{M, N }  
∗ t∈M,q∈N,(t,q)/
∈{(t,k+1):k∈[(t−1)n:(tn−1)](modN )}
N
Hence, the minimum NDLT is lower bounded by τ d ≥ M . It | {z }
a total of sΓ columns
can be easily proved that the multiplicative gap between the (50)
achievable NDLT τad (r) in Theorem 1 and its lower bound is for ∀j ∈ N , and
N τ d (r) min{ MN
r }
+1, N
within 2 for M ∈ Z+ , i.e., τ da∗ (r) ≤ N/M ≤ 2. We V=
complete the proof of the lower bound and gap of NDLT in
  
 Y
αtq 
binary offloading.  H̄tq w : αtq∈[0 : s] .
Combining (39) and (45), an outer bound of the optimal
 
t∈M,q∈N,(t,q)/
∈{(t,k+1):k∈[(t−1)n:(tn−1)](modN )}

communication latency region can be given by the union of

| {z }
a total of (s+1)Γ columns
all latency pairs (τ u (r), τ d (r)) at all feasible computation load (51)
r’s satisfying   We then show that the desired signal streams received at
Nr N each receiver are linearly independent of each other and
τ u (r) ≥ + 1, N , τ d (r) ≥ (46)
M min{M, N } interference signal streams such that the desired streams
n P o
M
for ∀r ∈ r : i=1 ai = N r, ai ∈ [0 : N ], ∀i ∈ M . can be decoded by zero-forcing interferences. At any re-
ceiver i, the desired
 signal streams are beamformed  along
the nsΓ vectors of H̄i,i1V̄i1 H̄i,i2V̄i2 · · · H̄i,inV̄in , where
A PPENDIX
im = (i − 1)n + m (mod N ), m ∈ [n]. By condition (49),
A. Proof of Lemma 1 the interference streams at any receiver i from transmitter
j are aligned at the column vector space of V for j ∈
1) Achievable scheme: We use the partial interference
[N ]/ {k+1 : k ∈ [(i−1)n : in−1] (mod N )}. To decode the de-
alignment scheme with a us = nsΓ+(s+1)Γ symbol extension
sired nsΓ streams successfully, it suffices to show that the
over the original channel, where s ∈ N and Γ = M (N − n).
us ×us matrix
Specifically, each transmitter j encodes the task input message  
Wj into sΓ independent streams xlj , l ∈ [sΓ ], each beamformed Ai = H̄i,i1V̄i1 H̄i,i2V̄i2 · · · H̄i,inV̄in V (52)
along a us×1 column vector vjl . So the symbol X̄j transmitted has a full rank of us almost surely for ∀i ∈ M. By the
at transmitter j can be expressed as beamforming vectors in (50) and (51), we can observe that the
u elements in the l-th row of Ai have the following forms
s
XsΓ 
xlj vjl = V̄j Xj ,
 [
X̄j = (47) hi,im(l)
Y
(htq (l))αtq : αtq∈[0 :s−1],m∈[n]
l=1 
t∈M,q∈N,(t,q)∈{
/ (t,k+1):k∈[(t−1)n:(tn−1)](modN )}

Γ Γ
where Xj , (xlj )sl=1 is a s ×1 column vector, and V̄j = [vjl ]sl=1
Γ | {z }
a total of nsΓ elements
is a us ×sΓ matrix. Then, the received signal at EN i can be  
written as  Y 
βtq
N
X (htq (l)) : βtq∈ [0 : s] ,
Ȳi = H̄ij V̄j Xj + Z̄i , (48) 
t∈M,q∈N,(t,q)∈{
/ (t,k+1):k∈[(t−1)n:(tn−1)](modN )}

j=1
| {z }
a total of (s+1)Γ elements
(53)
where Ȳi and Z̄i represent the us symbol extension of the
where {hij (l)} are drawn independently from a continuous
received signal Yi and noise Zi , respectively. H̄ij is a us ×us
probability distribution. We observe from (53) that all the
diagonal matrix representing the us symbol extension of the
elements of Ai meet the two conditions of [17, Lemma 1].
channel, whose l-th diagonal element is hij (l).
Hence, the matrix Ai is a full-rank matrix for ∀i ∈ M. Taking
Next, we design the beamforming vectors such that each
s to infinity, the DoF for each receiver achieved by above
receiver i can decode the n desired signals {Xk+1 : k ∈ [(i−1)n : nsΓ n Nr
scheme is given by lims→+∞ nsΓ +(s+1) Γ = n+1 = N r+M .
(in−1)](mod N )} by zero-forcing the interferences. To align
the N −n interference signals at each receiver together in the Further, consider the basic scheme that N transmitters
space with dimension (s+1)Γ , beamforming vectors need to deliver their messages to the assigned receivers in the time
n r
satisfy the following conditions: division manner, which achieves a DoF of N =M for each
receiver. Therefore, the per-receiver DoF of the considered
span(H̄ijV̄j ) ≺ span(V), ∀i ∈ M, (49)
for ∀j ∈ N , (i, j) ∈
/ {(i, k+1) : k ∈ [(i−1)n : (in−1)](modN )},
interference-multicast channel
 N r withr
multicast group size r is
given by DoFru = max N r+M ,M .
where span(P) denotes the space spanned by the column
vectors of matrix P, and V is a us ×(s +1)Γ matrix. Now we 2) Converse Proof of Lemma 1: Since in Section V-A, we
need to design the column vectors of V̄[j] and V to satisfy have proved that the proposed task assignment and uploading
(49). Let w be a us×1 column vector w = (1, 1, · · · , 1)T . The scheme in Section IV-1 is information-theoretically optimal,
the per-receiver DoF of the considered uplink channel in (14) respectively, and are given as follows,
of Lemma 1 must also be optimal. V̄(i−1)n+k =
  
 Y
αqt 
 Ḡqt wk : αqt ∈ [0 : s−1] (56)
 
q∈N,t∈M,(q,t)6=((t−1)n+k,t)
B. Proof of Lemma 2 for ∀i ∈ M, ∀k ∈ [n], and
Uk =
  
1) Achievability: We show the achievable schemes in two  Y
αqt 
cases, r = 1 and r ≥ 2, respectively.  Ḡqt wk : αqt ∈ [0 : s] (57)
i) r = 1: By (13), the task output messages at each transmitter
 
t∈M,q∈N ,(q,t)6=((t−1)n+k,t)
i can be represented as W fj : j ∈ [(i−1)n+1 : in] . Let Γ = for ∀k ∈ [n].
M (N−1) and consider a us = sΓ+n(s+1)Γ symbol extension.
fj are encoded into sΓ independent streams In the following, we show that the desired signal streams are
Each message W
l Γ linearly independent with the interference signal streams, and
xj , l ∈ [s ], each beamformed along a us ×1 column vector
hence can be decoded by zero-forcing the interference. Con-
vjl , for ∀j ∈ N . Then, the signal transmitted at transmitter i
sider the signal vectors received at any receiver j = (i−1)n+k,
can be expressed as
i ∈ M, k ∈ [n]. By (56), the desired signal streams are
in sΓ in
X X X beamformed along the sΓ vectors of Ḡ(i−1)n+k,i V̄(i−1)n+k ,
X̄i = xlj vjl = V̄j Xj , (54) while the interference vectors are aligned at the column vector
j=(i−1)n+1 l=1 j=(i−1)n+1
Γ
spaces of Uk0 , ∀k 0 ∈ [n]. To decode the desired streams
where Xj = (xlj )sl=1 is a sΓ × 1 column vector and V̄j = successfully, it suffices to show that the us ×us matrix
Γ
[vjl ]sl=1 is a us ×sΓ matrix. The signal received at receiver j
 
Λj = Λ(i−1)n+k = Ḡ(i−1)n+k,iV̄(i−1)n+k U1 U2 · · · Un
can be expressed as (58)
M
X in
X is a full-rank matrix almost surely for ∀j ∈ N or ∀i ∈ M and
Ȳj = Ḡji V̄k Xk + Z̄j , (55) ∀k ∈ [n]. It is seen that the l-th row elements of Λj have the
i=1 k=(i−1)n+1
following

forms, 
where Ḡji is a us × us diagonal matrix representing the us  Y [
h(i−1)n+k,i (l) (gqt (l))αqtwk (l) : αqt∈[0 : s−1]
symbol extension of the channel, Ȳj and Z̄j represent the 
q∈N,t∈M,(q,t)6=((t−1)n+k,t)

us symbol extension of the received signal Yj and noise Zj ,  
respectively.
 Y 
βqt 0
(gqt (l)) wk0 (l) : βqt ∈ [0 : s], k ∈ [n] .
Next, we align the interferences at each receiver j such
 0

q∈N,t∈M,(q,t)6=((t−1)n+k ,t)

that the total dimension of the spaces spanned by the inter- (59)
ference vectors is n(s + 1)Γ . Then, the desired sΓ streams By (59), we have:
corresponding to the desired signal Xj can be decoded by 1) The product term in the l-th row of Uk contains wk (l) with
0
zero-forcing the interferences from an us = sΓ + n(s + 1)Γ - exponent 1, but do not contain wk0 (l), ∀k 6= k. Thus, all the
dimensional received signal vector. We ensure this by de- monomial elements in the l-th row of [U1 U2 · · · Un ] are
unique.

signing the beamforming vectors V̄j as follows, where the
message W fj desired by receiver j is at transmitter d j e ∈ M 2) The equations corresponding to G(i−1)n+k,i are not con-
n
by (13), tained in the interference alignment relations of (56) for Uk ,
span(Ḡji V̄(i−1)n+1 ) ⊂ span(U1 ) 
 so the monomial elements in the l-th row of Uk do not contain
 h(i−1)n+k,i , ∀i ∈ M. It means that all the monomial terms in
span(Ḡji V̄(i−1)n+2 ) ⊂ span(U2 ) 



 Ḡ(i−1)n+k,i V̄(i−1)n+k are different from those in Uk . They
.. 

 ∀j ∈ N , ∀i ∈ M,
 are also different from the monomial terms in Uk0 , ∀k 0 6= k,
.
due to wk (l).
span(Ḡji V̄(i−1)n+k ) ⊂ span(Uk ) 
j6=(i−1)n+k for ∀k ∈[n],
..


 Therefore, we can conclude that these us vectors in Λj

. 

 are independent, and hence Λj is a full-rank matrix. Taking

span(Ḡji V̄in ) ⊂ span(Un )
 s to infinity, the scheme achieves a per-receiver DoF of
sΓ 1 M
lims→+∞ sΓ +n(s+1) Γ = 1+n = N +M . Comparing it with
where Uk is a us × (s + 1)Γ matrix, ∀k ∈ [n]. Next, we 1
design {Vj } and {Uk } to satisfy above conditions. First, we the DoF of N achieved by TDMA, the per-receiver DoF
generate n us × 1 column vectors wk = (wkl )ul=1 s
, k ∈ [n]. of the considered
n downlink o channel for r = 1 is given by
d M 1
All elements of these n vectors are chosen i.i.d from some DoF1 = max N +M , N .
continuous distribution whose support lies between a finite ii) r ≥ 2: We first consider interference neutralization enabled
minimum value and a finite maximum value. Then, the sets by transmitter cooperation. Encode the task output message
of column vectors of V̄j and Uk are denoted as V̄j and Uk , fj into r independent streams xp , p ∈ [r]. For better illus-
W j
tration, each stream xpj is given an index (p−1)N +j. There [6] V. S. Annapureddy, A. E. Gamal, and V. V. Veeravalli, “Degrees of free-
are a total of N r (or M n) different streams corresponding to dom of interference channels with CoMP transmission and reception,”
IEEE Trans. Inf. Theory, vol. 58, no. 9, pp. 5740–5760, Sep. 2012.
all N messages. Based on the index order, these N r different [7] V. R. Cadambe and S. A. Jafar, “Interference alignment and degrees of
streams can be divided into N groups, each group with r freedom of the K-user interference channel,” IEEE Trans. Inf. Theory,
different streams, where the k-th group is given by vol. 54, no. 8, pp. 3425–3441, Aug. 2008.
[8] S. Li, M. A. Maddah-Ali, Q. Yu, and A. S. Avestimehr, “A fundamental
Qk = xpj : (p−1)N +j ∈ [(k−1)r+1 : kr] , k ∈ [N ].

tradeoff between computation and communication in distributed com-
(60) puting,” IEEE Trans. Inf. Theory, vol. PP, no. 99, pp. 1–1, 2017.
[9] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran,
Since each message exists at r different transmitters, each “Speeding up distributed machine learning using codes,” IEEE Trans.
stream is also owned by r different transmitters. Each group Inf. Theory, vol. PP, no. 99, pp. 1–1, 2017.
of streams is downloaded in the time division manner. The [10] D. Wang, G. Joshi, and G. Wornell, “Efficient task replication for fast
response times in parallel computation,” in Proc. ACM SIGMETRICS,
downlink channel formed by transmitting each group of r 2014.
streams can be treated as a MISO broadcast channel with [11] I. Wang and D. N. C. Tse, “Interference mitigation through limited
perfect transmitter cooperation, whose sum DoF is r [6], [18] transmitter cooperation,” IEEE Trans. Inf. Theory, vol. 57, no. 5, pp.
2941–2965, May 2011.
achieved by using interference neutralization. Thus, a DoF of [12] K. Li, M. Tao, and Z. Chen, “Exploiting computation replication in
r
N is obtained for each receiver in the r ≥ 2 case. multi-user multi-server mobile edge computing networks,” in Proc. IEEE
Then, we apply asymptotic interference alignment scheme Global Commun. Conf. (GLOBECOM), Dec. 2018.
N [13] A. Sengupta, R. Tandon, and O. Simeone, “Fog-aided wireless networks
in the r = 1 case. Since M = n1 , the messages at each for content delivery: Fundamental latency tradeoffs,” IEEE Trans. Inf.

transmitter i are Wk : k ∈ [(i − 1)n1 + 1 : in1 ] for r = 1
f Theory, vol. 63, no. 10, pp. 6650–6678, Oct. 2017.

fk+1 : k ∈ [(i−1)rn1 : (irn1 −1)](mod N ) for r ≥ 2. [14] F. Xu, M. Tao, and K. Liu, “Fundamental tradeoff between storage and
and W latency in cache-aided wireless interference networks,” IEEE Trans. Inf.
In r ≥ 2 case, we can let each transmitter only transmit the Theory, vol. 63, no. 11, pp. 7464–7491, Nov. 2017.
n1 messages among the total rn1 messages, and different [15] J. Hachem, U. Niesen, and S. Diggavi, “Degrees of freedom of cache-
aided wireless interference networks,” IEEE Trans. Inf. Theory, pp. 1–1,
transmitters transmit non-overlapped messages. By doing so, 2018.
we construct a downlink channel with the same information [16] A. M. Girgis, Ö. Erçetin, M. Nafie, and T. A. ElBatt, “Degrees of
flow as r =1 case. Utilizing the alignment scheme in r = 1 freedom of interference networks with transmitter-side caches,” CoRR,
vol. abs/1712.05957, 2017. [Online]. Available: http://arxiv.org/abs/
case, we thus obtain a per-receiver DoF of NM+M nfor r≥ 2 case.
o 1712.05957
Comparing above two schemes, a Dof of max NM r
+M , N is [17] V. R. Cadambe, S. A. Jafar, “Interference alignment and the degrees
of freedom of wireless X networks,” IEEE Trans. Inf. Theory, vol. 55,
obtained. no. 9, pp. 3893–3908, Sep. 2009.
Summarizing the per-receiver DoF for r = 1 and r ≥ 2 cases, [18] T. Gou and S. A. Jafar, “Degrees of freedom of the k user mtimesn
we thus prove Lemma 2. mimo interference channel,” IEEE Trans. Inf. Theory, vol. 56, no. 12,
pp. 6040–6057, Dec 2010.
2) Converse proof of Lemma 2: For the upper bound, we [19] H. Weingarten, Y. Steinberg, and S. S. Shamai, “The capacity region
assume that each transmitter has known all N task output of the gaussian multiple-input multiple-output broadcast channel,” IEEE
messages so that the full transmitter cooperation among M Trans. Inf. Theory, vol. 52, no. 9, pp. 3936–3964, Sep. 2006.
transmitters is enabled. This assumption can only improve the
channel capacity. We thus construct a virtual MISO broadcast
channel with N single-antenna receivers and a M -antenna
transmitter, whose optimal sum DoF is min{M, N } [19]. The
capacity of the considered cooperative interference channel
cannot exceed that of this virtual MISO broadcast channel.
∗
Hence, the optimal per-receiver DoF DoFrd is upper bounded
}
by min{M,N
N . The gap between this upper bound and the
∗
DoFrd
achievable lower bound in (16) satisfies DoFrd
≤ 2.
R EFERENCES
[1] S. Barbarossa, S. Sardellitti, and P. D. Lorenzo, “Communicating while
computing: Distributed mobile cloud computing over 5G heterogeneous
networks,” IEEE Signal Process. Mag., vol. 31, no. 6, pp. 45–55, Nov.
2014.
[2] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey
on mobile edge computing: The communication perspective,” IEEE
Commun. Surveys Tuts., vol. 19, no. 4, pp. 2322–2358, 4th Quart. 2017.
[3] S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “Communication-aware
computing for edge processing,” in Proc. IEEE Int. Symp. Inf. Theory
(ISIT), Jun. 2017, pp. 2885–2889.
[4] J. Liu, Y. Mao, J. Zhang, and K. B. Letaief, “Delay-optimal computation
task scheduling for mobile-edge computing systems,” in Proc. IEEE Int.
Symp. Inf. Theory (ISIT), Jul. 2016, pp. 1451–1455.
[5] A. Al-Shuwaili and O. Simeone, “Energy-efficient resource allocation
for mobile edge computing-based augmented reality applications,” IEEE
Wireless Commun. Letters, vol. 6, no. 3, pp. 398–401, Jun. 2017.