Combating Computational Heterogeneity in Large-Scale
Distributed Computing via Work Exchange
Mohamed Adel Attia

Ravi Tandon

Department of Electrical and Computer Engineering

arXiv:1711.08452v1 [cs.DC] 22 Nov 2017

University of Arizona, Tucson, AZ 85721
E-mail:{madel, tandonr}@email.arizona.edu

November 23, 2017

Abstract
Owing to data-intensive large-scale applications, distributed computation systems have gained
significant recent interest, due to their ability of running such tasks over a large number of commodity nodes in a time efficient manner. One of the major bottlenecks that adversely impacts
the time efficiency is the computational heterogeneity of distributed nodes, often limiting the
task completion time due to the slowest worker. In this paper, we first present a lower bound
on the expected computation time based on the work-conservation principle. We then present
our approach of work exchange to combat the latency problem, in which faster workers can be
reassigned additional leftover computations that were originally assigned to slower workers. We
present two variations of the work exchange approach: a) when the computational heterogeneity
knowledge is known a priori; and b) when heterogeneity is unknown and is estimated in an online
manner to assign tasks to distributed workers. As a baseline, we also present and analyze the use
of an optimized Maximum Distance Separable (MDS) coded distributed computation scheme
over heterogeneous nodes. Simulation results also compare the proposed approach of work exchange, the baseline MDS coded scheme and the lower bound obtained via work-conservation
principle. We show that the work exchange scheme achieves time for computation which is very
close to the lower bound with limited coordination and communication overhead even when the
knowledge about heterogeneity levels is not available.

1

Introduction

Due to the astonishing expansion of the data production in the recent years, processing of large scale
data-sets over a centralized single machine is widely becoming infeasible. This growth moves the
computational paradigm towards large distributed computation, which can enable the processing
of data-intensive tasks for machine learning, and data mining over a large number of commodity
machines in a time-efficient manner (e.g., Apache Spark [1], and MapReduce [2]). One of the
concerns related to large-scale distributed computation is due to stragglers, which are a small set
of machines/nodes that can unexpectedly run slower than the average or can be even disconnected
This work was supported by the NSF grant CAREER-1651492.

due to several factors such as resource contention, network or disk failures, and power limits [3, 4].
Being buckled under faults, the task will be delayed or even never completed when the master node
has to wait for extended periods pf time until the stragglers reply.
In order to mitigate the impact of stragglers, various approaches have been proposed from several
research communities, as discussed next. One approach is to efficiently detect the stragglers while
running computational tasks, and then relaunch the delayed tasks on other machines [4,5]. Another
set of approaches attack this problem by introducing redundancy in computation. The simplest
form of redundancy, i.e., repetition was proposed in [6, 7], where each repeated task can combat
one straggler doing the same task. However, a more efficient approach to introduce redundancy is
by leveraging codes. In particular, the idea of using (n, k) Maximum Distance Separable (MDS)
coded distributed computations was presented in [8] for linear distributed computations such as
matrix multiplication, where n is the number of workers. The computation time is then limited
by the k th (instead of the nth ) fastest worker. The performance can also be quantified in terms of
the recovery threshold metric, where any k out of n workers are sufficient to complete the whole
underlying task, and hence the system can tolerate up to any (n − k) stragglers. The result in [8]
was extended in [9] for high dimensional matrix multiplication. More recently, a new class of codes
(polynomial codes) were proposed in [10], which achieve the optimal recovery threshold for high
dimensional matrix multiplication. Moreover, in [11], and [12], an efficient coded framework was
proposed using MDS codes for distributed matrix multiplication in the MapReduce setting. In [13],
the authors proposed the use of codes in parallelly computing the convolution of two long vectors
before a deadline in the presence of stragglers. In addition to coded computation, there are other
other hardware based approaches approaches to combat computational heterogeneity by explicitly
attempting to reduce the unevenness and variability related to hardware effects, e.g., [14]. Another
approach (with roots in operations research commpunity) is that of work stealing, where the faster
workers take over the remaining computations from the slower workers once they finish their tasks
leaving the slower workers idle till the end of the computation session [15].
At the core of the straggler problem is the heterogeneity of computation across the workers,
i.e., different workers in the cluster may have different computational capabilities. The recently
proposed approaches that employ codes to combat this problem have the drawback that they only
use the computations from a subset of workers, and hence, the computations performed from the
remaining nodes are not used at all. Furthermore, other approaches such as work stealing and
variations suffer from the drawback that slower workers can remain idle for certain periods of time.
In summary, all of the aforementioned approaches suffer either from redundant computations or
idle workers not participating for a period of time. In this work, we explore a series of fundamental
questions related to this problem:
• Q1 : If no redundant computations are permitted, nor any worker remains idle at any point,
what is the minimum time for distributed computation? To answer this question, we present
an orcale lower bound on the computation time which is a function of the underlying computational speeds of the workers (i.e., the parameters describing the computational heterogeneity).
• Q2 : How do we devise schemes that can approach the oracle lower bound? To answer this
2

