arXiv:1803.09877v2 [stat.ML] 28 Mar 2018

D RACO:
Robust Distributed Training via Redundant Gradients
Lingjiao Chen, Hongyi Wang, Zachary Charles, Dimitris Papailiopoulos
University of Wisconsin-Madison
Abstract
Distributed model training is vulnerable to worst-case system failures and adversarial compute nodes,
i.e., nodes that use malicious updates to corrupt the global model stored at a parameter server (PS). To
tolerate node failures and adversarial attacks, recent work suggests using variants of the geometric median
to aggregate distributed updates at the PS, in place of bulk averaging. Although median-based update rules
are robust to adversarial nodes, their computational cost can be prohibitive in large-scale settings and their
convergence guarantees often require relatively strong assumptions.
In this work, we present D RACO, a scalable framework for robust distributed training that uses ideas
from coding theory. In D RACO, each compute node evaluates redundant gradients that are then used by
the parameter server to eliminate the effects of adversarial updates. We present problem-independent
robustness guarantees for D RACO and show that the model it produces is identical to the one trained in the
adversary-free setup. We provide extensive experiments on real datasets and distributed setups across a
variety of large-scale models, where we show that D RACO is several times to orders of magnitude faster
than median-based approaches.

1 Introduction
Distributed and parallel implementations of stochastic optimization algorithms have become the de facto
standard in large-scale model training [LAP+ 14, RRWN11, ZCL15, AWD10, ABC+ 16, CLL+ 15, PGCC17,
CSAK14]. Due to increasingly common malicious attacks, hardware and software errors [CL+ 99, KAD+ 07,
BGS+ 17, CSX17], a nontrivial challenge in distributed machine learning is protecting against adversarial
compute nodes and failures that may affect the training process and can bias or corrupt the end model. It
is known that in these distributed setups even a single adversarial node can introduce arbitrary bias and
inaccuracies to the end models [BGS+ 17].
A recent line of work [BGS+ 17, CSX17] studies this problem under a synchronous training setup, where
a parameter server (PS) stores the model, and compute nodes evaluate gradient updates that are shipped
to the PS and applied to the global model. The aforementioned studies suggest that instead of averaging
the gradients—a standard aggregation technique—the PS can use a robust version of averaging, i.e., the
geometric median (GM). The advantage of median-based approaches is that they can be robust to up to a
constant fraction of the compute nodes being adversarial [CSX17]. However, in settings with large amounts
of data, the cost of computing the geometric median can dwarf the cost of computing a batch of gradients
[BGS+ 17], rendering it impractical for distributed deployment. Furthermore, proofs of convergence for
such systems require restrictive assumptions such as convexity, and need to be re-tailored to each different
training algorithm. A scalable distributed training framework that is robust against adversaries and can be
applied to a large family of training algorithms (e.g., mini-batch SGD, GD, coordinate descent, SVRG, etc.)
remains an open problem.
In this paper, we take a different route compared to median-based approaches and use ideas from coding
theory to ensure robustness during distributed training. We present D RACO, a general distributed training
framework that is robust against adversarial nodes and worst-case compute errors. We show that D RACO
1

g1 + g2 + g3 + g4

3

e
2g 4

g2

3g

g3 +

x1
x2
x3

+

+

g1

g1

2

g2

2g
3 +
g4

PS

x3
x4
x1

x2
x3
x4

x4
x1
x2
Adversary

Figure 1: The high level idea behind D RACO’s algorithmic redundancy. Let us assume a data set consisting
of 4 data points x1 , . . . , x4 , and let gi be the gradient of the model with respect to data point xi . In the present
setup, instead of each compute node i evaluating a single gradient gi , during D RACO’s execution each node
computes additional redundant gradients. In this example, the replication ratio is 3, and for the specific data
allocation and gradient encoding mechanism shown above, the parameter server can recover the desired
sum of gradients, i.e., g1 + g2 + g3 + g4 , from a linear combination of any 2 of the received encoded gradient
updates. This means that in the presence of any single adversary,
the PS can still recover the sum of the four

gradients. This can be done through a majority vote on all 42 = 6 possible results from all pairs of encoded
gradient updates. Although this is a simple decoding strategy, it cannot scale to a large number of compute
nodes. D RACO implements a more systematic and efficient encoding and decoding mechanism that scales
well on many machines.
can resist any s adversarial compute nodes during distributed training and it returns a model identical to
the one trained in the adversary-free setup. This allows D RACO to come with “black-box” convergence
guarantees, i.e., proofs of convergence in the adversary-free setup carry through to the adversarial setup
with no modification, unlike prior median-based approaches [BGS+ 17, CSX17]. Moreover, in median-based
approaches such as [BGS+ 17, CSX17], computing the geometric median which is performed at the PS can
dominate the overall training runtime. In D RACO most of the computational effort is carried through by the
compute nodes. This is a key factor that allows our framework to offer up to orders of magnitude faster
convergence in real distributed setups.
To design D RACO, we borrow ideas from coding theory and employ algorithmic redundancy. In standard
adversary-free distributed computation setups, during each distributed round, each of the P compute
nodes processes B/P gradients and ships their sum to the parameter server. In D RACO, each compute
node processes rB/P gradients and sends a linear combination of those to the PS. This means that D RACO
incurs a computational redundancy ratio of r. While this may seem sub-optimal, we show that under
a worst-case adversarial setup, it is information theoretically impossible to design a system that obtains
identical models to the adversary-free setup with less redundancy. Upon receiving the P gradient sums,
the PS uses a “decoding” function to remove the effect of the adversarial nodes and reconstruct the original
desired sum of the B gradients. With redundancy ratio r, we show that D RACO can tolerate up to (r − 1)/2
adversaries, which is information theoretically tight. See Fig. 1 for a toy example of D RACO’s functionality.
We present two constructions of encoding and decoding techniques that D RACO implements. The
encoding schemes are based on the fractional repetition code and cyclic repetition codes presented in
[TLDK17, RTTD17]. In contrast to previous work on stragglers and gradient codes [TLDK17, RTTD17,
CPE17], our decoders are tailored to the adversarial setting and require different approaches. Our decoding
schemes utilize an efficient majority vote style decoder and a novel Fourier decoding technique.
We note that compared to median-based techniques that can tolerate approximately a constant fraction
2

of “average case” adversaries, D RACO’s (r − 1)/2 bound on the number of “worst-case” adversaries can be
significantly smaller. However, in realistic regimes where only a constant number of nodes are malicious,
D RACO is significantly faster as we show in experiments in Section 4.
We implement D RACO in PyTorch and deploy it on distributed setups on Amazon EC2, where we
compare against median-based training algorithms on several real world datasets and various ML models.
We show that D RACO is up to orders of magnitude faster compared to GM-based approaches across a range
of neural networks, e.g., LeNet, VGG-19, AlexNet, ResNet-18, and ResNet-152, and always converges to the
correct adversary-free model, while in some cases median-based approaches do not converge.
Related Work The large-scale nature of modern machine learning has spurred a great deal of novel research
on distributed and parallel training algorithms and systems [RRWN11, DCM+ 12, AGL+ 17, JST+ 14, LWR+ 14,
MPP+ 15, CPM+ 16]. A lot of this work has focused on developing and analyzing efficient implementations
of distributed training algorithms. More recently, there has been interest in federated learning during which
training is distributed among a large number of compute nodes (e.g., edge devices), without centralized
training data [KMR15, KMY+ 16, BIK+ 16].
In some of the above distributed setups, synchronous training can suffer from straggler nodes [ZKJ+ 08],
where a few compute nodes are significantly slower than average. While early work on straggler mitigation
used techniques similar to job replication [SLR16], more recent work has employed coding theory to speed
up distributed machine learning systems [LLP+ 17, LMAA15, DCG16, DCG17, RPPA17]. Of particular note
in this recent line of work is gradient coding, a straggler mitigation method proposed in [TLDK17], which uses
codes to speedup synchronous distributed first-order methods such as mini-batch SGD [RTTD17, CPE17,
CSSS11]. Our work builds on and extends this recent line of work to the adversarial setup. We note that
mitigating stragglers is technically speaking a simpler problem compared to defending against adversarial
nodes, since in the adversarial setup we have no knowledge as to which nodes are the adversaries.
The topic of byzantine fault tolerance has been extensively studied since the early 80s [LSP82]. A few
recent studies focus on byzantine fault tolerance in the context distributed training, and show that while
average-based gradient methods are susceptible to adversarial nodes [BGS+ 17, CSX17], median-based update methods can yield good convergence results while being robust to adversarial nodes. Both [BGS+ 17]
and [CSX17] use variants of the geometric-median to improve the tolerance of first-order methods against
adversarial nodes. Unfortunately, analyzing the convergence properties of median based approaches requires
several assumptions and new proofs of convergence, as average based guarantees do not immediately transfer to the median setup. Furthermore, when the geometric median is used for aggregation, its computational
cost can entirely dominate training time in large-scale settings.
We note that the idea of using redundancy to guard against failures in computational systems has
existed for decades. Von Neumann used redundancy and majority vote operations in boolean circuits to
achieve accurate computations in the presence of noise with high probability [VN56]. These results were
further analyzed and extended in work such as [Pip88] to understand how susceptible a boolean circuit is to
randomly occurring failures. Our work can be seen as an application of the aforementioned concepts to the
context of distributed training in the face of adversity.

