Coded Cooperative Computation for Internet of Things
Yasaman Keshtkarjahromi

Hulya Seferoglu

University of Illinois at Chicago
ykesht2@uic.edu

University of Illinois at Chicago
hulya@uic.edu

arXiv:1801.04357v1 [cs.DC] 13 Jan 2018

ABSTRACT
Cooperative computation is a promising approach for localized data
processing for Internet of Things (IoT), where computationally intensive tasks in a device could be divided into sub-tasks, and offloaded to other devices or servers in close proximity. However,
exploiting the potential of cooperative computation is challenging
mainly due to the heterogeneous nature of IoT devices. Indeed, IoT
devices may have different and time-varying computing power and
energy resources, and could be mobile.
Coded computation, which advocates mixing data in sub-tasks
by employing erasure codes and offloading these sub-tasks to other
devices for computation, is recently gaining interest, thanks to its
higher reliability, smaller delay, and lower communication costs. In
this paper, we develop a coded cooperative computation framework,
which we name Computation Control Protocol (CCP), by taking
into account heterogeneous computing power and energy resources
of IoT devices. CCP dynamically allocates sub-tasks to helpers and
is adaptive to time-varying resources. We show that (i) CCP improves task completion delay significantly as compared to baselines,
(ii) task completion delay of CCP is very close to its theoretical
characterization, and (iii) the efficiency of CCP in terms of resource
utilization is higher than 99%, which is significant.

KEYWORDS
Coded computation, edge computing, Internet of Things (IoT).

1

INTRODUCTION

Data processing is crucial for many Internet of Things (IoT) applications, but it could be computationally intensive and not doable
if IoT devices operate individually. One of the promising solutions
to handle computationally intensive tasks is computation offloading, which advocates offloading tasks from IoT devices to remote
servers or cloud. Yet, offloading tasks to remote servers or cloud
could be luxury that cannot be afforded in IoT applications where
connectivity to remote servers can be lost or compromised, which
makes localized processing crucial.
Cooperative computation is a promising approach for localized
data processing for IoT, where computationally intensive tasks in a
device (collector device) could be offloaded to other devices (helpers)
in close proximity as illustrated in Fig. 1. These devices could be
other IoT or mobile devices, local servers, or fog at the edge of
the network [1], [2]. However, exploiting the potential of cooperative computation is challenging mainly due to the heterogeneous
nature of of the devices at the edge. Indeed, these devices may have
different and time-varying computing power and energy resources,
and could be mobile. Thus, our goal is to develop a dynamic and
adaptive cooperative computation framework for IoT applications
by taking into account the heterogeneity of resources at the edge of
the network.

A1, x Helper 1

Helper 1

A, x

y=Ax
Helper 2

Collector

A2, x Helper 2
Collector

.
.
.

.
.
.

Helper N

(a) Offloading sub-tasks from the
collector to helpers

AN, x Helper N

(b) Helpers send computed sub-tasks back
to the collector

Figure 1: Cooperative computation to compute y = Ax. (a) Matrix A is divided into the sub-matrices A1 , A2 , ..., A N . Each submatrix along with the vector x is transmitted from the collector
to one of the helpers. (b) Each helper computes the multiplication of its received sub-matrix with vector x and sends the
computed value back to the collector.

We focus on the computation of linear functions. In particular,
we assume that the collector’s data is represented by a large matrix
A and it wishes to compute the product y = Ax, for a given vector
x, Fig. 1. In fact, matrix multiplication forms the atomic function
computed over many iterations of several signal processing, machine learning, and optimization algorithms, such as gradient descent based algorithms, classification algorithms, etc. [3–6].
In cooperative computation setup, matrix A is divided into submatrices A1 , A2 , ..., A N and each sub-matrix along with the vector
x is transmitted from the collector to one of the helpers, Fig. 1(a).
Helper n computes An x, and transmits the computed result back to
the collector, Fig. 1(b), who can process all returned computations
to obtain the result of its original task; i.e., the calculation of y = Ax.
Coding in computation systems is recently gaining interest in
large scale computing environments, and it advocates higher reliability and smaller delay [3]. In particular, coded computation
(e.g., by employing erasure codes) mixes data in sub-tasks and offloads these coded sub-tasks for computation, which improves delay
and reliability. The following canonical example inspired from [3]
demonstrates the effectiveness of coded computation.
E XAMPLE 1. Let us consider that a collector device would like
to calculate y = Ax with the help of three helper devices (helper
1, helper 2, and helper 3), where the number of rows in A is 6. Let
us assume that each helper has a different runtime; helper 1 computes each row in 1 unit time, while the second and the third helpers
require 2 and 10 units of time for computing one row, respectively.
Assuming that these runtimes are random and not known a priori,
one may divide A to three sub-matrices; A1 , A2 , and A3 ; each with 2
rows. Thus, the completion time of these sub-matrices becomes 2, 4,
and 20 at helpers 1, 2, and 3, respectively. Since the collector should

delay analysis of CCP for (i) finite number of tasks, (ii) on
the average for large number of tasks, and (iii) when the runtime of sub-tasks at helpers follows shifted exponential distribution.
• We evaluate CCP and show that (i) CCP improves task completion delay significantly as compared to baselines, (ii) the
efficiency of CCP in terms of resource utilization is higher
than 99%, and (iii) task completion delay of CCP is very close
to its theoretical characterization.
The structure of the rest of this paper is as follows. Section II
presents the system model. Section III presents our cooperative computation algorithm, CCP. Sections IV and V provide the efficiency
and task completion delay characterization of CCP. Section VI presents
simulation results. Section VII presents related work. Section VIII
concludes the paper.

receive all the calculated sub-matrices to compute its original task;
i.e., y = Ax, the total computing time becomes max(2, 4, 20) = 20.
As seen, helper 3 becomes a bottleneck in this scenario, which
can be addressed using coding. In particular, A could be divided
into two sub-matrices A1 and A2 ; each with 3 rows. Then, A1 and
A2 could be offloaded to helpers 1 and 2, and A1 + A2 could be
offloaded to helper 3. In this setup, runtimes become 3, 6, and 30
at helpers 1, 2, and 3, respectively. However, since the collector
requires reply from only two helpers to compute y = Ax thanks to
coding, the total task completion delay becomes max(3, 6) = 6. As
seen, the task completion delay reduces to 6 from 20 with the help
of coding.

The above example demonstrates the benefit of coding for cooperative computation. However, assigning sub-tasks with equal sizes
to all helpers, without considering their heterogeneous resources is
inefficient. Let us consider the same setup in Example 1. If A1 with
4 rows and A2 with 2 rows are offloaded to helper 1 and helper
2, respectively, and helper 3 is not used, the task completion delay becomes max(4, 4) = 4, which is the smallest possible delay in
this example. Furthermore, the resources of helper 3 are not wasted,
which is another advantage of taking into account the heterogeneity
as compared to the above example. As seen, it is crucial to divide
and offload matrix A to helpers by taking into account the heterogeneity of resources.
Indeed, a code design mechanism under such a heterogeneous
setup is developed in [7], where matrix A is divided, coded, and offloaded to helpers by taking into account heterogeneity of resources.
However, available resources at helpers are generally not known by
the collector a priori and may vary over time, which is not taken
into account in [7]. For example, the runtime of helper 1 in Example 1 may increase from 1 to 20 while computing (e.g., it may start
running another computationally intensive task), which would increase the total task completion delay. Thus, it is crucial to design
a coded cooperation framework, which is dynamic and adaptive to
heterogeneous and time-varying resources, which is the goal of this
paper.
In this paper, we design a coded cooperation framework for IoT
devices. In particular, we design a Computation Control Protocol
(CCP), which packetizes rows of matrix A into packets, codes these
packets using Fountain codes, and determines how many coded
packets each helper should compute dynamically over time. We
provide theoretical analysis of CCP’s efficiency and runtime, and
evaluate its performance via simulations as compared to [7]. The
following are the key contributions of this work:

2

• We develop a coded cooperative computation protocol (CCP)
based on Automatic Repeat reQuest (ARQ) mechanism. In
particular, a collector device offloads coded sub-tasks to helpers
gradually, and receives Acknowledgment (ACK) after each
sub-task is computed. Depending on the time difference between offloading a sub-task to a helper and its ACK, the
collector estimates the runtime of the helpers, and offloads
more/less tasks accordingly. This makes CCP dynamic and
adaptive to heterogeneous and time-varying resources at helpers.
• We analyze the efficiency of CCP in each helper, where the
efficiency metric represents the effective utilization of resources at each helper. We also provide the task completion
2

SYSTEM MODEL

We consider a setup, where the collector device offloads its task to
helpers in the set N (where N = |N |) via device-to-device (D2D)
links such as Wi-Fi Direct and/or Bluetooth. In this setup, all the
devices could potentially be mobile, so the encounter time of the
collector with helpers varies over time. I.e., the collector can connect to less than N helpers at a time.
As we described in Section 1, we focus on computation of linear
functions; i.e., the collector wishes to compute y = Ax where A =
(ai, j ) ∈ RR×R , and x = (xi, j ) ∈ RR×1 . Our goal is to determine
sub-matrix An = (ai, j ) ∈ Rr n ×R that will be offloaded to helper n,
where r n is an integer.
We packetize each row of A into a packet and create R packets; ρ 1 , ρ 2 , . . . , ρ R . These packets are coded using Fountain codes
[8], [9] to ν 1, ν 2, . . . , ν R+K packets, where K is the coding overhead.
Fountain codes are ideal in our dynamic coded cooperation setup
thanks to their rateless property, low encoding and decoding complexity, and low overhead. In particular, the encoding and decoding
complexity of Fountain codes could be as low as O(R log(R)) for LT
codes and O(R) for Raptor codes, and the overhead, i.e., K, could
be as low as 5% [10].1
Let T xn,i be the time that the ith coded packet pn,i ∈ {ν 1, ν 2 ,
. . . , ν R+K } is transmitted from the collector to helper n, Tcn,i be the
time that helper n finishes computing pn,i , and Tr n,i be the time that
the computed packet (i.e., by abusing the notation pn,i x) is received
by the collector from helper n. The transmission time of the first
packet, i.e., pn, 1 , is 0, i.e., T xn, 1 = 0, ∀n ∈ N .
In this setup, the collector device offloads coded packets gradually to helpers, and receives two ACKs for each packet; one confirming the receipt of the packet by the helper, and the second one (piggybacked to the computed packet pn,i x) showing that the packet is
computed by the helper. Inspired by ARQ mechanisms [12], the collector transmits more / less coded packets based on the frequency of
the received ACKs. In particular, we define the transmission time interval TT In,i as the time interval between sending two consecutive
1 Note

that we do not use network coding in our work as its decoding complexity is
too high [11], which introduces too much computation overhead at the collector which
obsoletes the computation offloading benefit. Furthermore, we do not use maximum
distance separable (MDS) codes in our work as it requires a priori task allocation (due
to its block coding nature) and not suitable for the dynamic and adaptive framework
that we would like to develop.

Now that we know that TT In,i = βn,i should be satisfied for
the best system efficiency and smallest task completion delay, the
collector can set TT In,i to βn,i . However, the collector does not
know βn,i a priori as it is the computation runtime of packet pn,i
at helper n (e.g., it may follow the shifted exponential distribution
in (1)). Thus, we should determine TT In,i without explicit knowledge of βn,i . Our approach in CCP is to estimate βn,i using computation times of previous packets. In particular, our goal is to set
TTTn,i to E[βn,i ].2 The crucial question is how to estimate E[βn,i ],
which is challenging as the collector only has the transmission times
of packets and reception times of ACKs. Therefore, we define and
use residual time XTTn,i and round trip times of computed packets;
data to determine E[β ]. Next, we will first show how we charRTTn,i
n,i
data , and then present how we determine
acterize XTTn,i and RTTn,i

packets; pn,i and pn,i +1 to helper n by the collector. The goal of
our mechanism is to determine the best TT In,i that reduces the task
completion delay and increases helper efficiency (i.e., exploiting the
full potential of the helpers while not overloading them).
Each transmitted packet pn,i experiences transmission delay between the collector and helper n as well as computing delay at
helper n. Also, ACKs and the computed packet pn,i x experience
transmission delay while transmitted from helper n to the collector.
Our CCP algorithm is compatible with any delay model and distribution, but for the sake of analyzing the efficiency and completion
time of CCP, we assume that transmission delays are constant (we
relax this constraint in simulations), and computing time of pn,i at
helper n is βn,i and follows shifted exponential distribution, i.e., :
F βn, i (t) = Pr (βn,i < t) = 1 − e −µ n (t −an ) ,

(1)

data .
E[βn,i ] using XTTn,i and RTTn,i
Characterization of XTTn,i . The collector side has the knowledge of the transmission time T xn,i of packet pn,i , and time Tr n,i
that the computed packet pn,i x is received. Thus, the time between
transmitting a packet and receiving its computed value defined as
Ttn,i = Tr n,i −T xn,i can be calculated at the collector. On the other
hand, to better utilize resources at helper n, the collector should
offload a new packet before (or immediately after) receiving the
computed value of the previous packet, i.e., the following condition
should be satisfied: TT In,i ≤ Ttn,i . Thus, we can write TT In,i =
Ttn,i − XTTn,i +1 , where XTTn,i +1 is the residual time that the collector measures in our CCP setup and is equal to:

where an represents the minimum time required for computing a
packet by helper n; i.e., βn,i > an , and µ n represents the speed of
the computation at helper n; i.e., larger µ n corresponds to smaller
βn,i . As helpers are heterogeneous, µ n and an vary across helpers.
We use shifted exponential distribution as a runtime model as it is a
good model for computation delay [3] and [7].
We note that runtime βn,i of packet pn,i represents energy/battery
level and mobility of helpers as well as their computing power. For
example, if a helper has limited energy, it can delay computation of
the offloaded packets, so the collector will choose this helper less
likely for the upcoming packet offloads. Similarly, if a helper is mobile and moves out of the transmission range of the collector, the
runtime of packets increases, so again the collector will not select
this helper for upcoming packet offloads.
Finally, we assume that helpers are willing to cooperate with the
collector. I.e., creating incentive mechanisms are out of scope of this
paper, and our work could be complemented with existing incentive
mechanisms [13].

3

XTTn,i +1 = Tr n,i − T xn,i +1 .

(2)