question, we present a new idea called work exchange, which attempts to minimize redundant
computations, by reassigning and exchanging computational tasks across workers. This work
exchange approach is fundamentally different from the coded computation approaches in two
ways: a) it attempts to minimize redundant computation and leverage the knowledge of computational heterogeneity in the system; and b) it works for linear or non-linear computational
tasks as long as the original task is sub-divisible into large number of smaller sub-tasks.
• Q3 : What are the resources that can be traded-off in order to minimize the computation time?
Coded distributed computation approaches (in particular, the ones using MDS codes) require
excess number of workers (in contrast to waiting for the slowest worker), however they do
not require intermediate coordination once the tasks are assigned. On the other hand, the
proposed work exchange approach leads to a reduction in the computation time, however, it
requires more coordination/communication overhead for the re-assignment of tasks. Thus,
the fundamental question is that what are the tradeoffs between communication, storage and
coordination in order to achieve a certain time for distributed computation.
To give an intuition behind leveraging the knowledge of computational heterogeneity, let us
consider a matrix multiplication problem where we need to compute Ax, where A ∈ R200×d and
x ∈ Rd×1 over a cluster of three distributed workers. Clearly, this problem can be divided into 200d
elementary multiplication operations. The three workers are heterogeneous and for simplicity, let
us assume that they work at a constant rate λ1 = d, λ2 = 3d, and λ3 = 6d operations per second
for workers 1, 2, and 3 respectively.
Heterogeneity unaware MDS Coded Computation: The coding based approach works as follows: we
(1)
(1)
first divide the matrix A across rows into two equal sub-matrices A1 , and A2 of size 100 × d each.
(1)
Then, we use a (3, 2) MDS code over these sub-matrices to generate 3 coded matrices, e.g., A1 ,
(1)
(1)
(1)
A2 , and A1 + A2 , to be assigned to the three workers as shown in Figure 1a. Every worker
then multiplies the assigned coded matrix with x, which needs 100d operations for each worker.
According to the speed of each worker, the master node receives the replies from workers 1, 2, and
3 after 100, 33.33, and 16.67 seconds, respectively. However, due to the MDS property, any 2 out of
(1)
(1)
3 replies are enough to decode A1 x, and A2 x, yielding the completion time to be 33.33 seconds.
Heterogeneity aware Distributed Computation: Consider now the following approach, where instead
(2)
(2)
of adding redundancy, we break the matrix A into three unequal sized sub-matrices A1 , A2 , and
(2)
A3 of sizes 20 × d, 60 × d, and 120 × d, respectively, and then assign them to workers 1, 2, and
3, respectively as shown in Figure 1b. According to the speed of each worker, the master node
receives the replies from the three workers simultaneously after 20 seconds, which is less than 33.33
seconds achieved using the coding approach. From this simple example, we make the following
key observations: a) if we are aware of computational heterogeneity (or if it can be estimated),
then we can leverage such prior heterogeneity knowledge in order to balance out the computational
operations assigned to the workers; b) ignoring slow workers or introducing redundant computations
is not always optimal from a latency perspective.
We next summarize the main contributions of this paper:

3

Worker 1
(1)
A1 x

Worker 1
(2)

after 20 sec.

after 16.67 sec. (Fastest)

Master Nodex
d⇥1
Master Node

(1)
A2 x

100 ⇥ d

(1)

A2 x

after 33.33 sec.

3d

20 ⇥ d

(2)

A1 x

6d oper./sec.
Worker 2

120d
oper.

A1 x

100 ⇥ d

(1)

A1 x

100d
oper.

100d
oper.

6d oper./sec.
(Fastest)

Worker 2

Master Nodex
d⇥1
Master Node

oper./sec.

(Slower)

(2)

A2 x

(2)

A2 x

after 20 sec.

3d

60d
oper.

60 ⇥ d

oper./sec.

(Slower)

100d

Worker 3 oper.
(1)

Worker 3

(1)

(2)

A1 + A2
(1)
A1 x

+

(1)
A2 x

after 100 sec.

d

A3 x

100 ⇥ d

(2)
A3 x

oper./sec.

after 20 sec.

(Slowest)

(a)

d

120 ⇥ d

20d
oper.

oper./sec.

(Slowest)

(b)

Figure 1: The matrix multiplication Ax problem over three workers with different computational
speeds. In Figure 1(a), a (3, 2) MDS code is used so that any 2 replies are enough to decode Ax.
This coded computation scheme achieves a computation time of 33.33 seconds. In Figure 1(b), the
computation of Ax is unevenly divided across the workers according to the heterogeneity knowledge
so that all workers finish simultaneously after 20 seconds.
• We first study a baseline scheme which uses (n, k) MDS codes for distributed computation, and
find the expected mean computation time optimized over all choices of k ∈ [1 : n].
• We then study the work conservation principle, and derive an oracle lower bound on the computation time as a function of the computational heterogeneity of the system. We find that this
oracle lower bound bears an interesting analogy to the well known water-filling solution for optimal power allocation over parallel channels with heterogenous noise characteristics. In the optimal
water-filling solution, more power is assigned to channels with higher signal-to-noise ratio (SNR).
Similarly, the oracle lower bound naturally suggests that to minimize computation time, more
computations must be assigned to workers with faster computational capabilities.
• We then propose a work-exchange based scheme, with the goal of approaching the oracle bound,
through limited coordination and communication among workers. We first consider the case when
the heterogeneity knowledge is known apriori. We then address a more realistic scenario where the
heterogeneity knowledge is not available, and can be gradually learned over time allowing for larger
levels of coordination and communication as compared to the former case.
• We present simulation results to compare the baseline optimized MDS coded scheme, the oracle
lower bound and the variations of work-exchange based scheme. Interestingly, the work-exchange
scheme is shown to be very close to the lower bound and requires limited amount of coordination
and communication even without heterogeneity knowledge.

4

2

System Model