2 Preliminaries
Notation In the following, we will denote matrices and vectors in bold, and scalars and functions in
standard script. We will let 1m denote the m × 1 all ones vector, while 1n×m will denote the all ones n × m
matrix. We define 0m , 0n×m analogously.
Given a matrix A ∈ Rn×m , we will let Ai,j denote its entry at location (i, j). We will let Ai,· ∈ R1×m
denote its ith row, and A·,j ∈ Rn×1 will denote its jth column. Given S ⊆ {1, . . . , n}, T ⊆ {1, . . . , m}, we
will let AS,T denote the submatrix of A where we keep rows indexed by S and columns indexed by T .
Given matrices A, B ∈ Rn×m , their Hadamard product, denoted A B, is defined as the n × m matrix where
(A B)i,j = Ai,j Bi,j .

3

Distributed Training The process of training a model from data can be cast as an optimization problem
known as empirical risk minimization (ERM):
n

min
w

1X
`(w; xi )
n i=1

where xi ∈ Rm represents the ith data point, n is the total number of data points, w ∈ Rd is a parameter
vector or model, and `(·; ·) is a loss function that measures the accuracy of the predictions made by the model
on each data point.
One way to approximately solve the above ERM is through stochastic gradient descent (SGD), which
operates as follows. We initialize our parameter vector at an initial point w0 and then iteratively update it
according to the rule
wk = wk−1 − γ∇`(wk−1 ; xik ),

where ik is a random data-point index sampled from {1, . . . , n}, and γ > 0 is the learning rate.
In order to take advantage of distributed systems and parallelism, we often use mini-batch SGD instead.
In this setup, at each iteration of the algorithm, we take a (possibly random) subset Sk ⊆ {1, . . . , n} of the
data and then update our model according to
wk = wk−1 −

γ X
∇`(wk−1 ; xi ).
|Sk |
i∈Sk