data . We define RTT data as the round trip
Characterization of RTTn,i
n,i
data
time (RTT) of packet i sent to helper n. More precisely, RTTn,i
is equal to transmission delay of packet pn,i from the collector
to helper n and transmission delay of the calculated packet pn,i x
data is round trip time,
from helper n to the collector. Although RTTn,i
it can not be directly measured in the collector, as the collector
only knows the time period between sending a packet and receiving the computed packet, which is equal to the sum of transmission
data using
and computing delay. Thus, in CCP, we calculate RTTn,i
ack
RTTn,i , which is the time period between sending packet pn,i and
receiving its ACK at the collector. Fig. 2(b) demonstrates the difdata and RTT ack . Note that RTT ack can be
ference between RTTn,i
n,i
n,i

COMPUTATION CONTROL PROTOCOL
(CCP)

In this section, we design Computation Control Protocol (CCP). We
consider the system setup in Fig. 1, where the collector connects
to N helpers. The collector estimates each helper’s state (i.e., how
fast the helper computes) to determine how fast it should offload its
packets. In particular, the goal of CCP is to determine TT In,i , which
is the time interval between transmission of the two consecutive
packets of pn,i and pn,i +1.
TT In,i in an ideal scenario. Let us first consider the ideal scenario, Fig. 2(a). In this case TT In,i should be equal to βn,i . Indeed,
if TT In,i > βn,i , helper n stays idle, which reduces the efficient utilization of resources. On the other hand, if TT In,i < βn,i , packets
are queued at helper n. This congested scenario is not ideal, because
the resources of helper n may vary over time, e.g., its computing
power may reduce if it starts running another application, or it may
move away. In that case the queued packets should be re-offloaded
to other helpers, which increases the task completion delay. Note
that the collector can create new coded packets and offload them
to other helpers if one helper moves away, which reduces the task
completion delay. However, this solution is also not ideal as some
helpers can be overloaded, which wastes resources.

ack
directly measured by employing ACKs. We can represent RTTn,i
up
down
ack
as RTTn,i = B x /Cn,i + B ack /Cn,i , where B x is the size of the
up
transmitted packet, B ack is the size of the ACK packet, and Cn,i and
down are the uplink (from the collector to helper n) and downlink
Cn,i
(from helper n to the collector) transmission rates experienced by
packet pn,i and its ACK.
data is characterized as RTT data = B /C up +
Note that RTTn,i
x n,i
n,i
down , where B is the size of the computed packet; p x. AsB r /Cn,i
r
n,i
suming that uplink and downlink transmission rates are the same,
data as:
which is likely in IoT setup, we can obtain RTTn,i
data
RTTn,i
=
2 We

3

B x + Br
ack
RTTn,i
.
B x + B ack

show in Section 5.2 that setting T T Tn, i = E[β n, i ] is optimal.

(3)

Collector

Helper n

Collector

ࢀ࢞࢔ǡ࢏ି૚
ࢀࢀࡵ࢔ǡ࢏ି૚

ࢀ࢞࢔ǡ࢏

ࢄࢀࢀ࢔ǡ࢏ = ࡾࢀࢀ࢔ࢊࢇ࢚ࢇ
ࢀ࢘࢔ǡ࢏ି૚
ࢀ࢘࢔ǡ࢏

ࢀࢉ࢔ǡ࢏ି૚
ࢀࢉ࢔ǡ࢏

(a) Ideal case

ࢼ࢔ǡ࢏ି૚
ࢼ࢔ǡ࢏

ࢀ࢞࢔ǡ࢏ି૚

ࡾࢀࢀ࢔ࢊࢇ࢚ࢇ

ࡾࢀࢀࢇࢉ࢑
࢔

ࢀ࢞࢏࢔

ࢀ࢘࢔ǡ࢏ି૚

(b)

Helper n

Collector

ࢀ࢞࢔ǡ࢏ି૚

࡭ࢉ࢑࢔ǡ࢏ି૚

ࢼ࢔ǡ࢏ି૚

࡭ࢉ࢑࢔ǡ࢏

ࢼ࢔ǡ࢏

ࢀ࢘࢔ǡ࢏

RT Tndata

Collector

Helper n

through an example

ࢀࢀࡵ࢔ǡ࢏ି૚
ࢄࢀࢀ࢔ǡ࢏

ࢀ࢞࢔ǡ࢏

ࢀ࢘࢔ǡ࢏ି૚
ࢀ࢘࢔ǡ࢏

Helper n

ࢀ࢞࢔ǡ࢏ି૚

ࢀࢉ࢔ǡ࢏ି૚
ࢀࢉ࢔ǡ࢏

(c) Underutilized case

ࢼ࢔ǡ࢏ି૚
ࢀ࢛࢔ǡ࢏

ࢼ࢔ǡ࢏

ࢀࢀࡵ࢔ǡ࢏ି૚

ࢄࢀࢀ࢔ǡ࢏

ࢀ࢞࢔ǡ࢏

ࢀ࢘࢔ǡ࢏ି૚

ࢀ࢕࢔ǡ࢏

ࢀ࢘࢔ǡ࢏

ࢀࢉ࢔ǡ࢏ି૚
ࢀࢉ࢔ǡ࢏

ࢼ࢔ǡ࢏ି૚
ࢼ࢔ǡ࢏

(d) Congested case

Figure 2: Different states of the system. (a) Ideal case. (b) Demonstrating RTTndata through an example. (c) Underutilized case. (d)
Congested case.
ack can be directly measured by the colAs we discussed earlier RTTn,i

the ideal and congested cases. Note that the congested and ideal
cases occur when packet pn,i is received at the helper meanwhile
or right after the helper computes packet pn,i −1x. In this setup,
since there is no under-utilization, Tun,i is equal to 0. On the other
hand, XTTn,i < RTTndata in the underutilized case scenario. As
seen in Fig. 2(c), underutilized case occurs when packet pn,i is
received at the helper after a while that the helper finished computing packet pn,i −1x. In this setup, RTTndata − XTTn,i is the duration that helper n is underutilized before calculating pn,i x, i.e.,
Tun,i = RTTndata − XTTn,i . Therefore, Tun is updated after pn,i x is
received by the collector as the following:

data .
RTTn,i

lector and used in (3) to determine
Next, we characterize
the average value of data round trip time of helper n, i.e., RTTndata
as exponential weighted moving averages of per packet round trip
data .
time; RTTn,i
data
RTTndata = αRTTn,i
+ (1 − α)RTTndata ,

(4)

where α is a weight satisfying 0 < α < 1.
Now that we characterized XTTn,i and RTTndata and discussed
how we can measure these parameters at the collector, we will explain how we will use these parameters to calculate E[βn,i ].
Calculation of E[βn,i ]. We formulate E[βn,i ] as follows:

Tun = Tun + max{0, RTTndata − XTTn,i }.

Tcn,i − Tun
,
(5)
E[βn,i ] =
mn
where Tcn,i is the time that helper n finishes computing pn,i x, Tun
is the estimate made at the collector about the total (cumulative)
time that helper n is underutilized, and m n is the number of packets that helper n processed until (and including) packet pn,i . Since
Tcn,i is the time instance that helper n finishes computing packet
pn,i x, and Tun is the cumulative time that helper n is underutilized,
their difference gives us the total time that helper n has been busy
since the starting time. Total busy time of helper n, i.e., Tcn,i −Tun
is normalized by the total number of processed packets m n to determine E[βn,i ]. Next, we characterize Tcn,i and Tun in terms of
XTTn,i and RTTndata .
The collector estimates Tcn,i as follows