We consider a distributed computation system, where the master node has the entire data-set of
N data points. The master node sends batches of the data-set to a set of K distributed workers
in order to locally calculate some function or train a model in a distributed manner. Each worker
independently starts to compute a function of the assigned batch (as an example, this function
could correspond to the gradient or sub-gradients of the data points assigned to the worker). Then,
the local functions are fed-back to the master node for further processing. For this work, we assume
the computations can be divided into smaller and independent sub-tasks (i.e., N is large enough)
and the task is not sequential which means that the results do not depend on the order in which the
data is being processed, and the overall computational task terminates once the master node gets
results for the total N data points in any order. The time utilized to process a single data point is
random, and is modeled at any worker wk as an exponential random variable with average speed
λk number of processed points per second, i.e., tnk ∼ exp(λk ) and tnk is the time used to process a
point n = {1, 2, . . . , N } at worker wk , where k ∈ K̄ = {1, . . . , K}. We also define λ̄ = {λ1 , . . . , λK }
as the heterogeneity parameter set for the K workers.
The master node initially assigns the data-set to the K workers in data batches spanning the
whole data-set. Our system model also allows for reassigning data points to the workers according
to some conditions in order to speed up the process, where the new assignments span the points
(k,i)
that are not yet processed. We define Nassign as the number of points assigned to worker wk
at the reassigning iteration i ∈ {1, 2, . . . , I}, where I represents the total number of reassigning
(k,i)
epochs/iterations. We also define Ndone as the number of points processed by worker wk during
P
(k,i)
(k)
the ith iteration, and Ndone = Ii=1 Ndone as the total number of points processed by worker wk
over the entire process. The reassignment process imposes extra communication overhead, which
is given for a worker wk and the ith assignment by
(k,i)

(k,i−1)

(k,i)
Ncomm
= max(Nassign − Nleft
(k,i−1)

(k,i−1)

, 0),

(1)

(k,i−1)

where Nleft
= Nassign − Ndone is number of points not processed by wk from the previous
assignment. The total extra communication overhead (not including the initial assignment) is
therefore
Ncomm =

K X
I
X

(k,i)
Ncomm
.

(2)

k=1 i=2

The end-to-end completion time T can be written now as the sum of three components: T = Tcomp +
Tcomm + Tcorr , where Tcomp is the time for computation, Tcomm is the time for communication and is
directly proportional to Ncomm , and Tcorr is the time for coordination and is directly proportional
to the number of reassignments I. In this work, we will study the terms {Tcomp , Ncomm , I}, and
the trade-offs between them.

5

3

Baseline MDS Coded Computation Scheme

We first consider the MDS coded computation scheme recently developed in [8] to combat stragglers
as a baseline to be compared with the lower bound and the proposed work-exchange schemes. For
fair comparison, we consider the same number of distributed workers K to be used in order to
process a data-set of N data points, where MDS codes can be used as follows: a) the data-set is
divided into equal chunks of N/L points each, for some L ∈ K̄ = {1, 2, . . . , K}; b) (K, L) MDS
codes can be used to assign coded chunks of data to the workers, such that the learning process is
done as soon as any L out of the K workers reply back with the processed points; and then c) the
value of L ∈ K̄ can be optimized in order to get the lowest possible computation time.
Let us now define the random variable Tk,m as the time required to process m points by a
worker wk with rate λk , then Tk,m (which is a sum of exponential random variables) follows an
Erlang distribution, i.e., Tk,m ∼ Erlang(m, λk ). Using (K, L) MDS codes, the total computation
MDS (L) = T (L,m) at
time is limited by the Lth fastest worker instead of the slowest worker, i.e., Tcomp
m = N/L, where T (L,m) is the Lth ordered statistic for the random variables Tk,m , where k ∈ K̄.
MDS (L) is
Therefore, the mean value for Tcomp
MDS
E[Tcomp
(L)] = µ(L,N/L) ,

(3)