Many distributed versions of mini-batch SGD work by partitioning the gradient computations across the
compute nodes in a distributed system. After computing their assigned gradients, the compute nodes then
sum them up and send this sum back to the PS. The PS uses this sum of gradients to update the model wk−1
according to the mini-batch SGD rule above.
In this work, we consider the question of how to perform each iteration of this update method in a
distributed and robust manner. Since we consider a fixed iteration, we will fix some batch (or set of points)
Sk , which after relabeling we assume equals {1, . . . , B}. We will denote ∇`(wk−1 ; xi ) by gi . The fundamental
PB
question we consider in this work is how to compute i=1 gi in a distributed and adversary-resistant manner.
We will present D RACO, a framework that can compute this summation in a distributed manner, even under
the presence of adversaries.
Remark 1. In contrast to previous works, our analysis and framework are applicable to any distributed algorithm
which requires the sum of multiple functions. Notably, our framework can be applied to common first-order methods
in machine learning, including gradient descent, variants of SGD, SVRG [JZ13], coordinate descent and various
projected or accelerated versions of these algorithms. For the sake of simplicity, our discussion in the rest of the text will
focus on mini-batch SGD.
Adversarial Compute Node Model We consider the case where a subset of size s of the P compute nodes
can act adversarially against the training process. It is known that mini-batch SGD fails to converge even
if there is only a single adversarial node [BGS+ 17]. The goal of an adversary can either be to completely
mislead the end model, or bias it towards specific areas of the parameter space. A compute node is considered
to be an adversarial node, if it does not return the prescribed gradient update given its allocated samples.
Such a node can ship back to the PS any arbitrary update of dimension equal to that of the true gradient.
In this work, we consider the strongest possible adversaries. We assume that in the worst-case an
adversarial node has access to infinite computational power, has access to the entire data set and the training
algorithm, and also has knowledge of what defense mechanism is used. Furthermore, all adversarial nodes
may collaborate with each other.

4

3

D RACO: Robust Distributed Training via Algorithmic Redundancy

In this section we formally present our main results for D RACO. The proofs are left to the appendix.
We generalize the scheme in Figure 1 to P compute nodes and B data samples. At each iteration of our
training process, we will assign the B gradients to the P compute nodes using a P × B allocation matrix
A. Here, Aj,k is 1 if node j is assigned the kth gradient gk , and 0 otherwise. Therefore, the support of Aj,· ,
denoted supp (Aj,· ), is the set of indices k of gradients evaluated by the jth compute node. For simplicity, we
will assume B = P throughout the following.
D RACO utilizes redundant computations, so it is worth formally defining the amount of redundancy
incurred. This is captured by the following definition.
Definition 1. The redundancy ratio r is defined by r :=

1
P

kAk0 .

In other words, the redundancy ratio is the average number of gradients assigned to each compute node.
We define a d × P matrix G by G , [g1 , g2 , · · · , gP ]. In other words, G has all assigned gradients as its
columns. The jth compute node first computes a d × P gradient matrix Yj , (1d Aj,· ) G using its allocated
gradients. In particular, if the kth gradient gk is allocated to the jth compute node, i.e., Aj,k 6= 0, then the
compute node computes gk as the kth column of Yj . Otherwise, it sets the k-th column of Yj to be 0d .
The jth compute node is equipped with an encoding function Ej that maps the d × P matrix Yj of
its assigned gradients to a single d-dimensional vector. After computing its assigned gradients, the jth
compute node sends zj , Ej (Yj ) to the PS. If the jth node is adversarial then it instead sends zj + nj to
the PS, where nj is an arbitrary d-dimensional vector. We let E be the set of local encoding functions, i.e.,
E = {E1 , E2 , · · · , EP }.

Parameter Sever: Decoding and Model Update

Model Update

D
At most s adversarial
updates

E1

E2

x1
x2
x3

x2
x3
x4

EP

...

1

xP 1
xP

x1

EP
xP

x1
x2

Compute nodes: Gradient Evaluations and Encoding

Figure 2: During D RACO each compute node is allocated a subset of the data set, in a systematic way that we
define in Section 3. Each compute node will compute redundant gradients which will then be encoded by
a local encoder function Ei . After encoding, each compute node sends an update vector to the parameter
server. These received vectors then pass through a decoder that detects where the adversaries are and
removes their effects from the updates. This way the output of the decoder is the full sum of the gradients
originally intended to be received at the PS. The PS then applies the updates to the parameter model and the
algorithm continues on to its next iteration.

5

We define a d × P matrix ZA,E,G by ZA,E,G , [z1 , z2 , · · · , zP ], and we define a d × P matrix N by N ,
[n1 , n2 , · · · , nP ]. Note that at most s columns of N are non-zero.
Under this notation, after all updates are finished the PS receives a d × P matrix R given by R ,
ZA,E,G + N. The PS then computes a single d-dimensional update gradient vector u , D(R) using some
decoder function D.
The overall system in D RACO is therefore determined by the tuple (A, E, D). In other words, we get to
choose how to assign gradients by designing A, how each compute node should locally amalgamate its
gradients by designing E, and how the PS should decode the output of all P compute nodes by designing D.
The process of D RACO is illustrated in Figure 2.
This framework of (A, E, D) encompasses both the framework of distributed SGD and the GM approach.
For instance, in distributed mini-batch SGD, we assign 1 gradient to each compute node. After relabeling, we
can assume that we assign gi to compute node i. Therefore, A is simply the identity matrix IP . The matrix Yj
therefore contains gj in column j and 0 in all other columns. The local encoding function Ej simply returns
gj by computing Ej (Yj ) = Yj 1P = gj , which it then sends to the PS. The decoding function now depends
on the algorithm. For vanilla mini-batch SGD, the PS takes the average of the gradients, while in the GM
approach, it takes a geometric median of the gradients.
In order to guarantee convergence, we want to ensure that D RACO exactly recovers the desired gradient,
regardless of the behavior of the adversarial nodes. In other words, we want D RACO to protect against worstcase adversaries. Formally, we want the PS to always obtain the sum of all gradients, i.e., the d-dimensional
vector G1P , via D RACO with any s adversarial nodes. A formal definition is given below.
Definition 2. D RACO with (A, E, D) can tolerate s adversarial nodes, if for any N = [n1 , n2 , · · · , nP ] such that
|{j : nj 6= 0}| ≤ s, we have D(ZA,E,G + N) = G1P .
Remark 2. Suppose that we can successfully defend against s adversaries. Then this means that after each distributed
iteration we can recover the model update of the distributed algorithm as if we were under the adversary-free setup.
This implies that any guarantees of convergence in the adversary-free case transfer to the adversarial case.
Redundancy Bound We first study how much redundancy is required if we want to exactly recover the
correct sum of gradients per iteration in the pressence of s adveraries. We give a lower bound on the amount
of redundancy needed below.
Theorem 1. Suppose a selection of gradient allocation, encoding, and decoding mechanisms (A, E, D) can tolerate s
adversarial nodes. Then its redundancy ratio r must satisfy r ≥ 2s + 1.
The above result is information theoretic, in the sense that it implies that regardless of how the compute
node encodes and how the PS decodes, each data sample has to be replicated at least 2s + 1 times to defend
against s adversarial nodes.
Remark 3. Suppose that a selection of gradient allocation, encoding, and decoding mechanisms (A, E, D) can tolerate
any s adversarial nodes. By Theorem 1, this implies that on average, each compute node encodes at least (2s + 1)
d-dimensional vectors. Therefore, if the encoding has linear complexity, then each encoder requires (2s + 1)d operations
in the worst-case. If the decoder D has linear time complexity, then it requires at least P d operations in the worst case,
as it needs to use the d-dimensional input from all P compute nodes. This linear-time encoding and decoding gives a
computational cost of O(P d) in general, which is significantly less than that of the GM approach in [BGS+ 17], which
requires O(P 2 (d + log P )) operations.
Optimal Coding Schemes A natural question is, can we achieve the optimal redundancy bound with linear-time
encoding and decoding? More formally, can we design a tuple (A, E, D) that has redundancy ratio r = 2s + 1
and computation complexity O((2s + 1)d) at the compute node and O(P d) at the PS? We give a positive
answer by presenting two coding approaches that match the above bounds. The encoding methods are
based on the fractional repetition code and the cyclic repetition codes in [TLDK17, RTTD17].

6

Fractional Repetition Code Suppose 2s + 1 divides P . The fractional repetition code (derived from
[TLDK17]) works as follows. We first divide all compute nodes into r = 2s + 1 groups. We assign the nodes
in a group to each compute the same sum of gradients. Let ĝ denote the desired sum of gradients per
iteration. In order to decode the outputs returned by the compute nodes in the same group, the PS uses
majority vote to select one value. This guarantees that as long as fewer than half of the nodes in a group are
adversarial, the majority procedure will return the correct ĝ.
Formally, the repetition code (ARep , E Rep , DRep ) is defined as follows. We will let ARep be a block
diagonal matrix whose diagonal elements are given by all 1 matrices 1r×r , i.e.,


1r×r 0r×r 0r×r · · · 0r×r 0r×r
0r×r 1r×r 0r×r · · · 0r×r 0r×r 


ARep =  .
..
..
..  .
..
..
 ..
.
.
.
.
. 
0r×r

0r×r

···

0r×r

0r×r

1r×r



The jth compute node first computes all its allocated gradients YRep
= 1d ARep
j
j,·

G. Its encoder

EjRep (YRep
)
j

function simply takes the summation of all the allocated gradients. That is,
= YRep
1P . It then
j
Rep
Rep
sends zj = Ej (Yj ) to the PS.
The decoder works by first finding the majority vote of the output of each compute node that was
assigned the same gradients. For instance, since the first r compute nodes were assigned the same gradients,
it finds the majority vote of [z1 , . . . , zr ]. It does the same with each of the blocks of size r, and then takes the
sum of the P/r majority votes. We note that our decoder here is different compared to the one used in the
straggler mitigation setup of [TLDK17]. Our decoder follows the concept of majority decoding similarly to
[VN56, Pip88].

P Pr
Maj R·,(`·(r−1)+1):(`·r) , where Maj (·) denotes the majority
Formally, DRep is given by DRep (R) = `=1
vote function and R is the d × P matrix received from all compute nodes. While a naive implementation of
majority vote scales quadratically with the number of compute nodes P , we instead use a streaming version
of majority vote [BM91], the complexity of which is linear in P . Thus, the following result is obtained.
Theorem 2. Suppose 2s + 1 divides P . Then the repetition code (ARep , E Rep , DRep ) with r = 2s + 1 can tolerate
any s adversaries, achieves the optimal redundancy ratio, and has linear-time encoding and decoding.
Cyclic Code Next we describe a cyclic code whose encoding method comes from [TLDK17] and is similar to
that of [RTTD17]. We denote the cyclic code, with encoding and decoding functions, by (ACyc , E Cyc , DCyc ).
The cyclic code provides an alternative way to tolerate adversaries in distributed setups. We will show
that the cyclic code also achieves the optimal redundancy ratio and has linear-time encoding and decoding.
Another difference between the cyclic repetition code and the is that in the cyclic code, the compute nodes
will compute and transmit complex vectors, and the decoding function will take as input these complex
vectors.
To better understand the cyclic code, imagine that all P gradients we wish to compute are put in a
circle. Since there are P starting positions, there are P possible ways to pick a sequence consisting of 2s + 1
clock-wise consecutive gradients in the circle. Assigning each sequence of gradients to each compute node
leads to redundancy ratio r = 2s + 1. Formally, its allocation matrix is
2s + 1
}|
{
z

1 1 ··· 1 1 0
0 ··· 0 0
0 1
1 ··· 1 1
0 · · · 0 0


 ..
..
..
..
.. . . . .
..
.. .. 
.

.
.
.
.
.
.
.
.
.


.
0
0
·
·
·
0
0
1
1
·
·
·
1
1
ACyc = 


1 0

0
·
·
·
0
0
1
·
·
·
1
1


.

.
.
.
.
.
.
.
.
.
..
..
..
..
.. ..
..
.. .. 
 ..
1 ··· 1
1 0 0 ··· 0 0 1
|
{z
}
2s

7

In the cyclic code, each compute node computes a linear combination of its assigned gradients. This
can be viewed as a generalization of the repetition code’s encoder. Formally,
wewill construct some matrix


Cyc
W ∈P ×P such that ∀j, `, ACyc
= 1d ACyc
j,·
j,` 6= 0 implies Wj,` = 0. We then let Yj

computed at compute node j. The local encoding function
X

EjCyc (YCyc
)=
j

=
=

`:k[YCyc
]
j

k0 6=0

n h
X

i

·,`

YCyc
j

`=1
YCyc
W`,j
j

G denote the gradients

EjCyc

·,`

is defined by
i
h
YCyc
W`,j
j
·,`

W`,j

= GW·,j .
After performing this local encoding, the jth compute node then sends zCyc
, EjCyc (YCyc
) to the PS. Let
j
j
ZA

Cyc

,E Cyc ,G

Cyc

Cyc
= [zCyc
, zCyc
, · · · , zCyc
that ZA
1
2
P ]. Then one can verify from the definition of Ej

,E Cyc ,G

=

ACyc ,E Cyc ,G

GW. The received matrix at the PS now becomes R
=Z
+ N = GW + N.
In order to decode, the PS needs to detect which compute nodes are adversarial and recover the correct
gradient summation from the non-adversarial nodes. We note that methods to do the latter alone in the
presence of straggler nodes was presented in [TLDK17] and [RTTD17]. Suppose there is a function φ(·) that
can compute the adversarial node index set V . We will later construct φ explicitly. Let U be the index set of
the non-adversarial nodes. Suppose that the span of W·,U contains 1P . Thus, we can obtain a vector b by
solving W·,U b = 1P . Finally, since U is the index set of non-adversarial nodes, for any j ∈ U , we must have
nj = 0. Thus, we can use RCyc
·,U b = (GW + N)·,U b = GW·,U b = G1P . The decoder function is given formally
in Algorithm 1.
Cyc

Algorithm 1 Decoder Function DCyc .
Input : Received d × P matrix RCyc
Output : Desired gradient summation uCyc
V = φ(R) // Locate the adversarial node indexes.
U = {1, 2, · · · , P } − V . // Non-adversarial node indexes
Find b by solving W·,U b = 1P
Compute and return uCyc = R·,U b

In order to make this approach work, we need to design a matrix W and the index location function φ(·)
such that (i) For all j, k, Aj,k = 0 =⇒ Wj,k = 0 and the span of W·,U contains 1P , and (ii) φ(·) can locate the
adversarial nodes.
Let us first construct W. Let C be a P × P inverse discrete Fourier transformation (IDFT) matrix, i.e.,


1
2πi
Cjk = √ exp
(j − 1)(k − 1) , j, k = 1, 2, · · · , P.
P
P
Let CL be the first P − 2s rows of C and CR be the last 2s rows. Let αj be the set of row indices of the
Cyc
zero entries in ACyc
·,j , i.e., αj = {k : Aj,k = 0}. Note that CL is a (P − 2s) × P Vandermonde matrix and
thus any P − 2s columns of it are linearly independent.
Since
|αj | = P − 2s − 1, we can obtain a P − 2s − 1

dimensional vector qj uniquely by solving 0 = qj 1 · [CL ]·,αj . Construct a P × (P − 2s − 1) matrix




Q , q1 q2 · · · qP and a P × P matrix W , Q 1P · CL . One can verify that (i) each row of W has
the same support as the allocation matrix ACyc and (ii) the span of any P − 2s + 1 columns of W contains 1P ,
summarized as follows.
8

Lemma 3. For all j, k, Aj,k = 0 ⇒ Wj,k = 0. For any index set U such that |U | ≥ P − (2s + 1), the column span of
W·,U contains 1P .
The φ(·) function works as follows. Given the d × P matrix RCyc received from the compute nodes, we
first generate a 1 × d random vector f ∼ N (11×d , Id ), and then compute [hP −2s , hP −2s−1 , · · · , hP −1 ] , fRC†R 1 .
We then obtain a vector β = [β0 , β1 , · · · , βs−1 ]T by solving


hP −s−1
hP −s−2


 ...
hP −2s

hP −s
hP −s−1
...
hP −s+1

...
...
..
.
...


 

hP −2
β0
hP −1




hP −3   β1  hP −2 

  .  =  . .
..
  ..   .. 
.
hP −s+1
βs−1
hP −s

Ps−1
We then compute h` = u=0 βu h`+u−s , where ` = 0, 1, · · · , P − 2s − 1 and h` = hP +` . Once the vector
h , [h0 , h1 , · · · , hP −1 ] is obtained, we can compute the IDFT of h, denoted by t , [t0 , t1 , · · · , tP −1 ]. The
returned index set V = {j : tj+1 6= 0}. The following lemma shows the correctness of φ(·).
Lemma 4. Suppose N = [n1 , n2 , · · · , nP ] satisfies |{j : knj k0 6= 0}| ≤ s. Then φ(RCyc = φ(GW + N) = {j :
knj k0 6= 0} with probability 1.
Finally we can show that the cyclic code can tolerate any s adversaries and also achieves redundancy
ratio and has linear-time encoding and decoding.
Theorem 5. The cyclic code (ACyc , E Cyc , DCyc ) can tolerate any s adversaries with probability 1 and achieves the
redundancy ratio lower bound. For d  P , its encoding and decoding achieve linear-time computational complexity.
Note that the cyclic code requires transmitting complex vectors GW which potentially doubles the
bandwidth requirement. To handle this problem, one can transform the original real gradient G ∈ Rd×P into
a complex gradient Ĝ ∈ Cdd/2e×P by letting its ith component have real part Gi and complex part Gdd/2e+i .
Then the compute nodes only need to send ĜW. Once the PS recovers ûCyc , Ĝ1P , it can simply sum the
real and imaginary parts to form the true gradient summation, i.e., uCyc = Re(ûCyc ) + Im(ûCyc ) = G1P .

4

Experiments

In this section we present an empirical study of D RACO and compare it to the median-based approach in
[BGS+ 17] and [CSX17] under different adversarial models and real distributed environments. The main
findings are as follows: 1) For the same training accuracy, D RACO is up to orders of magnitude faster
compared to the GM-based approach; 2) In some instances, the GM approach [BGS+ 17, CSX17] does not
converge, while D RACO converges in all of our experiments, regardless of which dataset, machine learning
model, and adversary attack model we use; 3) Although D RACO is faster than GM-based approaches, its
runtime can sometimes scale linearly with the number of adversaries due to the algorithmic redundancy
needed to defend against adversaries.
Implementation and Setup We compare vanilla mini-batch SGD to both D RACO-based mini-batch SGD
and GM-based mini-batch SGD [BGS+ 17, CSX17]. In mini-batch SGD, there is no data replication and
each compute node only computes gradients sampled from its partition of the data. The PS then averages
all received gradients and updates the model. In GM-based mini-batch SGD, the PS uses the geometric
median instead of average to update the model. We have implemented all of those in PyTorch [PGC+ 17]
with MPI4py [DPKC11] deployed on the m4.2/4/10xlarge instances in Amazon EC2. We conduct our
experiments on various adversary attack models, datasets, learning problems and neural network models.
1†