(7)

As seen, Tun is determined using XTTn,i .
Determining TT In,i in practice. As we mentioned earlier, our
goal was to set TT In,i to E[βn,i ]. However, in order to efficiently
utilize resources at helper n, the collector should send a packet before or immediately after receiving the computed value of the previous packet, i.e., TT In,i ≤ Ttn,i = Tr n,i − T xn,i should be satisfied.
Therefore, if the calculated E[βn,i ] is larger than Tr n,i −T xn,i , then
we set TT In,i as Tr n,i − T xn,i to satisfy this condition. Otherwise,
we set TT In,i to E[βn,i ]. Therefore, we have:
TT In,i = min(Tr n,i − T xn,i , E[βn,i ]).

(8)

CCP in a nutshell. The main goal of CCP is to determine packet
transmission intervals; TT In,i as described in (8) and summarized
in Algorithm 1. Note that Algorithm 1 has also a timeout value defined in line 14, which is needed for unresponsive helpers. If helper
n is not responsive, TT In,i is quickly increased as shown in line 13
so that fewer and fewer packets could be offloaded to that helper.
In particular, CCP doubles TT In,i when the timeout for receiving
ACK occurs. This is inspired by additive increase multiplicative decrease strategy of TCP, where the number of transmitted packets are
halved to backoff quickly when the system is not responding.
After TT In,i is updated when a transmitted packet is ACKed or
timeout occurs, this interval is used to determine the transmission
times of the next coded packets. In particular, coded packets from
the set {ν 1, ν 2 , . . . , ν R+K } are transmitted one by one to all helpers
with intervals TT In,i until (i) TT In,i is updated with a new ACK
packet or timeout occurs, or (ii) the collector collects R + K computed packets.

Br
RTTndata ,
(6)
B x + Br
where Tr n,i is the time that the computed packet pn,i x is received
r
by the collector from helper n, so it is known by the collector. BxB+B
r
Tcn,i = Tr n,i −

RTTndata is the backward trip time estimated by the collector using
(4) and packet sizes.
The next step is to characterize Tun , which is the estimate made
at the collector about the total (cumulative) time that helper n is
underutilized. Tun is the summation of per packet underutilization
time, which is shown by Tun,i . In particular, Tun,i is defined as
the time period that the helper is idle between computing packet
pn,i −1x and pn,i x. In order to calculate Tun,i , we should determine the state of the system, i.e., if in the ideal, underutilized, or
congested case, Fig. 2. As shown in Fig. 2, XTTn,i ≥ RTTndata in
4

Algorithm 1 CCP algorithm at the collector
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

value of the duration that helper n is underutilized per packet, is
characterized as:



data

 (e µ1 ) 1 − e (µ n RT Tn ) + RTTndata , if RTTndata < µ1

n
n
E[Tun,i ] =

otherwise.
 (e µ1n ) ,

(11)

Initialize: Tun = 0, T xn, 1 = 0, XTTn, 1 = 0, TOn = ∞, ∀n ∈ N .
while R + K calculated packets have not been received do
if An ACK for successful transmission of packet pn,i is received from helper n then
Calculate RTTndata according to (4).
if Calculated packet pn,i x and the corresponding computation ACK is received before timeout expires then
if i == 1 then
ack
x
Tun = Bx B+B
RTTn,i
ack
else
XTTn,i = Tr n,i −1 − T xn,i .
Calculate Tun according to (7)
Calculate TT In,i according to (5) and (8)
else
TT In,i = 2 × TT In,i .
Update timeout as TOn = 2(TT In,i + RTTndata )

Proof: The proof is provided in Appendix A.

We define the efficiency of helper n as γn = 1 − E[Tun,i ]/E[βn,i ].
Note that E[Tun,i ] is the expected time that helper is underutilized
per packet, while E[βn,i ] is the expected runtime duration, i.e., the
expected time that helper n works per packet. Thus, E[Tun,i ]/E[βn,i ]
becomes the under-utilization ratio of helper n, so γn = 1−E[Tun,i ]/
E[βn,i ] becomes efficiency. From (11) and replacing E[βn,i ] with
an + 1/µ n 4 , γn is expressed as the following:

γn =

4

EFFICIENCY OF CCP

Tun,i =

















1+an µ n −µ n RT Tndata −1/e +exp(µ n RT Tndata −1)
,
1+an µ n
data
if RTTn < 1/µ n
e (1+an µ n )−1
,
otherwise.
e (1+an µ n )

(12)

We show through simulations (in Section 6) that, (i) γn in (12) is
larger than 99%, and (ii) CCP’s efficiency is even larger than γn as
γn in (12) is the average analysis.

In this section, we analyze the efficiency of CCP in each helper,
where the efficiency represents the effective utilization of resources
at each helper. For example, if helper n is underutilized, its efficiency reduces.
First, we characterize the time Tun,i that helper n is underutilized before computing packet pn,i x.3 As seen in Fig. 2(c), helper n
is underutilized before computing packet pn,i x, if TT In,i −1, calculated according to (8), is larger than βn,i −1 . In this case, the helper
is underutilized for the time period equal to the difference between
TT In,i −1 and βn,i −1 , i.e., Tun,i = max(TT In,i −1 − βn,i −1, 0). By
replacing TT In,i −1 from (8), we have:


















5 TASK COMPLETION DELAY OF CCP
In this section, we provide task completion delay analysis of CCP.
First, we characterize the delay performance of CCP when the number of tasks are finite. Then, we provide average delay analysis for
large number of tasks. This analysis holds for any runtime distribution. Finally, we calculate the task completion delay of CCP in a
closed form when runtimes follow shifted exponential distribution.

E[βn,i ] − βn,i −1,
if Tr n,i −1 − T xn,i −1 > E[βn,i ] > βn,i −1
Tr n,i −1 − T xn,i −1 − βn,i −1,
if E[βn,i ] > Tr n,i −1 − T xn,i −1 > βn,i −1
0,
otherwise.
(9)

5.1

Finite Number of Tasks

In this section, we analyze the delay performance of CCP as compared to the best and naive task allocation algorithms for finite number of tasks. The best algorithm knows the runtimes of helpers βn,i
a priori, and allocates tasks accordingly. Although the best algorithm is not practical, it is a nice baseline to understand the performance of CCP. The task completion delay of the best algorithm
Tbest is:

Tr n,i −1 − T xn,i −1 in the above equation is equal to the time period
between sending packet pn,i −1 and receiving its computed value
pn,i −1x, which is the sum of computing delay, βn,i −1 and an RTT
of sending a packet; RTTndata . Therefore, (9) is expressed as

Tbest = max
n ∈N



RTTndata ,
if 0 < βn,i −1 < E[βn,i ] − RTTndata



Tun,i = E[βn,i ] − βn,i −1, if E[βn,i ] − RTTndata < βn,i −1 < E[βn,i ]


 0,
otherwise.

(10)



RTTndata

+

best
rÕ
n

i =1


βn,i ,

(13)