where µ(L,m) is defined as the mean of the Lth ordered statistic for K independent and nonidentically distributed Erlang random variables Tk,m , k ∈ K̄, with rate λk and a shape parameter
m. In order to find µ(L,m) , we use the results in [16] and apply them to our model after some
mathematical manipulations (omitted here due to space constraints), where using the following
recursion relation we can find µ(L,m) starting from µ(0,m) = 0 as follows:
µ(`,m)

X̀
K −`+j
= µ(`−1,m) +
(−1)j−1
j−1
j=1

!

m
,
PK−`+j

(4)

 P
 j 

( i ni ) ! Y λki ni
,
n1 ! . . . nj !
λK j

(5)

where ` ∈ {1, 2, . . . , L}, and Pjm can be written as
Pjm

=

X

X

Kj ⊆K̄ 0≤ni <m
i=1,...,j

1
λKj

i=1

P
where Kj = {k1 , . . . , kj } ⊆ K̄ is an arbitrary sub-set of j workers, and λKj = ji=1 λki . Finding
µL,m using the recursion relation in (4), ∀L ∈ K̄, we then can get the optimized mean of the MDS
coded computation scheme as follows
MDS
E[Tcomp
] = min µ(L,N/L) .
L∈K̄

6

(6)

4

Lower Bound (Work Conservation Principle)

In this section, we present an oracle lower bound on the computation time using the work conservation principle. For the oracle bound analysis, we assume a genie aided system satisfying the work
conservation principle with the following assumptions:
1. All the K workers have the entire data-set available in their storage;
2. Complete coordination between the workers is permitted and the data points computed at
each worker have no overlap (i.e., each worker performs completely distinct computations),
P
(k)
i.e., K
i=1 Ndone = N ;
3. No worker remains idle at any point of the learning process.

oracle as a random variable representing the total time needed to finish the
We now define Tcomp
computations for all the N data points across the K workers. We further define the random
variable NTcomp
oracle (t) as the total number of points processed across the K workers at time t. The
following Theorem provides an oracle bound for the average computation time, as well as the
expected number of data points processed by every worker towards completion following the work
conservation principle.

Theorem 1. The average computation time for the oracle scheme on a set of K distributed workers
of heterogeneity set λ̄, and collaborating on the processing of N number of data points is given by
oracle
E[Tcomp
]=

N
,
λsum

where λsum =

K
X

λk .

(7)

i=1

This lower bound can be viewed as the expected computation time for an oracle machine working
with the sum of the speeds (λsum ) of the distributed workers.
oracle for t ≥ 0 can be found as
Proof. The CDF of Tcomp
oracle
FTcomp
oracle (t) = Pr(Tcomp ≤ t) = Pr(NT oracle (t) ≥ N )
comp

=

K
Y

X

nk ∈n̄ k=1
nsum =N

=

X



(k)
Pr Ndone (t) ≥ nk

Pn̄ (t)

nk ∈n̄
nsum ≥N

=1−

X

Pn̄ (t),

(8)

nk ∈n̄
nsum <N

where NTcomp
oracle (t) is the total number of points processed at time t, nsum =

7

PK

k=1 nk ,

n̄ = {n1 , . . . , nK },

and Pn̄ (t) is given as follows
Pn̄ (t) =

K
Y

k=1

K

 Y
e−λk t (λk t)nk
(k)
Pr Ndone (t) = nk =
.
nk !

(9)

k=1

oracle is a non-negative random variable, the average time E[T oracle ] to finish all the N
Since Tcomp
comp
point across the K workers can be found as
oracle
E[Tcomp
]=

Z

0

∞


X Z
1 − FTcomp
oracle (t) dt=

∞

Pn̄ (t)dt,

(10)

nk

(11)

0
nk ∈n̄
nsum <N

where the integration in (10) can be found as
Z

∞

Pn̄ (t)dt =

0

1
λsum



nK̄ !
n1 ! . . . nK !

Y
K 
k=1

λk
λsum

.

Using (11), we can now rewrite the summation in (10) as
oracle
E[Tcomp
]

=

=

1
λsum
1
λsum

N
−1
X

X

n
n1 , . . . , n K

n=0 nk ∈n̄
nsum =n

N
−1
X

1=

n=0

!


K 
Y
λk nk
λsum

k=1

N
,
λsum

(12)

where the second equality follows from the Multinomial theorem, which proves Theorem 1.
Corollary 2. The expected total number of points processed at completion by worker wk with mean
speed λk is given by
(k)

E[Ndone ] = λk t =
Proof. Let us fix a time frame t =

N
λsum ,

λk N
.
λsum

(13)

which is the mean completion time. The number of
(k)

points done by a worker wk in time t is a Poisson random variable with mean λk t, i.e., Ndone ∼
kN
Poisson(λk t = λλsum
). Therefore, the mean number of points processed by wk by completion is given
as in (13).

5

Heterogeneity Aware Work-Exchange

In this section, we try to approach the oracle bound in (7) using the prior heterogeneity knowledge
of the workers reflected by the values of λk , for k = 1, . . . , K. According to (13), the average
number of data points processed by a worker wk is directly proportional to λk . That is, we need to
assign smaller tasks for slower workers, and larger tasks for faster workers. In our first algorithm,
we we present a heterogeneity aware scheme in which do not allow any intermediate coordination
8

1

>

2

>

Worker 1

3

60%
done

100%
done
Send
feedback

1
sum

Work progress

100%
done

Worker 2
100%
done
Send
feedback

2
sum

100%
done

100%
done

90%
done

100%
done
Send
feedback

Worker 3

3
sum

40%
done

Initial
Assignment

Worker 2
is done

Worker 1
is done

Worker 3
is done

time

Wait for all to finish

Figure 2: (Fixed work assignment Algorithm in Section 5.1) The work is initially assigned according
to the heterogeneity knowledge such that faster workers get larger assignments and vice versa. The
master node waits for all the workers to reply.
or communication between the workers and the master once the data is initially assigned. That is,
the tasks assignment for the workers remains fixed throughout the computation process. We next
introduce the work exchange approaches by allowing for a low level of intermediate coordination
and communication between the workers and the master in order to further reduce the latency.

5.1

Heterogeneity Aware Scheme with Fixed Work Assignment

The basic idea of this scheme is that the master node assigns different and non-overlapping portions
of data for every worker depending on the heterogeneity knowledge such that the worker with higher
λ gets more data assignment as follows
(k)

Nassign =

λk N
,
λsum

∀k ∈ K̄.

(14)

The master node waits for all the workers to reply back as shown in Figure 2. That is the
computation time is limited by the last worker to reply. The completion time for worker wk is the
(k)
time needed to process Nassign data-points at a rate λk , which follows an Erlang distribution, i.e.,
(k)

Tk ∼ Erlang(Nassign , λk ). Therefore, the total computation time is
Tcomp = max(T1 , T2 , . . . , TK ).

5.2

(15)

Work Exchange with Heterogeneity Knowledge

We next present the work exchange scheme for the scenario in which the master node has knowledge
about computational heterogeneity. Similar to the previous scheme, the initial assignment depends

9

1

>

2

>

3

Count
Remaining
Work

i=1
Worker 1

Work progress

Worker 1

fs = 1
60%
done

1
sum

Count
Remaining
Work

i =2

fs = 1
40%
done

1
sum

Worker 2
2

100%
done

sum

3

Worker 3

3

80%
done

sum

f (2) = 1

...

Worker 2

2

Worker 3

sum

sum

40%
done

f (3) = 1
100%
done

Initial
Worker 2
Assignment is done

Reassign Worker 3
Remaining is done

Wait for first reply

Wait for first reply

time

Figure 3: (Heterogeneity Aware Work Exchange Algorithm in Section 5.2) The work is initially
assigned according to the heterogeneity knowledge. The master node waits for the first reply, and
then performs work exchange reassignments. The process continues over the remaining work till
all the computations are collected.
on the heterogeneity knowledge as follows
(k,1)

Nassign =

λk N
,
λsum

∀k ∈ K̄.

(16)

(1)

(k,1)

The completion time for worker wk in the first iteration, Tk , is the time needed to process Nassign
(1)

(k,1)

data-points at a rate λk , which follows an Erlang distribution, i.e., Tk ∼ Erlang(Nassign , λk ).
Once any worker wk finishes the processing over its data chunk it feeds-back the master-node, and
declares that it is now idle by sending a completion flag f (k) = 1 as shown in Figure 3. The time
for the first iteration then is given by time when the first worker replies, i.e.,
(1)

(1)

(1)

(1)
Tcomp
= min(T1 , T2 , . . . , TK ).

(17)

The master-node then pauses the processing over all workers by broadcasting a stop flag f s = 1,
(k,1)
and gets {y (k,1) , Nleft }, ∀k ∈ K̄, where for each worker wk : y (k,1) is the latest work done before
(k,1)
receiving f s = 1 after the initial reassigning iterations i = 1, and Nleft is the number of points
not processed yet. The total number of points left after the initial reassigning iterations i = 1 is
P
(1)
(k,1)
then Nrem = K
k=1 Nleft . The reassigning process in the next iteration is done as follows: the
master node reassigns new non-overlapping portions of the remaining Nrem(1) points depending on
the values of λ for each worker using the same principle as before according to (16).
Generally, the new assignment at iteration i is:
(i−1)

(k,i)

Nassign =

λk Nrem
,
λsum

10

∀k ∈ K̄.

(18)

(i)

(i)

(i)

(i)

(i)

(k,i)

The time for iteration i is given by Tcomp = min(T1 , T2 , . . . , TK ), where Tk ∼ Erlang(Nassign , λk ).
The procedure can then be repeated for I iterations until there are no remaining points left,
(I)
Nrem = 0. The total computation time is given by the sum of the computation times over all
P
(i)
iterations Tcomp = Ii=1 Tcomp . The reassigning process imposes extra coordination overhead to
get feedback from the workers at each reassigning epoch, and it also involves extra communication
overhead since the master node needs to retransmit the new assigned points to the workers given
by (2). However, since every worker is initially assigned the expected number of points it can
process, then for large number of points we expect negligible communication, and low coordination
overheads. The complete steps of the work exchange scheme with heterogeneity knowledge are
shown in Algorithm 1 for the master’s node protocol and Algorithm 2 for the worker’s protocol.
Algorithm 1 Work exchange scheme with heterogeneity knowledge: Master node’s protocol
(k)

Initialize: Nrem = N , Nleft = 0, ∀k ∈ K̄
th do
while Nrem > Nrem
(k)
rem
Assign Nassign = λkλN
, ∀k ∈ K̄ {points assigned to each worker}
sum
(k)

(k)

Send max(Nassign − Nleft , 0) new data points to each worker wk
Broadcast f s = 0
on receiving f (k) = 1, for any k ∈ K̄
Broadcast f s = 1
(k)
Get {y (k) , Nleft }, ∀k ∈ K̄ {get feedback from each worker}
P
(k)
Find Nrem = k∈K̄ Nleft
end while

Algorithm 2 Worker node wk ’s protocol
(k)

On receiving Nassign points
Start processing
while f s == 0 and f (k) == 0 do
on completing processing set f (k) = 1
end while
(k)
Feedback {y (k) , Nleft , f (k) }
Remark 1 (Cutting Threshold). We observe that as the value of Nrem decreases over iterations,
smaller number of points are being assigned to workers. This may causing extra number of reas(I)
th , where no more reassignment
signment iterations. Instead, we add a cutting threshold Nrem ≤ Nrem
iterations are allowed, tolerating negligible delays by waiting for the slowest workers but over small
th . We note that the cutting threshold N th is a design parameter
number of remaining points Nrem
rem
and its choice impacts the overall completion time. The impact of the choice of this threshold is
discussed through simulation results in Section 7.

11

{

1,

2,

3}

Unknown

i=1

Work progress

Worker 1

Count
Remaining
Work

i =2

Count
Remaining
Work

fs = 1

Worker 1

fs = 1

100%
done

f (1) = 1

1
3

ˆ sum

Worker 2
1
3

1
3

40%
done

ˆ1

ˆ2

60%
done

ˆ sum

80%
done

ˆ3

Worker 3

ˆ sum

Worker 3

30%
done

Uniform Initial Worker 2
Assignment is done

...

Worker 2

f (3) = 1
100%
done

Reassign Worker 3 Re-estimate
Remaining is done { 1 , 2 , 3 }

Estimate
{

1,

2,

3}

Wait for first reply

time

Wait for first reply

Figure 4: (Heterogeneity Unaware Work Exchange Algorithm in Section 6) The work is uniformly
assigned at the beginning. The master node waits for the first reply, estimates the average speed of
each worker, and then reassigns the remaining work to all the workers according to the estimated
heterogeneity. The process then continues till all the computations are completed.

6

Heterogeneity Unaware Work-exchange

We next introduce a variation of the work exchange scheme, which assumes a more realistic scenario
as follows: a) the heterogeneity set, i.e., λ̄, is unknown apriori; and b) each worker is not allowed
N
any extra storage above K
points. The steps for the scheme are depicted in Figure 4. As the
master node initially does not know which worker is faster, it initially assigns equal data batches
(k,1)
N
for k ∈ K̄. We can derive an estimate of the expected extra
for the workers, i.e., Nassign = K
communication overhead for this scheme as the flow needed to restore the expected number of
points to be processed by each worker in (13) starting from the uniform initial assignment, which
is given by the following
E[Ncomm ] ≈

K
X

max

i=1




N
N λk
−
,0 .
K
λsum

(19)

Similar to the known heterogeneity case, upon receiving a completion flag f (k) = 1 from any of
the workers, the master node stops the processing over all the workers by sending f s = 1, and gets
(k,1)
the total number of points processed by each worker wk as Ndone , and hence the total remaining
P
(1)
(k,1)
points Nrem = N − K
k=1 Ndone . The computation time for the first iteration is given by
(1)

(1)

(1)

(1)
Tcomp
= min(T1 , T2 , . . . , TK ),

(1)

where Tk

(20)

∼ Erlang(N/K, λk ). Before the next reassignment, the master node estimates the

12

heterogeneity level as
(k,1)

(1)

λ̂k =

Ndone
(1)

Tcomp

,

∀k ∈ K̄.

(21)

Therefore, the new reassignments can be given as
(1)

(k,2)
Nassign

= min

(1)

N λ̂k Nrem
,
(1)
K
λ̂sum

!

,

(22)

P
(1)
(1)
where λ̂sum = K
k=1 λ̂k , and we take the minimum over those two values in order not to exceed the
N
amount of storage K
allocated to each worker. Generally for the next iterations, the heterogeneity
is estimated as
(i−1)
λ̂k

Pi−1

(k,j)
j=1 Ndone
,
(j)
T
comp
j=1

= P
i−1

∀k ∈ K̄,

(23)

while the new reassignments can be given as

(i−1)

(k,i)
Nassign

(i−1)

where Nrem
(k,i+1)
Nassign

=N−

Pi−1 PK
j=1

= min

(k,j)
k=1 Ndone .

(i−1)

Nrem
N λ̂k
,
(i−1)
K
λ̂sum

!

,

(24)

It is clear that according to (24), that the sum over all
(i)

for k ∈ K̄ may not add necessarily to Nrem , and we simply carry on the difference for the
next iteration. Algorithm 3 summarizes the master’s node protocol for the work exchange scheme
with unknown heterogeneity, and the worker node’s protocol works exactly as in Algorithm 2.
(I)
th over the remaining number of data
Furthermore, we can also add a cutting threshold Nrem ≤ Nrem
points according to Remark 1, to stop the reassigning process and reduce the level of coordination.

7

Simulation Results

In this section, we present simulation results to compare time for computation Tcomp , the extra
communication overhead Ncomm , and the level of coordination needed (number of reassignments I)
for the two proposed schemes against the oracle lower bound and the optimized baseline MDS coded
scheme. In order to model the heterogeneity, we pick λk for each worker uniformly at random with
√
√
mean µ and variance σ 2 , i.e., λk ∼ Uniform(µ − 3σ 2 , µ + 3σ 2 ), ∀k ∈ K̄, therefore, for λk ≥ 0,
we have 0 ≤ σ 2 ≤ µ2 /3. The variance σ 2 indicates the level of heterogeneity, i.e., higher σ 2 leads to
more heterogeneous workers, and when σ 2 = 0 then all the workers are homogeneous with λk = µ,
∀k ∈ K̄. In the following analysis, we run our proposed schemes for N = 106 data points over
K = 50 distributed workers. The value of the cutting threshold (see Remark 1) is given as a fraction
N
N
, and is given the value 0.01 K
by default.
of K
Comparison between the schemes: In Figure 5, we find the mean computation time Tcomp for
13

Algorithm 3 Work exchange scheme with unknown heterogeneity: Master node’s protocol
(k)

(k)

Initialize: Nrem = N , λ̂(k) = 1, Nleft = 0, Ndone = 0, ∀k ∈ K̄
th do
while Nrem > Nrem


(k)
N λ̂k Nrem
, ∀k ∈ K̄ {points assigned to each worker}
Assign Nassign = min K
,
λ̂
P (k)sum
Find Nrem = Nrem − Nassign {Points to be carried on}
(k)

(k)

Send max(Nassign − Nleft , 0) points to each worker wk
Broadcast f s = 0
on receiving f (k) = 1, for any k ∈ K̄
Broadcast f s = 1
(k)
Get {y (k) , Nleft }, ∀k ∈ K̄ {get feedback from each worker}
P
(k)
Baseline
Baseline
Baseline
MDS
Baseline
MDS
Coded
MDS
MDS
Scheme
Coded
Coded
Scheme
Scheme
Baseline
Baseline
Baseline
MDS
Baseline
MDS
Coded
MDS
Coded
MDS
Coded
Scheme
Scheme
Coded
Scheme
Scheme
Find
N
=
NCoded
+Scheme
rem
rem
k∈K̄ Nleft


Heterogeneity
Heterogeneity
Heterogeneity
Heterogeneity
Aware
Aware
Scheme
Aware
Scheme
Aware
Scheme
with
Scheme
with
Fixed
with
Fixed
Assignment
with
Fixed
Assignment
Fixed
Assignment
Assignment
Heterogeneity
Heterogeneity
Heterogeneity
Heterogeneity
Aware
Aware
Aware
Scheme
Scheme
Aware
Scheme
with
Scheme
with
Fixed
with
Fixed
with
Assignment
Fixed
Assignment
Fixed
Assignment
Assignment
(k)
(k)
(k)
(k)

Heterogeneity
Heterogeneity
Heterogeneity
Heterogeneity
Aware
Aware
Work
Aware
Work
Aware
Work
Work
Exchange
Scheme
Exchange
Scheme
Scheme
Heterogeneity
Heterogeneity
Aware
Aware
Aware
Work
Work
Aware
Exchange
Work
Exchange
Work
Exchange
Scheme
Exchange
Scheme
Scheme
Scheme
Find
N
=N
+Exchange
NExchange
−Scheme
Nleft
, ∀k ∈ Heterogeneity
K̄ Heterogeneity
assign
done
done

Heterogeneity
Heterogeneity
Heterogeneity
Heterogeneity
Unaware
Unaware
Unaware
Work
Unaware
Work
Exchange
Work
Exchange
Work
Exchange
Scheme
Exchange
Scheme
Scheme
SchemeHeterogeneity
Heterogeneity
Heterogeneity
Heterogeneity
Unaware
Unaware
Unaware
Work
Unaware
Work
Exchange
Work
Exchange
Work
Exchange
Scheme
Exchange
Scheme
Scheme
Scheme
(k)
Baseline
MDS
Coded Scheme
Oracle
Oracle
Oracle
Bound
Bound
Oracle
Bound
Bound

200 200 200 200

0

0

Homogeneous Workers
Baseline MDS Coded Scheme
200
Baseline MDS Coded Scheme Heterogeneity Aware Scheme
with
Fixed
Assignment
0 0 0 0
Heterogeneity Aware Scheme with
Fixed Assignment
Heterogeneity
Aware Work Exchange Scheme
Heterogeneity Aware Work Exchange Scheme
Heterogeneity
Heterogeneity Unaware Work Exchange
Scheme Unaware 0Work Exchange Scheme
400 400 400 400
Oracle Bound
Oracle Bound
400
400

0

400 400 400 400

Computation Time Tcomp

400
400

High
High
Heterogeneity
High
Heterogeneity
High
Heterogeneity
Heterogeneity
Homogeneous
Workers

0

0

Computation Time Tcomp

200 200 200 200

0

Heterogeneity Aware Scheme with Fixed Assignment
Heterogeneity Aware Work Exchange Scheme
Heterogeneity Unaware Work Exchange Scheme
Homogeneous
Homogeneous
Homogeneous
Homogeneous
Workers
Workers
Workers
Workers
Oracle
Bound

200 200 200 200400

200
200

00 0

Homogeneous Workers

200

200 200
200 200
Homogeneous
Workers

0

sum sum sum 0
sum

Computation Time Tcomp

0

Computation Time Tcomp

Homogeneous
Homogeneous
Homogeneous
Homogeneous
Workers
Workers
Workers
Workers

Computation Time Tcomp
Computation Time Tcomp
Computation Time Tcomp

Computation Time Tcomp
Computation Time Tcomp

Computation Time Tcomp
Computation Time Tcomp
Computation Time Tcomp

Oracle
Oracle
Oracle
Bound
Bound
Oracle
Estimate
λ̂kBound
=Bound
Ndone /Tcurrent , ∀k ∈ K̄
400 400 400 400
400 400 400 400
end while

sum sum sum sum

0

0

High
High
Heterogeneity
High
Heterogeneity
High
Heterogeneity
Heterogeneity
High
Heterogeneity
High Heterogeneity

200

0

0

sum
sum
sum
sum sum
sum sum
sum sum sum
sum
sum
sumsum
sum sum
= 200 sum sum sum
= 300
= 100

sum
sum
sumsum sum

sum sum sum sum
= 400
= 200
= 200
= 200 = 300
= 300
= 300
= 300 = 400
=
=
400
=
= 200
= 200 =
= 300
= 300
= 300
= 400
= 400
= 400
=400
100
= 100
= 100
= 100 = 200
= 400
100
= 400
100
=
= 100 = 200
K 200
K 300
K = 400
K 100
K K K K
K K K K
K K
K K K K
K K K K
K K K K
K K K K
K K
K K K
200

400
High Heterogeneity

Figure 5: Computation time of N = 106 data
points over K = 50 workers for different values of
High Heterogeneity
200
λsum , and
two heterogeneity
levels σ 2 = 0 and σ 2 = λ2sum /(6K 2 ).
0
sum

K

= 100

sum

K

= 200

sum

K

= 300

sum

K

= 400

0
the work exchange schemes
with and without heterogeneity knowledge, and compare them with the
sum
sum
sum
sum
= 200 and the heterogeneity
= 300
=
400 scheme with fixed
= 100oracle bound,
optimized MDS coded scheme,
the
aware
K
K
K
K
assignments given in (6), (7), and (15), respectively. We run the simulation for four different values
of µ̂ = λsum /K (sample mean), and two heterogeneity levels: 1) σ 2 = 0, the homogeneous case;
and 2) σ 2 = µ̂2 /6, high heterogeneity. We first notice, that both the work exchange schemes always
oracle , and a slightly higher values for the
have almost the same computation as the oracle bound Tcomp
fixed assignment scheme. Second, as µ̂ increases, the value of Tcomp decreases for all the schemes
as expected because of higher average speed for the workers. Most importantly, that Tcomp for the
MDS which equals T oracle for the
work exchange schemes are invariant of σ 2 , unlike the value of Tcomp
comp
homogeneous case, and increases for higher value of σ 2 . In fact, the redundancy introduced using
MDS codes is unnecessary for the homogeneous case since all the workers perform the same, i.e.,
L = K = 50 is the optimal value.

Effect of heterogeneity level on Ncomm and I: In Figures 6a and 6b, we plot the average

14

Number of Reassignment Iterations (I)

Normalized Extra Communication ( Ncomm
)
N

0.45
Work Exchange Scheme with Unknown Heterogeneity

0.4

Work Exchange Scheme with Heterogeneity Knowledge

0.35
0.3
0.25
0.2
0.15
0.1
0.05
0

0

100

200

300

400

500

600

700

Heterogeneity Level (Variance

800
2

900

)

(6a) Normalized extra communication versus variance (σ 2 ) for the work exchange scheme with and
without the heterogeneity knowledge.

30

Work Exchange Scheme with Unknown Heterogeneity
Work Exchange Scheme with Heterogeneity Knowledge

25

20

15

10

5

0

100

200

300

400

500

600

700

Heterogeneity Level (Variance

800
2

900

)

(6b) Number of reassignment iterations (I) needed
versus variance (σ 2 ) for the work exchange scheme
with and without the heterogeneity knowledge.

Number of Reassignment Iterations (I)

normalized extra communication Ncomm
N , and the average number of reassignment iterations I,
respectively, for the two work exchange schemes versus σ 2 . For each value of σ 2 , we generate 50
random values of the heterogeneity set λ̄ , and find the average quantities for each. The points
falling on the solid lines are the average values over the 50 readings, and the vertical lines represent
the error bars. We notice the following: 1) With heterogeneity knowledge, the average extra
communication is almost zero for any σ 2 , and that is due to the initial assignment in (16) which is
the expected number of points to be done by each worker, and hence negligible extra communication
is needed. 2) Without heterogeneity knowledge, the average extra communication is zero for zero
variance and that is according to (19), where for σ 2 = 0 we have λk /λsum = 1/K, and hence
E[Ncomm ] = 0, and as σ 2 increases E[Ncomm ] increases. 3) The two proposed schemes have an
increasing values of I as σ 2 increases, with slight lower values for the known heterogeneity case.
70

60

2

=0

50

2

= µ2 /6

40

2

= µ2 /3

30

20

10

0

0

0.002 0.004 0.006 0.008

0.01

0.012 0.014 ⇣0.016 0.018
⌘
th
Nrem
N/K

0.02

Normalized Cutting Threshold

th ) for the work exchange
Figure 7: Number of reassignments (I) versus the cutting threshold (Nrem
2
scheme with unknown heterogeneity, and different values of σ .

th on I: In case of unknown heterogeneity, we set
Effect of adding a cutting threshold Nrem

15

th in Figure 7. We can see that as N th increases, the value of I decreases for
µ = 50 and vary Nrem
rem
different values of σ 2 as shown in the figure. Furthermore, we notice that after a certain point, the
th to 0.01 N for our example of
value of I starts to saturate. Therefore, we set the default value of Nrem
K
K = 50 workers, which is sufficient to get small mean number of reassignment iterations I without
compromising the mean computation time Tcomp as we can see in Figure 5 (Tcomp is still very close
oracle ).
to Tcomp

8

Conclusion and Future Directions

In this paper, we focused on the problem of mitigating the impact of computational heterogeneity in
large-scale distributed computation. We first obtained an oracle lower bound on the expected computation time as a function of the heterogeneity parameters, which has an interesting water-filling
interpretation. Inspired by the goal of approaching the oracle lower bound, we presented the idea
of work exchange, in which the master node can perform iterative reassignments of computational
tasks to the workers. We presented two variations of the work-exchange idea: the first in which
heterogeneity knowledge is available; and a second more realistic variation when the heterogeneity
knowledge is unknown apriori, and must be estimated in an online manner. These schemes reveal
that there are fundamental tradeoffs between latency (time for computation), level of coordination
and communication between the master node and the workers. Interestingly, it was found via simulation results that the computation time of the work-exchange scheme is very close to the oracle
lower bound even when the heterogeneity is unknown apriori, in contrast to the baseline MDS
coded computation scheme when the heterogeneity levels are high. Moreover, the work exchange
approach does not require linearity of the underlying computational task (unlike coded computation
approaches), but rather assumes flexible divisions of the work into smaller independent sub-tasks.
There are several interesting directions for future work which include a) adapting the workexchange algorithms for sequential computations where the smaller sub-tasks depend on each other
as in gradient descent and its stochastic variations; b) imposing divisibility constraints where the
computational task can only be divided into bounded number of sub-tasks; and c) obtain mathematical guarantees for the proposed work exchange schemes in terms of the expected latency, as a
function of the heterogeneity levels, coordination and communication overheads.

References
[1] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica, “Spark: Cluster Computing with Working Sets,” in Proceedings of USENIX HotCloud, 2010.
[2] J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,” in
Proceedings of USENIX OSDI, 2004.
[3] J. Dean and L. A. Barroso, “The Tail at Scale,” Communications of the ACM, vol. 56, no. 2,
pp. 74–80, 2013.

16

[4] G. Ananthanarayanan, S. Kandula, A. G. Greenberg, I. Stoica, Y. Lu, B. Saha, and E. Harris,
“Reining in the Outliers in Map-Reduce Clusters using Mantri,” in Proceedings of USENIX
OSDI, 2010.
[5] M. Zaharia, A. Konwinski, A. D. Joseph, R. H. Katz, and I. Stoica, “Improving Mapreduce
Performance in Heterogeneous Environments,” in Proceedings of USENIX OSDI, 2008.
[6] G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica, “Effective Straggler Mitigation:
Attack of the Clones,” in Proceedings of USENIX NSDI, 2013.
[7] N. B. Shah, K. Lee, and K. Ramchandran, “When do Redundant Requests Reduce Latency?”
in Proceedings of the 51st Annual Allerton conference on Communication, Control, and Computing, Monticello, IL, 2013.
[8] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” IEEE Transactions on Information Theory, 2017.
[9] K. Lee, C. Suh, and K. Ramchandran, “High-dimensional coded matrix multiplication,” in
Information Theory (ISIT), 2017 IEEE International Symposium on. IEEE, 2017, pp. 2418–
2422.
[10] Q. Yu, M. Maddah-Ali, and A. Avestimehr, “Polynomial Codes: an Optimal Design for HighDimensional Coded Matrix Multiplication,” in Proceedings of Neural Information Processing
Systems Conference (NIPS), Dec. 2017.
[11] S. Li, M. Maddah-Ali, and A. A, “Coded Distributed Computing: Straggling Servers and
Multistage Dataflows,” in Proceedings of the 54th Annual Allerton conference, Sep. 2016.
[12] ——, “A Unified Coding Framework for Distributed Computing with Straggling Servers,”
CoRR, vol. abs/1609.01690, 2016.
[13] S. Dutta, V. Cadambe, and P. Grover, “Coded Convolution can Provide Arbitrarily Large
Gains in Successfully Computing before a Deadline,” in Proceedings of the IEEE International
Symposium on Information Theory (ISIT), 2017.
[14] A. Bhatele, K. Mohror, S. H. Langer, and K. E. Issacs, “There Goes the Neighborhood:
Performance Degradation Due to Nearby Jobs,” in Proceedings of ACM/IEEE International
Conference for High Performance Computing, Networking, Storage and Analysis, 2013.
[15] R. Blumofe and C. Leiserson, “Scheduling multithreaded computations by work stealing,”
Journal of the ACM (JACM), vol. 46, no. 5, pp. 720–748, 1999.
[16] Y. Abdelkader, “Computing the Moments of Order Statistics from Nonidentically Distributed
Erlang Variables,” Statistical Papers, vol. 45, no. 4, pp. 563–570, 2004.

17