denotes transpose conjugate.

9

Adversarial Attack Models We consider two adversarial models. First, we consider the “reversed gradient"
adversary, where adversarial nodes that were supposed to send g to the PS instead send −cg, for some c > 0.
Next, we consider a “constant adversary" attack, where adversarial nodes always send a constant multiple κ
of the all-ones vector to the PS with dimension equal to that of the true gradient. In our experiments, we set
c = 100 for the reverse gradient adversary, and κ = −100 for the constant adversary. In either setup, at each
iteration, s nodes are randomly selected to act as adversaries.

60
40
20

0 1 2 3 4 5 6 7 8
Time Cost (min) 1e2

40
20

0.0 0.2 0.4 0.6 0.8 1.0 1.2
Time Cost (min) 1e3
(e) MNIST,FC,Const

0.0 0.2 0.4 0.6 0.8 1.0
Time Cost (min) 1e3

90
80
70
60
50
40
30
20
10
0.0 0.2 0.4 0.6 0.8
Time Cost (min) 1e4

(f) MNIST,LeNet,Const

(g) Cifar10,ResNet18,Const

0 1 2 3 4 5 6 7
Time Cost (min) 1e2

(d) MR,CRN,Rev Grad

100
90
80
70
60
50
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
Time Cost (min) 1e3

Testset Accuracy (%)

Testset Accuracy (%)

60

100
90
80
70
60
50

(b) MNIST,LeNet,Rev Grad (c) Cifar10,ResNet18,Rev Grad

100
80
60
40
20

80

0 1 2 3 4 5 6 7
Time Cost (min) 1e3

Testset Accuracy (%)

(a) MNIST,FC,Rev Grad

0.0 0.2 0.4 0.6 0.8
Time Cost (min) 1e3

90
80
70
60
50
40
30
20
10

adversaries: 2.2% (Proposed Cyclic)
adversaries: 6.4% (Proposed Cyclic)
adversaries: 11.1% (Proposed Cyclic)

Testset Accuracy (%)

100
80
60
40
20

80

Testset Accuracy (%)

adversaries: 2.2% (Proposed Rep)
adversaries: 6.7% (Proposed Rep)
adversaries: 11.1% (Proposed Rep)

Testset Accuracy (%)

adversaries: 2.2% (GM)
adversaries: 6.7% (GM)
adversaries: 11.1% (GM)

Testset Accuracy (%)

Testset Accuracy (%)

adversaries: 2.2% (SGD)
adversaries: 6.4% (SGD)
adversaries: 11.1% (SGD)

(h) MR,CRN,Const

Figure 3: Convergence rates of D RACO, GM, and vanilla mini-batch SGD, on (a) MNIST on FC with reverse
gradient adversaries, (b) MNIST on LeNet with reverse gradient adversaries, (c) Cifar10 on ResNet-18 with
reverse gradient adversaries, (d) MR on CRN with reverse gradient adversaries, (e) MNIST on FC with
constant adversaries, (f) MNIST on LeNet with constant adversaries, (g) Cifar10 on ResNet-18 with constant
adversaries, and (h) MR on CRN with constant adversaries.
End-to-end Convergence Performance We first evaluate the end-to-end convergence performance of
D RACO, using both the repetition and cyclic codes, and compare it to ordinary mini-batch SGD as well as the
GM approach. The datasets and their associated learning models are summarized in Table 1. We use fully
connected (FC) neural networks and LeNet [LBBH98] for MNIST, ResNet-18 [HZRS16] for Cifar 10 [KH09],
and CNN-rand-non-static (CRN) model in [Kim14] for Movie Review (MR) [PL05].
The experiments were run on a cluster of 45 compute nodes instantiated on m4.2xlarge instances. At each
iteration, we randomly select s = 1, 3, 5 (2.2%, 6.7%, 11.1% of all compute nodes) nodes as adversaries. All
three methods are trained for 10,000 distributed iterations. Figure 3 shows how the testing accuracy varies
with training time. Tables 2, 3, and 4 give a detailed account of the speedups of D RACO compared to the GM
approach, where we run both systems until they achieve the same designated testing accuracy.
First, as expected, ordinary mini-batch may not converge even if there is only one adversary. Second,
under the reverse gradient adversary model, D RACO converges several times faster than the GM approach,
using both the repetition and cyclic codes. In fact, as shown in the speedup tables, both the repetition and
the cyclic code versions of D RACO achieve up to more than an order of magnitude speedup compared to the
GM approach. We suspect that this is because the computation of the GM is extremely expensive compared
to the encoding and decoding overhead of D RACO.
10

Table 1: The datasets used, their associated learning models and corresponding parameters.
Dataset

MNIST

Cifar10

MR

# data points

70,000

60,000

10,662

Model

FC/LeNet

ResNet-18

CRN

# Classes

10

10

2

# Parameters

1,033k / 431k

1,1173k

154k

Optimizer

SGD

SGD

Adam

Learning Rate

0.01 / 0.01

0.1

0.001

Batch Size

720 / 720

180

180

Table 2: Speedups (i.e., X times faster) of D RACO (Repetition/Cyclic Codes) over GM when using a fullyconnected neural network on the MNIST dataset. We run both methods until they reach the same specified
testing accuracy. In the table ‘const’ and ‘rev grad’ refer to the two types of adversarial updates.
Test Accuracy

80%

85%

88%

90%

2.2% const

3.4/2.7

3.5/2.8

4.8/3.9

4.1/3.1

6.7% const

2.7/2.0

4.1/3.1

6.0/4.6

5.6/4.1

11.1% const

2.9/2.2

4.8/3.7

6.1/4.7

5.3/3.8

2.2% rev grad

2.2/1.9

2.4/2.2

4.1/3.7

3.2/2.9

6.7% rev grad

3.1/2.5

3.3/3.1

5.5/4.8

4.5/3.7

11.1% rev grad

2.7/2.3

3.0/2.6

3.1/2.7

3.1/2.6

Table 3: Speedups of D RACO (with both repetition and cyclic codes) over GM when using ResNet-18 on
Cifar10. We run both methods until they reach the same specified testing accuracy. Here ∞ means that the
GM approach failed to converge to the same accuracy reached by D RACO.
Test Accuracy
80%
85%
88%
90%
2.2% rev grad