Ín
βn,i . In (13),
where r nbest = argminr n maxn ∈N RTTndata + ri =1
RTTndata comes from the fact that there is delay for sending the first
packet pn, 1 , and receiving the last computed packet, pn,r n x even if
βn,i ’s are known a priori.
There is a gap between CCP and the best algorithm as CCP is
practical, while the best algorithm is not. Next, we characterize the
gap between CCP and the best algorithm. The task completion delay

The next theorem characterizes the expected value of underutilization time E[Tun,i ].

T HEOREM 1. Assume that the runtime of each packet, i.e., βn,i
is a random variable according to an i.i.d shifted exponential distribution with mean an + 1/µ n and shifted value of an . The expected

4 Note that (5) calculates the expected runtime for our CCP algorithm, where the helpers
3 Note

can process packets according to any runtime distribution. However, in this section, for
the sake of analysis, we assume that runtime distribution is shifted exponential.

that T u n, i is per packet under-utilization time, while T u n in (7) is cumulative
under-utilization time.
5

of CCP is Tccp and expressed as:

right after the previous computed packet is received at the collector.
Therefore, Tnaive is an upper bound of Tccp . Next, similar to the
derivation of (15), we calculate the gap between Tnaive and Tccp :

ccp
rn



Õ
Tccp = max RTTndata +
(βn,i + Tun,i ) ,
n ∈N



ccp

(14)

i =1



Ír n

Tnaive − Tccp = max

where r n = argminr n maxn ∈N RTTndata + i =1 (βn,i + Tun,i ) ,
and Tun,i is per packet under-utilization time at helper n, which
occurs as CCP does not have a priori knowledge of βn,i , so it determines packet transmission times using TT In,i in (8). The gap
between Tccp and Tbest is upper bounded by:
Tccp − Tbest = max
n ∈N

− max
n ∈N

≤ max
n ∈N

− max
n ∈N

≤ max
n ∈N

− max
n ∈N

= max
n ∈N



ccp

RTTndata

+

rÕ
n

βn,i + Tun,i

i =1



RTTndata +
RTTndata

+

best
rÕ
n

+

best
rÕ
n

βn,i

RTTndata +

best
rÕ
n

i =1

≥ max
n ∈N

n ∈N

n ∈N

best
rÕ
n

Tun,i

n ∈N



ccp

i =1

RTTndata + βn,i

RTTndata

+

naive
rÕ
n



(βn,i + Tun,i )

i =1

naive
rÕ
n

i =1

naive
rÕ
n

i =1






RTTndata + βn,i

RTTndata + βn,i







− 1)RTTndata ) −

max

n ∈N

n ∈N

naive
rÕ
n

(Tun,i )

i =1

naive
rÕ
n

(Tun,i ).

i =1

(17)

As seen, there is a gap between Tnaive and Tccp that asymptotically
grows with increasing number of tasks. This shows the effectiveness of our approach as compared to the naive algorithm for finite
number of tasks. In the next section, we will provide average task
completion delay analysis of CCP.

(15)


(RTTndata + βn,i ) ,

i =1



n ∈N

from the fact that max(f (x) + д(x)) < (max(f (x)) + max(д(x))).5
As seen, the performance of CCP increases with decreasing Tun,i ,
i.e., increasing efficiency in (12). Next, we find an upper bound on
the task completion delay performance of CCP.
To find an upper bound of Tccp , we consider a naive task allocation algorithm, where each packet is transmitted from the collector
to each helper n when the previous computed packet is received
from the helper. In this method, the total delay for receiving each
computed packet i from the helper n at the collector is equal to
the transmission delay of RTTndata plus the computing delay of βn,i .
Therefore, the total completion delay for this method, denoted by
Tnaive , is equal to:
Tnaive = max

(βn,i + Tun,i )

= min ((r nnaive − 1)RTTndata ) − max

where, the first inequality comes from r n = argminr n maxn ∈N


Ín
(βn,i + Tun,i ) and the second inequality comes
RTTndata + ri =1

naive

+

rn
Õ

i =1



Tun,i ,

ccp