2.6/2.0

3.3/2.6

4.2/3.3

6.7% rev grad

2.8/2.2

3.4/2.7

4.3/3.4

11.1% rev grad

4.1/3.3

4.2/3.2

5.5/4.4

∞/∞
∞/∞
∞/∞

Table 4: Speedups of D RACO (with both repetition and cyclic codes) over GM when using CRM on MR. We
run both methods until they reach the same specified testing accuracy.
Test Accuracy
95%
96%
98%
98.5%
2.2% rev grad

5.4/4.2

5.6/4.3

9.7/7.4

12/9.0

6.7% rev grad

6.4/4.5

6.3/4.5

11/8.1

19/13

11.1% rev grad

7.5/4.7

7.4/4.6

12/8

19/12

11

Under the constant adversary model, the GM approach sometimes failed to converge while D RACO still
converged in all of our experiments. This reflects our theory, which shows that D RACO always returns a
model identical to the model trained by the ordinary algorithm in an adversary-free environment. One
reason why the GM approach may fail to converge is that by using the geometric median, it is actually losing
information about a subset of the gradients. Under the constant adversary model, the PS effectively gains no
information about the gradients computed by the adversarial nodes, and cannot recover the desired optimal
model.
Another reason that GM may not converge may be because theoretical convergence guarantees of GM
require certain assumptions on the underlying models, such as convexity. Since neural networks are generally
non-convex, we have no guarantees that GM converges in these settings. It is worth noting that GM may
also not converge if we were to use an algorithm such as L-BFGS or accelerated gradient descent, as the
choice of algorithm is separate from the underlying properties of the neural network models. Nevertheless,
D RACO still converges for such algorithms.

adversaries 11.1% GM

adversaries 11.1% Rep

adversaries 11.1% SGD

adversaries 11.1% Cyclic

101
100

102

Time Per Iteration (sec)

Time Per Iteration (sec)

Time Per Iteration (sec)

102
102

101

101

100

100

10−1

10−1

Comp

Comm

Encode

Decode

Comp

(a) ResNet-152, Rev Grad

Comm

Encode

Decode

Comp

(b) VGG-19, Rev Grad

Comm

Encode

Decode

(c) AlexNet, Rev Grad

101
100

10−1

102

Time Per Iteration (sec)

Time Per Iteration (sec)

Time Per Iteration (sec)

102
102

101

101

100

100

10−1

Comp

Comm

Encode

(d) ResNet-152, Const

Decode

Comp

Comm

Encode

(e) VGG-19, Const

Decode

Comp

Comm

Encode

Decode

(f) AlexNet, Const

Figure 4: Empirical Per Iteration Time Cost on Large Models with 11.1% adversarial nodes (a): reverse
gradient adversary on ResNet-152, (b): reverse gradient adversary on VGG-19, (c): reverse gradient adversary
on AlexNet, (d): constant adversary on ResNet-152, (e): constant adversary on VGG-19, (f): constant
adversary on AlexNet
Per iteration cost of D RACO We provide empirical per iteration costs of applying D RACO to three large
state-of-the-art deep networks, ResNet-152, VGG-19, and AlexNet [HZRS16, SZ14, KSH12]. The experiments
provided here are run on 46 real instances (45 compute nodes with 1 PS) on AWS EC2. For ResNet-152
and VGG-19, m4.4xlarge (equipped with 16 cores with 64 GB memory) instances are used while AlexNet
experiments are run on m4.10xlarge (40 cores with 160 GB memory) instances given the high memory
cost during training. We use a batch size of B = 180 and split the data among compute nodes. Therefore,
each compute node is assigned B
n = 4 data points per iteration. We use the Cifar10 dataset for all the
12

aforementioned networks. For networks like AlexNet that were not designed for small images, we resize
the Cifar10 images to fit the network. As shown in Figure 4, with s = 5, the encoding and decoding time
of D RACO can be several times larger than the computation time of ordinary SGD, though SGD may not
converge in adversarial settings. Nevertheless, D RACO is still several times faster than GM.
Table 5: Averaged Per Iteration Time Costs on ResNet-152 with 11.1% adversary
Time Cost (sec)

Comp

Comm

Encode

Decode

GM const

1.72

39.74

0

212.31

Rep const

20.81

39.36

0.24

7.74

SGD const

1.64

27.99

0

0.09

Cyclic const

23.08

39.36

5.94

6.64

GM rev grad

1.73

43.98

0

161.29

Rep rev grad

20.71

42.86

0.29

7.54

SGD rev grad

1.69

36.27

0

0.09

Cyclic rev grad

23.08

42.86

5.95

6.65

Table 6: Averaged Per Iteration Time Costs on VGG-19 with 11.1% adversary
Time Cost (sec)

Comp

Comm

Encode

Decode

GM const

0.26

12.47

0

74.63

Rep const

2.59

12.91

0.20

3.03

SGD const

0.25

6.9

0

0.03

Cyclic const

3.08

12.91

4.01

4.30

GM rev grad

0.26

14.57

0

39.02

Rep rev grad

2.55

14.66

0.20

3.04

SGD rev grad

0.25

7.15

0

0.03

Cyclic rev grad

3.07

14.66

4.02

3.65

Table 5, 6 and 7 provide the detailed cost of the runtime of each component of the algorithm in training
ResNet-152, VGG-19 and AlexNet, respectively. While the communication cost is high in both D RACO and
the GM method, the decoding time of the GM approach, i.e., its geometric median update at the PS, is
prohibitively high. Meanwhile, the encoding and decoding overhead of D RACO is relatively negligible in
these cases.
Effects of number of adversaries We also analyze how the number of adversaries affects the performance
of D RACO. We ran Cifar10 on ResNet-18 with 15 compute nodes, varying the number of adversaries s from 1
to 7. For these experiments, we used the constant adversary model. For the repetition code, we adapted
the group size based on s while in the cyclic code we always took 2s + 1. Figure 5 shows the total runtime
cost of D RACO does not increase significantly as the number of adversaries increase. This is likely due to
the fact that even at s = 7, the communication cost (which is not affected by the number of stragglers) is the
dominant cost of the algorithm.

13

Table 7: Averaged Per Iteration Time Costs on AlexNet with 11.1% adversarial nodes.
Time Cost (sec)

Comp

Comm

Encode

Decode

GM const

0.37

27.40

0

275.08

Rep const

4.16

30.71

0.67

10.65

SGD const

0.35

25.72

0

0.14

Cyclic const

3.67

30.71

13.55

12.54

GM rev grad

0.36

28.10

0

163.48

Rep rev grad

4.15

31.76

0.67

9.98

SGD rev grad

0.35

26.76

0

0.11

Cyclic rev grad

3.66

31.755

13.55

12.54

160

300

150
Time Cost (sec)

Time Cost (sec)

250

140

200

130

150

120

100

110
100 6.7 13.3 20 26.6 33.3 40 46.7
Percentage of Aversarial Nodes (%)

50 6.7 13.3 20 26.6 33.3 40 46.7
Percentage of Aversarial Nodes (%)
(a) Repetition Code

(b) Cyclic Code

Figure 5: Time Cost to Reach 70% Test set Accuracy with Cifar10 dataset run with ResNet-18 on cluster 15
computation nodes varying Percentage of Adversarial Nodes from 6.7% to 46.7% with Constant Adversary
(a) Repetition Code and (b) Cyclic Code

14

5 Conclusion and Open Problems
In this work we presented D RACO, a framework for robust distributed training via algorithmic redundancy.
D RACO is robust to arbitrarily malicious compute nodes, while being orders of magnitude faster than
state-of-the-art robust distributed systems. We give information–theoretic lower bounds on how much
redundancy is required to resist adversaries while maintaining the correct update rule, and show that D RACO
achieves this lower bound. There are several interesting future directions.
First, D RACO is designed to output the same model with or without adversaries. However, slightly
inexact model updates often do not decrease performance noticeably. Therefore, we might ask whether we
can either (1) tolerate more stragglers or (2) reduce the computational cost of D RACO by only approximately
recovering the desired gradient summation. Second, while we give two relatively efficient methods for
encoding and decoding, there may be others that are more efficient for use in distributed setups.

Acknowledgement
This work was supported in part by a gift from Google and AWS Cloud Credits for Research from Amazon.
We thank Jeffrey Naughton and Remzi Arpaci-Dusseau for invaluable discussions and feedback on earlier
drafts of this paper.

References
[ABC+ 16] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu
Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for
large-scale machine learning. In OSDI, volume 16, pages 265–283, 2016.
[AGL+ 17] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd:
Communication-efficient sgd via gradient quantization and encoding. In Advances in Neural
Information Processing Systems, pages 1707–1718, 2017.
[AWD10]

Alekh Agarwal, Martin J Wainwright, and John C Duchi. Distributed dual averaging in networks.
In Advances in Neural Information Processing Systems, pages 550–558, 2010.

[BGS+ 17]

Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al. Machine learning with adversaries:
Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, pages
118–128, 2017.

[BIK+ 16]

Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan,
Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for
federated learning on user-held data. arXiv preprint arXiv:1611.04482, 2016.

[BM91]

Robert S Boyer and J Strother Moore. Mjrty—a fast majority vote algorithm. In Automated
Reasoning, pages 105–117. Springer, 1991.

[CL+ 99]

Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99,
pages 173–186, 1999.

[CLL+ 15]

Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang, Minjie Wang, Tianjun Xiao, Bing Xu,
Chiyuan Zhang, and Zheng Zhang. Mxnet: A flexible and efficient machine learning library for
heterogeneous distributed systems. arXiv preprint arXiv:1512.01274, 2015.

[CPE17]

Zachary Charles, Dimitris Papailiopoulos, and Jordan Ellenberg. Approximate gradient coding
via sparse random graphs. arXiv preprint arXiv:1711.06771, 2017.

15

[CPM+ 16] Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting
distributed synchronous sgd. arXiv preprint arXiv:1604.00981, 2016.
[CSAK14] Trishul M Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam:
Building an efficient and scalable deep learning training system. In OSDI, volume 14, pages
571–582, 2014.
[CSSS11]

Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms
via accelerated gradient methods. In Advances in neural information processing systems, pages
1647–1655, 2011.

[CSX17]

Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial
settings: Byzantine gradient descent. arXiv preprint arXiv:1705.05491, 2017.

[DCG16]

Sanghamitra Dutta, Viveck Cadambe, and Pulkit Grover. Short-dot: Computing large linear
transforms distributedly using coded short dot products. In Advances In Neural Information
Processing Systems, pages 2100–2108, 2016.

[DCG17]

Sanghamitra Dutta, Viveck Cadambe, and Pulkit Grover. Coded convolution for parallel and
distributed computing within a deadline. In Information Theory (ISIT), 2017 IEEE International
Symposium on, pages 2403–2407. IEEE, 2017.

[DCM+ 12] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior,
Paul Tucker, Ke Yang, Quoc V Le, et al. Large scale distributed deep networks. In NIPS, pages
1223–1231, 2012.
[DPKC11] Lisandro D Dalcin, Rodrigo R Paz, Pablo A Kler, and Alejandro Cosimo. Parallel distributed
computing using python. Advances in Water Resources, 34(9):1124–1139, 2011.
[HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image
recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages
770–778, 2016.
[JST+ 14]

Martin Jaggi, Virginia Smith, Martin Takác, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, and Michael I Jordan. Communication-efficient distributed dual coordinate ascent. In
NIPS, pages 3068–3076, 2014.

[JZ13]

Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance
reduction. In Advances in Neural Information Processing Systems, pages 315–323, 2013.

[KAD+ 07] Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva:
speculative byzantine fault tolerance. In ACM SIGOPS Operating Systems Review, volume 41,
pages 45–58. ACM, 2007.
[KH09]

Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images.
2009.

[Kim14]

Yoon Kim. Convolutional neural networks for sentence classification.
arXiv:1408.5882, 2014.

[KMR15]

Jakub Konečnỳ, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed
optimization beyond the datacenter. arXiv preprint arXiv:1511.03575, 2015.

arXiv preprint

[KMY+ 16] Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh,
and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv
preprint arXiv:1610.05492, 2016.

16

[KSH12]

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep
convolutional neural networks. In Advances in neural information processing systems, pages 1097–
1105, 2012.

[LAP+ 14] Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski,
James Long, Eugene J Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the
parameter server. In OSDI, volume 14, pages 583–598, 2014.
[LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied
to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
[LLP+ 17]

Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, and Kannan
Ramchandran. Speeding up distributed machine learning using codes. IEEE Transactions on
Information Theory, 2017.

[LMAA15] Songze Li, Mohammad Ali Maddah-Ali, and A Salman Avestimehr. Coded mapreduce. In
Communication, Control, and Computing (Allerton), 2015 53rd Annual Allerton Conference on, pages
964–971, 2015.
[LSP82]

Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM
Transactions on Programming Languages and Systems (TOPLAS), 4(3):382–401, 1982.

[LWR+ 14] Ji Liu, Steve Wright, Christopher Re, Victor Bittorf, and Srikrishna Sridhar. An asynchronous
parallel stochastic coordinate descent algorithm. In Proceedings of ICML 14, pages 469–477, 2014.
[MPP+ 15] Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran,
and Michael I Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. NIPS,
OPT, 2015.
[PGC+ 17] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito,
Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in
pytorch. 2017.
[PGCC17] Adam Paszke, Sam Gross, Soumith Chintala, and Gregory Chanan. Pytorch, 2017.
[Pip88]

Nicholas Pippenger. Reliable computation by formulas in the presence of noise. IEEE Transactions
on Information Theory, 34(2):194–197, 1988.

[PL05]

Bo Pang and Lillian Lee. Seeing stars: Exploiting class relationships for sentiment categorization
with respect to rating scales. In Proceedings of the 43rd annual meeting on association for computational
linguistics, pages 115–124. Association for Computational Linguistics, 2005.

[RPPA17]

Amirhossein Reisizadeh, Saurav Prakash, Ramtin Pedarsani, and Salman Avestimehr. Coded
computation over heterogeneous clusters. In Information Theory (ISIT), 2017 IEEE International
Symposium on, pages 2408–2412. IEEE, 2017.

[RRWN11] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach
to parallelizing stochastic gradient descent. In NIPS, pages 693–701, 2011.
[RTTD17] Netanel Raviv, Itzhak Tamo, Rashish Tandon, and Alexandros G Dimakis. Gradient coding from
cyclic mds codes and expander graphs. arXiv preprint arXiv:1707.03858, 2017.
[SLR16]

Nihar B Shah, Kangwook Lee, and Kannan Ramchandran. When do redundant requests reduce
latency? IEEE Transactions on Communications, 64(2):715–722, 2016.

[SZ14]

Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale
image recognition. arXiv preprint arXiv:1409.1556, 2014.
17

[TLDK17] Rashish Tandon, Qi Lei, Alexandros G Dimakis, and Nikos Karampatziakis. Gradient coding:
Avoiding stragglers in distributed learning. In International Conference on Machine Learning, pages
3368–3376, 2017.
[VN56]

John Von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable
components. Automata studies, 34:43–98, 1956.

[ZCL15]

Sixin Zhang, Anna E Choromanska, and Yann LeCun. Deep learning with elastic averaging sgd.
In Advances in Neural Information Processing Systems, pages 685–693, 2015.

[ZKJ+ 08]

Matei Zaharia, Andy Konwinski, Anthony D Joseph, Randy H Katz, and Ion Stoica. Improving
mapreduce performance in heterogeneous environments. In Osdi, volume 8, page 7, 2008.

18

A Proofs
A.1

Proof of Theorem 1

For simplicity of proof, let us define a valid s-attack first.
Definition 3. N = [n1 , n2 , · · · , nP ] is a valid s attack if and only if |{j : knj k0 6= 0}| ≤ s.
Now we prove theorem 1. Suppose (A, E, D) can resist s adversaries. The goal is to prove kAk0 ≥
P (2s + 1). In fact we can prove a slightly stronger version: kA·,i k0 ≥ (2s + 1) , i = 1, 2, · · · , B. Suppose for
some i, kA·,i k0 = τ < (2s + 1). Without loss of generality, assume that A1,i , A2,i , Aτ,i are non-zero. Let
G−i = [g1 , g2 , · · · , gi−1 , gi+1 , · · · , gP ]. Since (A, E, D) can protect against s adversaries, we have for any G,
D(ZA,E,G + N) = G1 = G−i 1 + gi ,
for any valid s-attack N. In particular, let g1i = 1d , gi2 = −1d , G1 = [g1 , g2 , · · · , gi−1 , g1i , gi+1 , · · · , gP ], and
G2 = [g1 , g2 , · · · , gi−1 , g2i , gi+1 , · · · , gP ]. Then for any valid s attack N1 , N2 ,
1

D(ZA,E,G + N1 ) = G−i 1P −1 + 1d .
and
2

D(ZA,E,G + N2 ) = G−i 1P −1 − 1d .
1

2

Our goal is to find N1 , N2 such that D(ZA,E,G + N1 ) = D(ZA,E,G + N2 ) which then will lead to a contradiction. Construct N1 and N2 by
h
i
h
i
A,E,N1
 ZA,E,N2
−
Z
, j = 1, 2, · · · , d τ −1
2 e
`,j
`,j
N1`,j =
0,
otherwise
and

N2`,j =

h
i
 ZA,E,N1
0,

h
i
2
− ZA,E,N

`,j

`,j

,

τ −1
j = d τ −1
2 e, d 2 e + 1, · · · , τ

otherwise

One can easily verify that N1 , N2 are both valid s attack. Meanwhile, we have
h
i
h
i
1
2
ZA,E,G
+ N1`,j = ZA,E,G
+ N2`,j , j = 1, 2, · · · , τ
`,j

`,j

due to the above construction of N1 , N2 . Note that Aj,i = 0 for all j > τ , which implies that for all compute
nodes with index j > τ , their encoder functions do not depend on the ith gradient. Since G1 and G2 only
differ in the ith gradient, the encoder function of any compute node with index j > τ should have the same
output. Thus, we have
h
i
h
i
h
i
h
i
1
1
2
2
ZA,E,G
+ N1`,j = ZA,E,G
= ZA,E,G
= ZA,E,G
+ N2`,j , j > τ
`,j

`,j

`,j

`,j

Hence, we have

h
i
1
ZA,E,G

`,j

which means

h
i
2
+ N1`,j = ZA,E,G

`,j

1

2

+ N2`,j , ∀j

ZA,E,G + N1 = ZA,E,G + N2
19

Therefore, we have
1

2

1

2

D(ZA,E,G + N1 ) = D(ZA,E,G + N2 )
and thus
G−1 1P −1 + 1d = D(ZA,E,G + N1 ) = D(ZA,E,G + N2 ) = G−1 1P −1 − 1d
This gives us a contradiction. Hence, the assumption is not correct and we must have kA·,i k0 ≥ (2s + 1) , i =
1, 2, · · · , P . Thus, we must have kAk0 ≥ (2s + 1)P .
A direct but interesting corollary of this theorem is a bound on the number of adversaries D RACO can
resist.
Corollary 6. (A, E, D) can resist at most

P −1
2

adversarial nodes.

Proof. According to Theorem 1, the redundancy ratio is at least 2s + 1, meaning that every data point must
be replicated by at least 2s + 1. Since there are P compute node in total, we must have 2s + 1 ≤ P , which
P −1
implies s ≤ P −1
2 . Thus, (A, E, D) can resist at most 2 adversaries.
In other words, at least a majority of the compute nodes must be non-adversarial.

A.2

Proof of Theorem 2

Since there are at most s adversaries, there are at least 2s + 1 − s = s + 1 non-adversarial compute nodes
in each group. Thus, performing majority vote on each group returns the correct gradient, and thus
the repetition code guarantees that the result is correct. The complexity at each compute node is clearly
O((2s + 1)d) since each of them only computes the sum of (2s + 1) d-dimensional gradients. For the decoder
at the PS, within each group of (2s + 1) machine, it takes O((2s + 1)d) computations to find the majority.
P
P
Since there are (2s+1)
groups, it takes in total O((2s + 1)d (2s+1)
) = O(P d) computations. Thus, this achieves
linear-time encoding and decoding.

A.3

Proof of Lemma 3

We first prove that Aj,k = 0 ⇒ Wj,k = 0.


Suppose Aj,k = 0 for some j, k. Then by definition k ∈ αj . By 0 = qj 1 · [CL ]·,αj we have 0 =


qj 1 [CL ]·,k = Wj,k .
Next we prove that for any index set U such that |U | ≥ P − (2s + 1), the column span of W·,U contains 1.
This is equivalent to that for any index set U such that |U | ≥ P − (2s + 1), there exists a vector b such that
W·,U b = 1. Now we show such b exists. Note that CL is a (P − 2s) × P full rank Vandermonde matrix and thus
any P − 2s columns of CL are linearly independent. Let Ū be the first P − 2s elements in U . Then all columns

−1 
0 0 ··· 0 1 T.
of [CL ]·,Ū are linearly independent and thus [CL ]·,Ū is invertible. Let bŪ , b̄ = CŪL
For any j 6∈ Ū , let bj = 0. Then we have


WU b = Q 1 × [CL ]·,U b


= Q 1 × [CL ]·,Ū b̄


−1 
= Q 1 × [CL ]·,Ū × [CL ]·,Ū 0



= Q 1 0 0 ··· 0 1 T
= 1.

This completes the proof.

20

0

··· 0


1 T

A.4

Proof of Lemma 4

We need a few lemmas first.
T

T

Lemma 7. Let a P -dimensional vector γ , [γ1 , γ2 , · · · , γP ] = (fN) . Then we have
Pr({j : γj 6= 0} = {j : kN·,j k0 6= 0}) = 1.
Proof. Let us prove that
Pr(N·,j 6= 0}|γj 6= 0) = 1.
and
Pr(γj 6= 0|N·,j 6= 0}) = 1.
for any j. Combining those two equations we prove the lemma.
The first equation is straightforward. Suppose N·,j = 0. Then we immediately have γj = fN·,j = 0. For the
second one, note that f has entries drawn independently from the standard normal distribution. Therefore
we have that γj = fN·,j ∼ N (1T N·,j , kN·,j k22 ). Since γj is a random variable with normal distribution, the
probability of it being any particular value is 0. In particular,
Pr(γj = 0|N·,j 6= 0}) = 0,
and thus
Pr(γj 6= 0|N·,j 6= 0}) = 1
which proves the second equation and finishes the proof.
Lemma 8. RCyc C†R = NC†R .