− max(−(r nnaive
n ∈N

i =1

n
 rÕ

− max



− max

βn,i + max

βn,i





RTTndata + βn,i

i =1

≥ max
n ∈N



RTTndata

naive
rÕ
n

n ∈N




i =1

RTTndata +

best
rÕ
n

best
rÕ
n

n ∈N



βn,i + Tun,i

i =1

i =1



− max



i =1

RTTndata




βn,i

i =1




best
rÕ
n

n ∈N

naive
rÕ
n

5.2

Average Task Completion Delay of CCP

In this section, we analyze the delay performance of CCP on the
average, and show that CCP is optimal in terms of minimizing the
average task completion delay. Towards this goal, we start with understanding the optimal task allocation mechanism, and then discuss the optimality of CCP.
5.2.1 Optimal Task Allocation. The optimal task allocation
mechanism solves the following optimization problem:
min max Dn

r 1, ...,r N n ∈N
N
Õ

r n = R + K,

subject to

(16)

(18)

n=1


Ín
(RTTndata + βn,i ) . Tnaive is
where r nnaive = argminr n maxn ∈N ri =1
larger than Tccp , as CCP transmits a packet to each helper before or

where Dn is the task completion delay of helper n to receive r n
coded packets, compute them, and send the results back to the collector. The goal of the optimization problem in (18) is to minimize
the total completion delay, which is equal to maxn ∈N Dn , as helpers
compute their tasks in parallel. The constraint in (18) is a task conservation constraint that guarantees that resources of helpers are not

5 Note that in (15), we assume that the computing time for packet i at helper n is the
same both in the best algorithm and CCP, which is necessary for fair comparison. We
make the same assumption in (17).

6

wasted. Dn following the same argument in (13) is expressed as
Dn = RTTndata +

rn
Õ

βn,i .

We know from [20] that the average idle time between two successive arrivals, denoted by Tnidle , for a G/G/1 queue (and thus a
D/G/1 queue) is equal to:
1−ρ
1 1
Tnidle =
= − ,
(24)
λ
λ µ

(19)

i =1

For large values R, RTTndata becomes negligible as compared to
Ír n
Ín
i.e., (RTTdnat a << ri =1
βn,i ). Thus, Dn can be approxi =1 βn,i , Í
rn
imated as i =1 βn,i and the optimization problem in (18) is expressed as:
min max

r 1, ...,r N n ∈N
N
Õ

subject to

rn
Õ

where ρ = λ/µ. Therefore, our D/G/1 queue with λ = E[β1]+ϵ and
i
µ = 1/E[βi ] has the minimum average idle time of:
Tnidle = E[βi ] + ϵ − E[βi ] = ϵ.
(25)
Í
idle
Thus, the total idle time of the system is n ∈N Tn = N ϵ, which
is arbitrarily small for finite set N . This shows that the system resources are wasted N ϵ of the time, which is arbitrarily small. This
is a necessary condition for optimality.
As a sufficient condition, we should show that the D/G/1 queue
we described above has a stationary distribution, or equivalently
the average waiting time in the queue is finite. The mean stationwaiting
ary waiting time, Tn
, for a G/G/1 queue from [20] is upper
bounded by:

βn,i

i =1

rn = R + K

n=1

r n ∈ N, ∀n ∈ N .

(20)

The expected value of the objective function of (20) is expressed
Ín
Ín
as E[maxn ∈N ri =1
βn,i ], which is equal to maxn ∈N ri =1
βn,i =
maxn ∈N r n E[βn,i ] where expectation is across the packets. Assuming that (i) the average task completion delay is T = maxn ∈N r n
E[βn,i ], and (ii) ignoring the integer constraint in (20) as it is irrelevant on the average, (20) is reformulated to optimize the average
task completion delay as
min

r 1, ...,r N

waiting

Tn

σ2

(21)

n=1

When we solve (21) using Lagrange relaxation, we obtain the optimal task completion time Topt as
Topt = ÍN

R+K

1
n=1 E[βn, i ]

,

5.3

(22)

opt

opt

R+K
.
ÍN
1
E[βn,i ] n=1
E[βn, i ]

Case Study: Shifted Exponential Distribution

In this section, we characterize the optimal task completion delay
Topt in (13) for two delay models. Model I: The processing time of
each packet pn,i at helper n follows a shifted exponential distribution, and processing times of packets are i.i.d. This model suits well
for IoT applications where helpers have heterogeneous and timevarying resources, and our CCP algorithm is designed based on this
model. Model II: Assuming that r n packets are offloaded to helper
n, the processing time of all of these packets follows a shifted exponential distribution. This model is inspired from [3] and [7], and
suits well for large scale computing systems rather than IoT. We analyze the completion time of our CCP mechanism for both models
as described next.

and the optimal task allocation r n as
rn =

(26)

to 2ϵs . Thus, the average waiting time is finite for any service time
distribution (including exponential and shifted exponential distributions) with finite variance. This shows the optimality of CCP for
any computing time distribution that has a finite variance.

subject to r n E[βn,i ] ≤ T , ∀n
rn = R + K .

λ(σx2 + σs2 )
,
2(1 − ρ)

where σx2 and σs2 are the variances of the arrival and service times,
respectively. As seen, for our queueing system with deterministic
waiting
arrival process (i.e., σx2 = 0), the upper bound of Tn
is equal

T

N
Õ

≤

(23)

5.2.2 Optimality of CCP. As seen, the optimal number of packets that should be allocated to helper n is inversely proportional to
the average computing time per packet for helper n. Note that an algorithm that allocates packets to helpers with E[βn,i ] frequency also
achieves the optimal task completion delay in (22). CCP, although it
is a gradual algorithm, allocates packets to helpers at every E[βn,i ]
according to (8), so it is intuitive to conclude that CCP performs
close to the optimal task allocation on the average. Next, we show
that CCP achieves optimal task allocation on the average.
Let us focus on helper n. Sub-tasks arrive to helper n deterministically E[βi ] times apart according to CCP. We assume that small
fraction ϵ of subtasks are dropped (not processed) by helper n, and
the rest of packets are processed with the average time of E[βi ] per
packet. We can model the helper n’s task arrival process as a D/G/1
queue with arrival rate λ = E[β1]+ϵ (with arbitrarily small ϵ) and
i
the departure rate µ = 1/E[βi ]. Next, we show that this queue has
the minimum idle time and finite waiting time.

T HEOREM 2. The optimum task completion delay, i.e., Topt , is
characterized as
R+K
Topt = Í
(27)
µn
n ∈N 1+an µ n

for large R, and when βn,i , the runtime for computing packet pn,i by
helper n, is an i.i.d shifted exponential random variable with mean
an + 1/µ n and shifted value of an (i.e., Model I).
Proof: By replacing E[βn,i ] in 22 with an + 1/µ n , Topt is equal
to:
Topt = Í

R+K

µn
n ∈N 1+an µ n

7

,

(28)


T HEOREM 3. The optimum task completion delay, i.e., Topt , is
characterized for Model II as
R+K

1
n ∈N βn

,

Task Completion Delay

Topt = Í

200

(29)

where R is large, βn is the processing time of each packet pn,i at
helper n and is equal for all packets; i.e., βn,i = βn , ∀i. With the
assumption that βn is a shifted exponential random variable with
mean an + 1/µ n and shifted value of an , E[Topt ] is upper bounded
by:
R+K
E[Topt ] ≤ Í
,
(30)
µn

CCP
Optimum Analysis
Best
Uncoded (r n ∝ 1/(1/ µ n +a n ))

150

Uncoded (r n ∝µ n )

100

HCMM

50

0
0

2000

4000

6000

8000

10000

8000

10000

Numbr of Rows
(a) Scenario 1

n ∈N 1+an µ n

6

400



Task Completion Delay

Proof: The proof is provided in Appendix B.

SIMULATION RESULTS

In this section, we evaluate our Cooperative Computation Protocol (CCP). We consider two scenarios: (i) Scenario 1, where the
system resources for each helper vary over time. In this scenario,
the runtime for computing each packet pn,i , ∀i at each helper n
is an i.i.d shifted exponential random variable with shifted value
an and mean an + 1/µ n , and (ii) Scenario 2, where the runtime
for computing packets in helper n does not change over time, i.e.,
βn,i = βn , ∀i, and βn , ∀n ∈ N is a shifted exponential random
variable with shifted value an and mean an + 1/µ n .6
We evaluate CCP algorithm for Scenarios 1 and 2 and compare
its task completion delay with: (i) Optimum Analysis: The theoretical task completion delay characterization given by Theorem 2 for
Scenario 1 and Theorem 3 for Scenario 2. (ii) Best: Realization of
the best algorithm formulated in (13) by knowing βn,i a priori at the
collector and setting TT In,i as βn,i . (iii) Uncoded: r n packets without coding are assigned to each helper n, and the collector waits to
receive computed values from all helpers. We consider two scenar1
ios for setting r n ; the first one is proportional to a +1/µ
(mean of
n
n
βn,i ), and the second one is proportional to µ n . (iv) HCMM: Coded
cooperation framework developed in [7] using block codes.
In our simulations, each simulated point is obtained by averaging
over 200 iterations for N = 100 helpers. The transmission rate for
sending each packet from the collector to each helper n and from
helper n to the collector is a Poisson random variable with an average selected uniformly between 10 Mbps and 20 Mbps for each
helper n. The size of a transmitted packet pn,i is set to B x = 8R bits,
where R is the number of rows of matrix A, and it varies from 0 to
10,000 in our simulations. The sizes of a computed packet pn,i x and
an acknowledgement packet are set to B r = 8 bits and B ack = 1 bit,
respectively. We introduce 5% coding overhead for CCP, Optimum
Analysis and Best.
Task Completion Delay vs. Number of Rows: Fig. 3(a) shows
completion delay versus number of rows for Scenario 1, where the
runtime for computing each packet by helper n, βn,i , ∀i, is a shifted
exponential random variable with shifted value of an = 0.5 and
mean of an + 1/µ n , where µ n is selected uniformly from {1, 2, 4}.
As seen, CCP performs close to the Optimum Analysis (27) and the

CCP
Optimum Analysis
Best
Uncoded (r n ∝ 1/(1/ µ n +a n ))

300

Uncoded (r n ∝µ n )

200

HCMM

100

0
0

2000

4000

6000

Number of Rows
(b) Scenario 2

Figure 3: Task completion delay vs. number of rows/packets for
(i) Scenario 1, and (ii) Scenario 2, where the runtime for computing one row by helper n is selected from a shifted exponential distribution with an = 0.5, ∀n ∈ N and µ n , which is selected
uniformly from {1, 2, 4}.

best algorithm. This shows the effectiveness of our proposed algorithm. In addition, CCP performs better than the baselines. In particular, in average, 30% and 24% improvement is obtained by CCP
over HCMM and no coding, respectively. Fig. 3(b) considers the
same setup but for Scenario 2, where the runtime for computing r n
packets by helper n is r n βn , where βn is selected from a shifted
exponential distribution with an = 0.5, ∀n ∈ N and µ n , which is selected uniformly from {1, 2, 4}. As seen, for this scenario, CCP performs close to the Optimum Analysis given by (29) and the best algorithm. CCP performs better than HCMM, and HCMM performs
better than no coding. In particular, in average, 40% and 69% improvement is obtained by CCP over HCMM and no coding, respectively. Note that uncoded performs better than HCMM for Scenario
1, as HCMM is designed for Scenario 2, so it does not work well in
Scenario 1. CCP performs well in both scenarios.
Fig. 4 shows completion delay versus number of rows for both
Scenarios 1 and 2, where the runtime for computing the rows by
each helper n, is from a shifted exponential distribution with µ n , n ∈
N selected uniformly from {1, 3, 9} and an = 1/µ n (different shifted
values for different helpers). As seen, CCP performs close to Optimum Analysis and the best algorithm and much better than the

6 Note that Scenarios 1 and 2 correspond to Models I and II in Section 5.3, respectively.

8

2500
CCP
Optimum Analysis
Best
Uncoded
HCMM

60

2000

T naive -Tccp

1500

40

1000

20

500
0

0
0

2000

4000

6000

8000

0.5

10000

(a) Scenario 1
150

0
2000

4000

6000

2

× 10 4

CCP as Compared to Best And Naive Algorithms: Fig. 5,
shows the gap between CCP and the best algorithm, which is characterized in (15), and the gap between CCP and the naive algorithm,
which is characterized in (17). For calculating Tbest , we assume
βn,i ’s are known a priori and we set TT In,i as βn,i ; Tbest is the
time for receiving the (R + K)th computed packet at the collector.
For calculating Tnaive , we send a packet to each helper n right after the previous computed packet is received at the collector from
that helper; Tnaive is the time for receiving the (R + K)th computed
packet at the collector. As expected, the gap between Tccp and Tnaive
increases rapidly with increasing the number of rows, while the gap
between Tccp and Tbest remains small with increasing the number of
rows. For the simulation results of Fig. 5, N = 10 helpers are used
and the transmission rate for sending each packet from the collector
to each helper n and from helper n to the collector is a Poisson random variable with an average selected uniformly between 0.1 Mbps
and 0.2 Mbps for each helper n. The other parameters are the same
as the parameters used in Fig. 3(b).

50

0

1.5

Figure 5: CCP as compared to best and naive algorithms.

CCP
Optimum Analysis
Best
Uncoded
HCMM

100

1

Number of Rows

Number of Rows

Task Completion Delay

T ccp -Tbest

Gap

Task Completion Delay

80

8000

10000

Number of Rows
(b) Scenario 2

Figure 4: Task completion delay vs. number of rows/packets for
(i) Scenario 1, and (ii) Scenario 2, where the runtime for computing one row by each helper n is selected from a shifted exponential distribution with µ n , which is selected uniformly from
{1, 3, 9} for different helpers and an = 1/µ n , ∀n ∈ N

baselines. In particular for Scenario 1, more than 30% and 15% improvement is obtained by CCP over HCMM and no coding, respectively. Also, for Scenario 2, in average, 42% and 73% improvement
is obtained by CCP over HCMM and no coding, respectively.
Efficiency: We calculated the efficiency of helpers for different
simulation setups and compared it with the theoretical efficiency
obtained in (12) for Scenario 1. For all simulation setups, the average efficiency over all helpers was around 99% and the theoretical efficiency was a little lower than the simulated efficiency. E.g.,
for R = 8000 rows, where µ n , n ∈ N is selected uniformly from
{1, 3, 9} and an = 1/µ n , the average of efficiency over all helpers
is 99.7072% and the average of theoretical efficiency is 99.4115%.
This is expected as the theoretical efficiency is based on the average
analysis.
We also calculate the efficiency of helpers for Scenario 2. For
all simulation setups, the average efficiency over all helpers was
around 99%, e.g., for R = 8000 rows, where µ n , n ∈ N is selected
uniformly from {1, 3, 9} and an = 1/µ n , the average of efficiency
over all helpers was 99.9267%. Note that the theoretical efficiency
for Scenario 1 is 100%. The simulated efficiency is lower than the
theoretical one, because the simulation underutilizes the helpers
when transmitting the very first packets, i.e., before the collector
estimates the resources of helpers.

7

RELATED WORK

Cooperative computation is a promising approach for localized data
processing for IoT, where computationally intensive tasks in a device (collector device) could be offloaded to another device or servers
(helpers) in close proximity [1], [2]. Indeed, cooperative computation mechanisms by exploiting D2D connections of mobile devices
in close proximity are developed in [14] and [15]. A similar approach is considered in [16] with particular focus on load balancing across workers. As compared to this line of work, we consider
coded cooperative computation.
Coded cooperative computation is shown to provide higher reliability, smaller delay, and reduced communication cost in MapReduce framework [17], where computationally intensive tasks are offloaded to distributed server clusters [18]. In [3] and [19], coded
computation for matrix multiplication is considered, where matrix
A is divided into sub-matrices and each sub-matrix is sent from the
master node (called collector in our work) to one of the worker
nodes (called helpers in our work) for matrix multiplication with
the assumption that the helpers are homogeneous. In [3], workload
of the worker nodes is optimized such that the overall runtime is
minimized. In [7], the same problem is considered, but with the assumption that workers are heterogeneous in terms of their resources.
9

Compared to this line of work, we develop CCP, a practical algorithm that is (i) adaptive to the time-varying resources of helpers,
and (ii) does not require any prior information about the computation capabilities of the helpers. As shown, our proposed method
reduces the task completion delay as compared to prior work.

8

[20] D.P. Bertsekas and R.G. Gallager, “Data Networks,” Prentice-Hall International,
1992.

APPENDIX A: PROOF OF THEOREM 1
With the assumption that βn,i −1 is from a shifted exponential distribution with shifted value of an and mean of an + 1/µ n , E[βn,i ] in
(10) can be written as an + 1/µ n :

CONCLUSION

In this paper, we designed a Computation Control Protocol (CCP),
where heterogeneous IoT devices with different computation capabilities and energy resources are connected to each other. In CCP,
a collector device divides tasks into sub-tasks, offloads them to
helpers by taking into account heterogeneous resources. CCP is (i)
a dynamic algorithm that efficiently utilizes the potential of each
helper while not overutilizing them, (ii) adaptive to the time-varying
resources at helpers. We analyzed the performance of CCP in terms
of task completion delay and efficiency. Simulation results confirm
that CCP reduces the completion delay and is efficient.


RTTndata ,




Tun,i = an + µ1 − βn,i −1,
n


 0,


if an < βn,i −1 < an + µ1n − RTTndata
if an + µ1n − RTTndata < βn,i −1 < an + µ1n
otherwise,
(31)

where, the random variable βn,i −1 is always greater than its shifted
value, an , i.e., the condition βn,i −1 > an is always satisfied. From
(31), the value of variable Tun,i changes depending on the value of
RTTndata compared with the distribution parameter 1/µ n . Therefore,
(31) can be decomposed as:
(
T̃n,i , if RTTndata < 1/µ n
(32)
Tun,i =
T n,i , otherwise,

REFERENCES
[1] Y. Li and W. Wang, “Can mobile cloudlets support mobile applications?,”IEEE
INFOCOM 2014 - IEEE Conference on Computer Communications, Toronto, ON,
2014, pp. 1060-1068.
[2] M. Chen, Y. Hao, Y. Li, C. F. Lai and D. Wu, “On the computation offloading at
ad hoc cloudlet: architecture and service modes,” in IEEE Communications Magazine, vol. 53, no. 6, pp. 18-24, June 2015.
[3] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos and K. Ramchandran, “Speeding up distributed machine learning using codes,” in Proc. of IEEE International
Symposium on Information Theory (ISIT), Barcelona, Spain, July 2016.
[4] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G.
Hullender, “Learning to rank using gradient descent,” in Proceedings of the 22nd
international conference on Machine learning. ACM, 2005, pp. 89âĂŞ96.
[5] T. Zhang, “Solving large scale linear prediction problems using stochastic gradient
descent algorithms,” in Proceedings of the twenty-first international conference on
Machine learning. ACM, 2004, p. 116.
[6] L. Bottou, “Large-scale machine learning with stochastic gradient descent,” in Proceedings of COMPSTATâĂŹ2010. Springer, 2010, pp. 177âĂŞ186.
[7] A. Reisizadeh, S. Prakash, R. Pedarsani and A. S. Avestimehr, “Coded Computation over Heterogeneous Clusters,” available in ArXiv, arXiv1701.05973.
[8] M. Luby, “LT codes,” in Proc. of The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002.
[9] A. Shokrollahi, “Raptor codes,” in IEEE Transactions on Information Theory, vol.
52, no. 6, pp. 2551-2567, June 2006.
[10] D. J. C. MacKay, “Fountain codes,” in IEE Proceedings - Communications, vol.
152, no. 6, pp. 1062-1068, 9 Dec. 2005.
[11] T. Ho, R. Koetter, M. Medard, D. R. Karger and M. Effros, “The benefits of
coding over routing in a randomized setting,” in Proc. of IEEE International Symposium on Information Theory, 2003.
[12] S. Lin, D. J. Costello, and M. J. Miller. “Automatic-repeat-request error-control
schemes,” in IEEE Communications Magazine, vol. 22(12), pp. 5-17, 1984.
[13] K. Lai, M. Feldman, I. Stoica and J. Chuang, “Incentives for Cooperation in Peerto-Peer Networks,” in Workshop on Economics of Peer-to-Peer Systems, Berkeley,
CA, 2003.
[14] R. K. Lomotey and R. Deters, “Architectural designs from mobile cloud computing to ubiquitous cloud computing - survey,” in Proc. IEEE Services, Anchorage,
Alaska, June 2014.
[15] E. Miluzzo, R. Caceres and Y. Chen, “Vision: mclouds - computing on clouds of
mobile devices,” in ACM workshop on Mobile cloud computing and services, Low
Wodd Bay, Lake District, UK, June 2012.
[16] T. Penner, A. Johnson, B. V. Slyke, M. Guirguis and Q. Gu, “Transient clouds:
Assignment and collaborative execution of tasks on mobile devices,” in Proc. IEEE
GLOBECOM, Austin, TX, Dec. 2014.
[17] J. Dean and S. Ghemawat, “Mapreduce: simplified data processing on large clusters,” in Communications of the ACM , vol. 51, no. 1, pp. 107âĂŞ113, 2008.
[18] S. Li, M. A. Maddah-Ali and A. S. Avestimehr, “Coded MapReduce,” in 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton),
Monticello, IL, 2015.
[19] S. Dutta, V. Cadambe and P. Grover, “Short-dot: Computing large linear transforms distributedly using coded short dot products,” in Advances In Neural Information Processing Systems (NIPS), Barcelona, Spain, Dec. 2016.

where,

RTTndata ,




T̃n,i = an + µ1n − βn,i −1,


 0,


if an < βn,i −1 < an + µ1n − RTTndata
if an + µ1n − RTTndata < βn,i −1 < an + µ1n
otherwise,
(33)

and,

T n,i =

(
an + 1/µ n − βn,i −1, if an ≤ βn,i −1 ≤ an + 1/µ n
(34)
0,
otherwise

˜ n and T n,i .
To prove Theorem 1, we find the expected values of Tu
i
From (33), the average of T˜n,i is calculated as:
∫
˜
E[Tn,i ] =
f βn, i −1 (t)T˜n,i dt
=
+

∫ an +1/µ n −RT T data
n
an

∫ an + 1
µn

an + µ1n −RT Tndata

µ n exp(−µ n (t − an ))RTTndatadt

µ n exp(−µ n (t − an ))(an +

1
− t)dt
µn

= RTTndata + 1/µ n (exp(−1) − exp(µ n RTTndata − 1)). (35)
Similarly, from (34), we can calculate the average of T n,i :
E[T n,i ] =
=

∫

f βi −1 (t)T n,i dt

∫ an +1/µ n
an

µ n exp(−µ n (t − an ))(an + 1/µ n − t)dt

= 1/µ n exp(−1).
10

(36)

where the last inequality comes from the fact that βn , n = 1, 2, ..., N
is always positive7 . For any concave function д(x), the inequality of
E[д(x)] ≤ д(E[x]) is satisfied. Therefore, we have:

By replacing the obtained expected values of T̃n,i and T n,i in (32),
we have:
 RTTndata + 1 (e −1 − exp(µ n RTTndata − 1)),

µn



if RTTndata < µ1n
E[Tun,i ] =


 1 e −1,
otherwise.
 µn
(37)

This concludes the proof.

APPENDIX B: PROOF OF THEOREM 3
With the assumption that βn,i = βn , ∀i, E[βn,i ] in (22), is equal to
βn , as the computation time for computing all packets by helper n
are equal. Thus, the optimum completion delay is equal as:
R+K
Topt = Í
.
(38)
n ∈N 1/βn
This proves (29). Next, we prove (30).
We first define function д(β 1 , β 2 , ..., βn ) = ÍN 1 . This funcn=1



R+K
E[Topt ] = E Í
n ∈N 1/βn


1
= (R + K)E Í N
n=1 1/βn
1
≤ (R + K) ÍN
n=1 1/E[βn ]
1
= (R + K) ÍN
.
µn

βn

tion is a concave function, as its second derivative with respect to
βm , m = 1, 2, . . . , N is negative, as shown below:


d
1
d2
1
(39)
д(.)
=
.

Í
2 (β )2
N
dβm
d(βm )2
m
n=1 1/βn
2
−2
=
3 +
 2 (40)
ÍN
ÍN
4
3
(βm )
(βm )
n=1 1/βn
n=1 1/βn

 −β ÍN
m n=1,n,m 1/βn
2
(41)
=
ÍN
2
ÍN
βm n=1
1/βn
(βm )3 n=1
1/βn
≤ 0,
(42)

n=1 1+an µ n

7 Note

that β n is the computing time per packet and thus it should be positive.This is
also considered when selecting shifted exponential distribution for β n , as β n ≥ an >
0.

This concludes the proof.

11

(43)
(44)
(45)
(46)