Proof. By definition, RCyc C†R = (GW + N) C†R = G Q 1 CL + N C†R = G Q 1 CL C†R + NC†R = NC†R . In
the last equation we use the fact that IDFT matrix is unitary and thus CL C†R = 0(P −2s)×(2s) .
Lemma 9. Let a P -dimensional vector ĥ , [ĥ0 , ĥ1 , · · · , ĥP −1 ]T be the discrete Fourier transformation (DFT) of a
P -dimensional vector t̂ , [t̂1 , t̂2 , · · · , t̂P −1 ]T which has at most s non-zero elements, i.e., ĥ = C† t̂ and ktk0 ≤ s. Then
there exists a s-dimensional vector β̂ , [β̂0 , β̂1 , · · · , β̂s−1 ]T , such that

ĥP −s−1
ĥP −s−2


 ...
ĥP −2s

ĥP −s
ĥP −s−1

...
...
..
.

...
ĥP −s+1

ĥP −2
ĥP −3
..
.

. . . ĥP −s−1





ĥP −1

ĥP −2 



 β̂ =  . .

 .. 

(A.1)

ĥP −s

Furthermore, for any β̂ satisfying the above equations,
ĥ` =

s−1
X

β̂u ĥ`+u−s ,

u=0

always holds for all `, where ĥ` = ĥP +` .

21

(A.2)

Proof. Let i1 , i2 , · · · , is be the index of the non-zero elements in t̂. Let us define the location polynomial
Qs
Ps
2πi
p(ω) = k=1 (ω − e− P ik ) , k=0 θk ω k , where θs = 1. Let a s-dimensional vector β̂ ∗ , −[θ0 , θ1 , · · · , θs−1 ]T .
Now we prove that β̂ = β̂ ∗ is a solution to the system of linear equations (A.1). To see this, note that by
Ps
2πi
2πi
2πi
definition, for any λ, we have 0 = p(e− P iλ ) = k=0 θk e− P iλ k . Multiply both side by t̂iλ e− P iλ η , we have
0 = t̂iλ e−

2πi
P iλ η

s
X

θ k e−

2πi
P iλ k

k=0

= t̂iλ

s
X

θ k e−

2πi
P iλ (k+η)

.

k=0

Summing over λ, we have
0=
=

s
X

λ=1
s
X

t̂iλ

√1
P

PP −1
k=0

e−

2πi
P jk

θ k e−

2πi
P iλ (k+η)

t̂iλ e−

2πi
P iλ (k+η)

k=0

θk

k=0

By definition, ĥj = Cj,· t̂ =

s
X

.

λ=1

t̂k =
0=

s
X
√1
P

s
X

Ps

− 2πi
P iλ j .
λ=1 t̂iλ e

Hence, the above equation becomes

√
θk P ĥk+η

k=0

which is equivalent to
ĥs+η =

s−1
X

k=0

−θk ĥk+η

due to the fact that θs = 1. By setting η = −s + P − 1, −s + P − 2, · · · , −s + P − s, one can easily see that the
above equation becomes identical to the system of linear equations in (A.1) with β̂ = β̂ ∗ = −[θ0 , θ1 , · · · , θs−1 ]T .
Now let us prove for any β̂ that satisfies equation (A.1), we have (A.2). Note that an equivalent form of
(A.2) is that the following system of linear equations

ĥP −s−1+`
ĥP −s−2+`



...
ĥP −2s+`

ĥP −s+`
ĥP −s−1+`
...
ĥP −s+1+`

...
...
..
.

ĥP −2+`
ĥP −3+`
..
.

. . . ĥP −s−1+`





ĥP −1+`

ĥP −2+` 



 β̂ =  . 

 .. 

(A.3)

ĥP −s+`

holds for ` = 0, 1, 2 · · · , P − 1. We prove this by induction. When ` = 1, this is true since β̂ satisfies the system
of linear equations in (A.1). Assume it holds for ` = µ, i.e.,

ĥP −s−1+µ
ĥP −s−2+µ



...
ĥP −2s+µ

ĥP −s+µ
ĥP −s−1+µ
...
ĥP −s+1+µ

...
...
..
.

ĥP −2+µ
ĥP −3+µ
..
.

. . . ĥP −s−1+µ

22





ĥP −1+µ

ĥP −2+µ 



 β̂ = 

..



.
ĥP −s+µ

Now we need to prove it also holds when ` = µ + 1, i.e.,

ĥP −s−1+µ+1
ĥP −s+µ+1
...
ĥP −2+µ+1
ĥP −s−2+µ+1 ĥP −s−1+µ+1 . . .
ĥP −3+µ+1


..
.
..

...
...
.
ĥP −2s+µ+1

ĥP −s+1+µ+1



ĥP −1+µ+1
ĥP −2+µ+1 




.
 β̂ = 
..



.


. . . ĥP −s−1+µ+1

ĥP −s+µ+1

First, since both β̂, β̂ ∗ satisfy the induction assumption, we must have


ĥP −s−1+µ
ĥP −s+µ
...
ĥP −2+µ
ĥP −s−2+µ ĥP −s−1+µ . . .
ĥP −3+µ 



(β̂ − β̂ ∗ ) = 0s .
..
.
.


.
...
...
.
ĥP −2s+µ

ĥP −s+1+µ

. . . ĥP −s−1+µ

Due to the induction assumption, one can verify that

ĥP −s−1+µ
ĥP −s+µ
...
ĥP −2+µ
ĥP −s−2+µ ĥP −s−1+µ . . .
ĥP −3+µ

[θs−1 , θs−2 , · · · , θ0 ]
..
.
..

...
...
.
ĥP −2s+µ

and thus we have

ĥP −s+µ

Hence,

ĥP −s+µ

= ĥP −s+µ

ĥP −s+1+µ

. . . ĥP −s−1+µ



=


 

 = ĥP −s+µ


ĥP −s+µ+1


· · · ĥP −2+µ+1 ,


ĥP −s+µ+1 · · · ĥP −2+µ+1 (β̂ − β̂ ∗ )


ĥP −s−1+µ
ĥP −s+µ
...
ĥP −2+µ
ĥP −s−2+µ ĥP −s−1+µ . . .
ĥP −3+µ 


=[θs−1 , θs−2 , · · · , θ0 ]
(β̂ − β̂ ∗ ) = 0.
..
.
.


.
...
...
.
ĥP −2s+µ ĥP −s+1+µ . . . ĥP −s−1+µ

ĥP −s−1+µ
ĥP −s−1+µ


. . . ĥP −1+µ β̂


. . . ĥP −1+µ β̂ ∗ + ĥP −s+µ

ĥP −s−1+µ

Furthermore, by induction assumption, we have

ĥP −s−2+µ+1 ĥP −s−1+µ+1 . . . ĥP −3+µ+1
ĥP −s−3+µ+1 ĥP −s−2+µ+1 . . . ĥP −4+µ+1


..
..

.
...
...
.







. . . ĥP −1+µ (β̂ − β̂ ∗ ) = ĥP +µ = ĥP −1+µ+1 .



ĥP −s−1+µ

 ĥP −s−2+µ


 β̂ = 


...
. . . ĥP −s+1+µ+1
ĥP −(2s−1)+µ


ĥP −2s+µ+1 ĥP −s+1+µ+1
 
ĥP −1+µ
ĥP −2+(µ+1)
ĥP −3+(µ+1) 
ĥP −2+µ 
 

=
.
..
..
 

.
.

ĥP −(s−1)+µ

ĥP −s−2+µ
ĥP −s−1+µ
...
ĥP −s+µ

ĥP −s+(µ+1)

Combing those two result we have proved

ĥP −s−1+µ+1
ĥP −s+µ+1
ĥP −s−2+µ+1 ĥP −s−1+µ+1



...
...
ĥP −2s+µ+1 ĥP −s+1+µ+1

...
...
..
.

ĥP −2+µ+1
ĥP −3+µ+1
..
.

. . . ĥP −s−1+µ+1
23





ĥP −1+µ+1

ĥP −2+µ+1 



 β̂ = 
.
..



.
ĥP −s+µ+1


. . . ĥP −2+µ
. . . ĥP −3+µ 

 β̂
..
..

.
.
. . . ĥP −s+µ

By induction, the equation A.3 holds for all ` = 0, 1, · · · , P − 1. Equation A.3 immediately finishes the
proof.
T

Now we are ready to prove Lemma 4. By Lemma 7, for the P -dimensional vector γ = (fN) , we have
Pr({j : γj 6= 0} = {j : kN·,j k0 6= 0}) = 1,
Since there are at most s adversaries, the number of non-zero columns in N is at most s and hence there
are at most s non-zero elements in γ, i.e., kγk0 ≤ s, with probability 1. Now consider the case when kγk0 ≤ s.
First note that [hP −2s , hP −2s+1 , · · · , hP −1 ] = fRCyc C†R = fNC†R = γ T C†R , where the second equation is due
to Lemma 8. Now let us construct ĥ = [ĥ0 , ĥ1 , · · · , ĥP −1 ]T by ĥ = C† γ. Note that C is symmetric and thus
 T
C† = C† . One can easily verify that ĥ` = h` , ` = P − 2s, P − 2s + 1, · · · , P − 1. Therefore, the equation

becomes


hP −s−1
hP −s−2


 ...
hP −2s

ĥP −s−1
ĥP −s−2


 ...
ĥP −2s

hP −s
hP −s−1
...
hP −s+1

hP −s
ĥP −s−1
...
ĥP −s+1

...
...
..
.

...

...
...
..
.

hP −2
hP −3
..
.



β0
β1
..
.





hP −s+1
βs−1
ĥP −2
ĥP −3
..
.



β0
β1
..
.





βs−1
. . . ĥP −s+1





hP −1
 hP −2 
 

 =  .. 
  . 
hP −s





ĥP −1
 ĥP −2 
 

= . 
  .. 
ĥP −s

which always has a solution. Assume we find one solution β̄ = [β̄0 , β̄1 , · · · , β̄P −1 ]T . By the second part of
Lemma 9, we have
ĥ` =

s−1
X

u=0

β̄u ĥ`+u−s , ∀`.

Now we prove by induction that h` = ĥ` , ` = 0, 1, · · · , P − 1.
When ` = 0, we have
ĥ0 =

s−1
X

β̄u ĥu−s =

u=0

s−1
X

β̄u hu−s = h0

u=0

where the second equation is due to the fact that [hP −2s , hP −2s−1 , · · · , hP −1 ] = [ĥP −2s , ĥP −2s−1 , · · · , ĥP −1 ]
and ĥP +` = ĥ` , hP +` = h` (by definition).
Assume that for ` ≤ µ, ĥ` = h` .
When ` = µ + 1, we have
ĥµ+1 =

s−1
X

β̄u ĥµ+1+u−s =

u=0

s−1
X

β̄u hµ+1+u−s = hµ+1

u=0

where the second equation is because of the induction assumption for ` ≤ µ, ĥ` = h` .
Thus, we have h` = ĥ` for all `, which means h = ĥ = C† γ. Thus t, the IDFT of h, becomes t = Ch =
CC† γ = γ. Then the returned Index Set V = {j : ej+1 6= 0} = {j : γj 6= 0}. By Lemma 7, with probability 1,
{j : γj 6= 0} = {j : knj k0 6= 0}. Therefore, we have with probability 1, V = {j : knj k0 6= 0}, which finishes the
proof.
24

A.5

Proof of Theorem 5

We first prove the correctness of the cyclic code. By Lemma 4, the set U contains the index of all nonadversarial compute nodes with probability 1. By Lemma 3, there exists b such that W·,U b = 1. Therefore,
Cyc
uCyc = RCyc
, E Cyc , DCyc ) can recover the
·,U b = (GW + N)·,U b = GW·,U b = G1P . Thus, The cyclic code (A
desired gradient and hence resist any ≤ s adversaries with probability 1.
Next we show the efficiency of the cyclic code. By the construction of ACyc and W, the redundancy ratio
is 2s + 1 which reaches the lower bound. Each compute node needs to compute a linear combination of the
gradients of the data it holds, which needs O((2s + 1)d) computations. For the PS, the detection function φ(·)
takes O(d) (generating the random vector f) + O(dP + 2P s) (computing fRC†R ) + O(s2 ) (solving the Toeplitz
system of linear equations in (A.1) ) + O((P − 2s)s) (computing h` , ` = 0, 1, 2, · · · , P − 2s − 1 ) + O(P log P )
(computing the DFT of h ) + O(P ) (examining the non-zero elements of t ) = O(d + dP + 2P s + s2 + (P −
2s)s + P log P + P ) = O(dP + P s + P log P ). Finding the vector b takes O(P 3 ) (by simply constructing b via
[CL ]·,Ū , though better algorithms may exist). The recovering equation R·,U b takes O(dP ). Thus, in total, the
decoder at the PS takes O(dP + P 3 + P log P ). When d  P , i.e., d = Ω(P 2 ), this becomes O(dP ). Therefore,
(ACyc , E Cyc , DCyc ) also achieves linear-time encoding and decoding.

B Streaming Majority Vote Algorithm
In this section we present the Boyer—Moore majority vote algorithm [BM91], which is an algorithm that
only needs computation linear in the size of the sequence.
Algorithm 2 Streaming Majority Vote.
Input : n items I1 , I2 , · · · , In
Output : The majority of the n items
Initialize an element Ma = I1 and a counter Counter = 0.
for i = 1 to n do
if Counter == 0 then
M a = Ii .
Counter = 1.
else if M a == Ii then
Counter = Counter + 1.
else
Counter = Counter − 1.
end
end
Return M a.
Clearly this algorithm runs in linear time and it is known that if there is a majority item then the algorithm
finally will return it [BM91].

25

