Sequential Gradient Coding For Straggler Mitigation
Authors: Nikhil Krishnan Muralee Krishnan
MohammadReza Ebrahimi
Ashish J Khisti
Venue: ICLR 2023 poster (2023)
Keywords: gradient coding
straggler mitigation
distributed computation
coded computing

Abstract: In distributed computing, slower nodes (stragglers) usually become a bottleneck. Gradient Coding (GC), introduced by Tandon et al., is an efficient technique that uses principles of error-correcting codes to distribute gradient computation in the presence of stragglers. In this paper, we consider the distributed computation of a sequence of gradients $\{g(1),g(2),\ldots,g(J)\}$, where processing of each gradient $g(t)$ starts in round-$t$ and finishes by round-$(t+T)$. Here $T\geq 0$ denotes a delay parameter. For the GC scheme, coding is only across computing nodes and this results in a solution where $T=0$. On the other hand, having $T>0$ allows for designing schemes which exploit the temporal dimension as well. In this work, we propose two schemes that demonstrate improved performance compared to GC. Our first scheme combines GC with selective repetition of previously unfinished tasks and achieves improved straggler mitigation. In our second scheme, which constitutes our main contribution, we apply GC  to a subset of the tasks and repetition for the remainder of the tasks. We then multiplex these two classes of tasks across workers and rounds in an adaptive manner, based on past straggler patterns. Using theoretical analysis, we demonstrate that our second scheme achieves significant reduction in the computational load. In our experiments, we study a practical setting of concurrently training multiple neural networks over an AWS Lambda cluster involving 256 worker nodes, where our framework naturally applies. We demonstrate that the latter scheme can yield a 16\% improvement in runtime over the baseline GC scheme, in the presence of naturally occurring, non-simulated stragglers.


SEQUENTIAL GRADIENT CODING FOR STRAGGLER MITIGATION
M. Nikhil Krishnan
M. Reza Ebrahimi University of Toronto
Indian Institute of Technology Palakkad ni mikhilkrishnan me aeagmmii com
mr ewweebbbiii.. @mail 1. utoronto.ca
Ashish Khisti
University of Toronto
akhisti@ece. utoronto.ccm
ABSTRACT
In distributed computing, slower nodes (stragglers) usually become bottleneck. Gradient Coding (GC), introduced by Tandon al., is an efficient technique that uses principles of error-correcting codes to distribute gradient computation in the presence stragglers. In this paper, we consider the distributed computation of a sequence of gradients {g(1), g(2). ................................ .())), where processing of each gradient g(t) starts in round-/ and finishes by round-(t + T). Here T 2 0 denotes a delay parameter. For the GC scheme, coding is only across computing nodes and this results in a solution where T = O. On the other hand, having T >> allows for designing schemes which exploit the temporal dimension as well. In this work, we propose two schemes that demonstrate improved performance compared GC. Our first scheme combines GC with selective repetition of previously unfinished tasks and achieves improved straggler mitigation. In our second scheme, which constitutes our main contribution, we apply GC subset of the tasks and repetition for the remainder of the tasks. We then multiplex these two classes of tasks across workers and rounds in an adaptive manner, based on past straggler patterns. Using theoretical analysis, we demonstrate that our second scheme achieves significant reduction in the computational load. In our experiments, we study practical setting of concurrently training multiple neural networks over an AWS Lambda cluster involving 256 worker nodes, where our framework naturally applies. We demonstrate that the latter scheme yield 16% improvement in runtime over the baseline GC scheme, in the presence of naturally occurring, non-simulated stragglers.
INTRODUCTION
We consider distributed system consisting of master and n computing nodes (will referred as workers), We are interested in computing sequence of gradients g(1),g(2),... 9(2)...... Assume for simplicity that there are no dependencies between the gradients (we will relax this assumption later in Sec. 2). If we naively distribute the computation of each gradient among workers, delayed arrival of results from any of the workers will become bottleneck. Such delay could be due various reasons such as slower processing workers, network issues leading to communication delays etc. Irrespective the actual reason, we will refer to worker providing delayed responses to the master, straggler. In recent work Tandon et al. (2017). the authors propose Gradient Coding (GC) to distribute computation of a single gradient across multiple workers in a straggler- resillent manner. Using (n, s)-GC, the master is able compute the gradient as
(n 8) workers respond (s is an integer such that 0 S < n). Adapting GC to our setting, we will have a scheme where gtt) is computed in round-t and in every round, up stragglers
tolerated (the concept of round will be formally introduced in Sec. 2). Experimental results (Yang et al.) 2019) have demonstrated that intervals of "bad" rounds (where each round has large number of stragglers) followed by "good" rounds (where there are relatively fewer number of stragglers), leading to natural temporal diversity.
Equaa contribution authors.

---

Published as a conference paper at ICLR 2023
Note that GC will enforce large s, as dictated by the number of stragglers expected in bad rounds, leading to a large computational load per worker. The natural question to ask here is that: do there exist better coding schemes that exploit the temporal diversity and achieve better performance?. ?. In this paper, we present sequential gradient coding schemes which answer this in the affirmative.
1.1 SUMMARY OF CONTRIBUTIONS
In contrast to existing GC approaches where coding is performed only across workers, we propose two coding schemes which explore coding across rounds well workers.
Our first scheme, namely, (Sec. 3.2, is natural extension of the (n, s)-GC scheme, where unfinished tasks are selectively reattempted in future rounds. Despite the simplicity, SR-SGC scheme tolerates a strict superset of straggler patterns compared to (n. s)-G. , for the same computational load.
Reatteentt-Sequeniial Gradient Coding (SR-SGC)
In our more involved second scheme, namely, Multiplexed-Sequeniiee (M-SGC) scheme (Sec. (.3). we divide tasks into two sets; those which are protected against stragglers via reattempts and those which are protected via GC. We then carefully multiplex these tasks to obtain a scheme where computational load per worker is significantly reduced. In particular, the load decreases by a factor of when compared to the (n1, s)-GC scheme and is close to the information theoretic limit in certain conditions.
Gradient Coding
Our experiments (Sec. an AWS Lambda cluster involving 256 worker nodes show that the M-SGC scheme achieves a significant reduction of runtime over GC, in real-world conditions involving naturally occurring, non-simulated stragglers.
1.2 RELATED WORK
We provide brief overview on the use of erasure codes for straggler mitigation in Appendix B The terminology of "sequential gradient coding" " initially appears Krishnan et al. (202T). Both the current paper and the work Krishnan et al. (221)) extend the classical GC setting (Tandon et al. 2017). by exploiting the temporal dimension. The authors of Krishnan et al. (2021) provide a non-expplle explicii coding scheme that is resilient against communication delays and does not extend when stragglers are due to computational slowdowns. In contrast, we propose two explicir coding schemes that are oblivious of the reason for straggling behavior. Moreover, under equivalent straggler conditions, the computational load requirements of the newly proposed SR-SGC scheme and the scheme in Krishnan al. (202T) are identical, whereas the new M-SGC scheme offers significantly smaller load requirement. The works Ye & Abbe (2018); Kadhe et al. (2020) explore trade-off between communication and straggler resiliency in GC. Several variations the classical GC setting appear in papers Raviv et al. (2020) (Halbawi et al. (2018); Wang et al. 2019a Maity et al. (2019).
There is rich literature on distributing matrix multiplication or more general, polynomial function computation (see Yang et al. (2019): Yu et al. (2017); et al. (2018); |Ramamorrhyy et al. (0119;; Subramaniam et al. (2019): Yu et al. (2019): Dutta et al. (2020): Yu et al., (2020); Raammmorthy et al. (2020) and references therein). In Krishnan et al. (2020), the authors introduce sequential matrix multiplication framework, where coding across temporal dimension is exploited to reduce the cumulative runtime for sequence of matrix multiplication jobs. While we also explore the idea of introducing temporal dimension to obtain improved coding schemes, extending the approach in Krishnan et al. (2020) to our setting yields inferior solution requiring large computational load.
2 SEQUENTIAL GRADIENT CODING SETTING
For integers a, b, let la 6] Sallaiisi <i and [a : 6]+ 2 mod a i b). For integer c, We are interested
we have c Ja b & fctilie (a: "] Workers are indexed by [0 n0:n-]] 1]. in computing sequence of J gradients (o(())ef)1:) Computation of gradient g(i) is referred to as job-i. All gradients are computed with respect to a single data set (this assumption is just for simplicity in exposition and our schemes can easily be adapted to include multiple data sets).
Data placement: Master partitions D into 1) data chanks (Do: Di...., D possibly of different sizes. Each wo stores data chunks (DiiED, where D. C [0:n 1.. Let gt) denote the t-th

---

Published as a conference paper at ICLR 2023
partial gradient computed with respect to Dj, i... i... that the partial gradient 9j (1) corresponds to job-t.
1) g(t). Naturally, we also say
Encoding: Master operates based on a certain concept of rounds and it takes J + T rounds to finish computing all the J gradients. Here, T' 2 0 is a system parameter which takes integer values. Let t E [1: J + T]. In round-f, worker-i computes (t()) partial gradients with respect to subset of data chunks it stores. These partial gradients may correspond to any of the jobs [1 tl. In other words, the partial gradients computed by worker-i in round-t are from within the set {9H ( (e(())))e The process of worker-i computing 7:()) partial gradients will be referred to as a lask. Once the (/a)) partial gradients are computed in round-t, worker-i returns a task result (t), which is a function of the (t(t) partial gradients, via an encoding step.
Identification of stragglers: In each round-t, let k(t) denote the time (in seconds) taken for the fastest worker (say, worker-i) to return the task result to the master. Master then waits for pu(() (p is tolerance parameter) more seconds and possibly more workers will return their task results during this time. Any worker which does not return its task result during this time will be marked straggler. Any pending tasks of stragglers will then be canceled and the system will move to the next round. Clearly, if worker-i is a straggler in round-t, the task undertaken by it has "failed" and task result (t) will not be returned to the master. We note that determining stragglers using the parameter is in line with the earlier work Krishnan et al. (2020).
Decoding: In the end of round-(t + T), master attempts to produce (decode) g(t) using all available results from the set (t))"))e []:+7( i.e., master tries to finish job-t, in the end of round- (L TT) Decoding is assumed to incur negligible computational cost, in comparison that for partial gradient computation. This assumption can easily be justified for our proposed schemes, as they require only finite memory. As workers potentially start computing partial gradients corresponding to any job-t only from round-t onwards, the parameter T may be regarded as delay in finishing a job.
Normalized computational load per worker: Let denote the number of data points in D. Let (t) denote the total number of data points across which worker-i computes (t) partial gradients in round-t. The normalized (computational) load at worker-i in round-t is then given by: Lt(t) & d:(()
Remark 2.1. Any dependencies existing between jobs need to be managed by choosing the T parameter accordingly. Suppose job-í2 is dependent on the computation of g(i)), where i < ig. One may choose here 7'' satisfying T iz i 1. In our experiments presented in Sec. 4 we concurrently train M neural network models, where jobs Mi+ + 1. M(2 + 1) are i-th iterations 0, in the training of models 1...., M, respectively. Here, we need T S M 1.
Remark 2.2. The flexibility of T > 0 (coding across rounds) enables us design coding schemes which feature lower computational load and tolerate practically motivated straggler models. This in turn leads to smaller cumulative runtime (in seconds) for finishing jobs (in J + T rounds).
2.1 STRAGGLER MODELS
For the sake of our analysis and code design, we will be referring to the following three straggler models. However, as explained in Remark 2.3 at the end of this section, and validated in Sec. 4 our coding schemes apply to any naturally occurring straggler patterns.
(B, W, X) A)-bursty straggler model: Based on experiments over Amazon BC2 cluster, the authors of Yang et al. (2019) observe that a 2-state Gilbert-Elliot (GE) model (see Appendix C more details) can be used to track transitions of workers from being stragglers to non-stragglers and vice-versa However, while designing codes for straggler mitigation, a deterministic counterpart for the GE model is more ideal. Sliding-window window-based deterministic models have been employed in many works as a reliable approximation of GE model; for instance, in the early classical work Forney (197I), in Saberi et (2019) in the context of control systems, Martinian & Sundherg (2004) in the context of low-latency communications and Krishnan et al. (2020) in the context of distributed matrix multiplication. We will now define the (B, W, A)-bursty straggler model. Let (t) be an indicator function which is if worker-i is straggler in round-t and otherwise. The straggler model is defined by the following two properties:
1. (Spatial correlation): In every window W, of the form [j: j + W 1] consisting of W consecutive rounds starting at round-j, there are at most S n distinet stragglers. i.e., size of the set of workers given by {i] St(t) = 1 for some t E Wj} } is at most X.
3

---

Published as a conference paper at ICLR 2023
2. (Temporal correlation): For any worker-i, first and last straggling slots (if any) are not more than B - 1 rounds apart in every window Wj. i... if St(t) = 1, for some E Wj, then (t( for all E it
B: Bt+B:ja W 1I..
Clearly, the parameters X, B satisty: 0 S X < n1, n 1SBSW.
(N, W X' >arrbitrryyy straggler model: This is natural extension of the (B, W, A)-bursty straggler model where we consider arbitrary stragglers instead of bursty stragglers. As in the bursty model, in every window W of the form [ : + W" 1], there are most X distinct stragglers, Moreover, for every worker-i, Eiewy (())) N. The parameters X, N satisfy: 0 S X S
N < W
s-straggllrs--ee--ouwy model: In this model, in each round, at most 8 workers can be stragglers. Here is integer satisfying
designed to tolerate straggler patterns conforming to "mixture" of these deterministic straggler models. As these models are design choice, the ground truth associated with the actual straggler behavior need not always conform to them. For instance, we evaluate the performance of our coding schemes on large AWS cluster (see Sec. 4). in the presence of naturally occurring stragglers. Clearly, the actual straggler behavior here need not be conforming the straggler model used during code design. However, even then, every job-t will still be finished by the end of round-(f (t + T).. We ensure this in the following manner. In any round, if the actual straggler pattern deviates from the straggler model assumption, the master will wait for stragglers to return results in that round. This way, the actual straggler pattern will "effectively" continue conform to the assumed straggler model.
Remark 2.3. Coding schemes that we present in the paper (see Sec. 3.2 and
3 SEQUENTIAL GRADIENT CODING SCHEMES
3.1 PRELIMINARIES, GRADIENT CODING
We present here a summary of the (n, s)-GC scheme. The data set is partitioned into - n equally sized data chunks Do, Di....y Dn-1- Worker-i stores s data chunks [DjJseistss)) With respect to each D, stored, worker-i computes the partial gradient Øj- Hence, worker-i computes the following + partial gradients: {g; [j((exts)]- Worker-i then transmits the result, which is linear combination of the s + 1 partial gradients,
Ejeles+ 04.j9j- The coefficients { are designed so that master has access to results returned by any n - out n workers, - 90 + I1 +... In-1 can be computed. In other words, for any W _ 00 n- with [W] = n n, there exist coefficients {.w,,,) "ww,.)weww wew such that g Ewew Bw. Clearly, the scheme tolerates stragglers. Applying the (n, BC- scheme to our framework, we get scheme which computes 0). Each worker-i round-t works on a task corresponding to job-t. Specifically, worker-i computes {g, je)} and returns (, Ejeles+ 04,59) (t). Normalized load is given by Lac = 2+11 This scheme clearly tolerates any straggler pattern conforming the s-stragglens-per-roond model. We will now present both our proposed schemes.
g(t) in round-t (i.e., delay
3.2
GRADIENT CODING (SR-SGC) SCHEME
SR-SGC scheme a natural extension of the (n, s)-GC scheme. We begin with (n, s)-GC as the "base scheme" and whenever there are stragglers than the base scheme can handle, will carefully reattempt certain tasks across time. This simple idea helps the scheme tolerate a strict superset of straggler patterns compared to the classical (n, S)-G scheme for the load (we present the formal statement in Prop. 3.I).
normalized
Design parameters: The parameter set is given by {n, B,W,W, W, A), where 0 < X n, B, and B divides (W - 1). i.e., there exists an integer æ 2 1 such that W = BB + 1. We set I+1 1. The scheme incurs delay of T = B and normalized load LSR-SGC = s+1
2
BA
W-1+B
Scheme outline: Recall the notation (t) presented in Sec. 3.c. In round-t, worker-i will attempt to compute either (1) or else, (t - B) as we will see now. Using the property of (n, s)-GC, a job can be finished if master receives (n s) task results corresponding to that job. In round-f, if master finds out that (n - v) < (n s) task results corresponding to job-(t - B) are received in round-(t. B). the minimum additionally required number of (v s) tasks corresponding to job-(t B) will be

---

Published as a conference paper at ICLR 2023
attempted in round-t. These tasks will be attempted by workers who did not previously return task results corresponding to job-(t - B3) in round-(t B). Rest of the (n - - s) workers will attempt tasks corresponding to job-t. On the other hand, if job-(t - B) is already finished in round-(t B), all tasks in round-t correspond to job-t. Ne() denote the number of task results corresponding to job-t returned to master round-t. Algorithm we formally describe the exact task assignments. As jobs are indexed in the range [1 JI, for consistency in notation, we assume that all task results corresponding to job-l' are known master by default ((L") = ni), whenever l' $ [1: J].
Algorithm 1 Algorithm used by master to assign tasks in round-t
Initialize 8 _ ([ B). for i [0: 1] do
0 < n - and f,(t - B) is not returned previously by worker-i in round-(t then
Worker-i attempts to compute l B). Recall the definition of (,()) in Sec. 3.1
Set 0 = 6
else
Worker-i attempts to compute (t).
Proposition 3.1. Consider the SR-SGC scheme for parameters {n, B, W, X}, where 0 < X S n, B > O,W = =, B, any straggler pattern which conforms either (i) the (B, W, A)-bursyyy straggler model or else, (ii) the --straggler--per per-round model, when restricted to any window of W consecutive rounds.
W-I+B and LSR-SGC s+1. The scheme then tolerates
BA
The proof of Prop. 3.1 requires a careful analysis of dependencies between successive rounds due to repetition of tasks. We defer the proof Appendix D
order to are able choose a lower value of w-I+B and result, normalized load is lower as well. In another perspective, SR-SGC scheme tolerates a superset of straggler patterns compared to the GC scheme for the same normalized load.
Remark 3.1. Let À < n. Without selective repetition, classical GC requires
tolerate the (B, W, A)-bursty straggler model. In SR-SGC, BA
3.3 MULTIPLEXED MULTIPLEXED-SEQUENNIIA GRADIENT CODING (M-SGC) SCHEME
In contrast to the SR-SGC scheme (where all tasks are coded using base (n, s)-G scheme), large fraction of computations in the M-SGC scheme are uncoded (thus incurs no computational overheads). This results in the M-SGC scheme achieving significantly lower normalized load compared to SR-SGC or GC schemes. Such a lower normalized load eventually translates to reduced cumulative runtimes as we see in Sec. 4
The parameter set for M-SGC scheme is given by (n. B, W. A), where 0 S < n, < B < W.
The scheme incurs a delay of T W 2 B. minor modification of the scheme to cover the
À scenario is discussed in Remark 3.2 As M-SGC scheme is more involved compared to the SR-SGC scheme, we initially present an example which highlights the ideas involved in M-SGC scheme. Subsequently, we provide the general coding scheme in Sec. Sec. 3.3.2] The scheme tolerates straggler patterns which conform to either (B, W, bu-bustty straggler model or (N B, W'
W + B 1, A)-arbityyyy straggler model (see Prop. 3.2
3.3.1 EXAMPLE
Consider parameters (n = 4, 2, 33 2). Assume that data set D contains d data points. D is partitioned into 16 data chunks of unequal sizes (Do...., 1..]. Data chunks D, A (Do, ............ ,,Dr) are of equal size and contain 3 data points each. Similarly, data chunks D2 (Ds....,D,y contain 32 d data points each. These 16 data chunks are distributed across workers in the following manner, Worker-O: (Do, D,, Ds, Do,, Dio. D 12. D 13. D14). worker- 1: [D2, Dg, Dio. D1,, , Di3, D14, , D1s). worker-2: (Da, D,, D D. D Ds. D D15, D12} and worker-3: (Do. D,, D1, Ds. Dy. D1s; D12. D13}. Note that data chunks in D2 are not repli- cated, whereas each data chunk in D2 is replicated 3 times. Each job-t is finished when master computes g(t) = (t)))) +
Data placement:
=,
91s (t). high level idea of the coding scheme as follows. Failed partial gradient computations with respect to data chunks D2 will be reattempted across rounds. Partial gradient computations with respect to data chunks D2 will be made straggler-resilien by employing the (4, GC- scheme.
5

---

Published as a conference paper at ICLR 2023
Diagonally interleaved mini-tasks: The task performed by each worker-i in round-t consists of W W-++ B = 4 sequentially performed mini-tasks (t; O).... Titt; If worker-i is a straggler in round-f, results of mini-tasks (t ...,, (ttt;3) will not reach master and as far as master is concerned, all of them "failed". Conversely, if worker-i is non-straggler in round-t, all the four mini- task results will reach master in the end of round-t. Mini-tasks Ti(t: 0). (t + 1: .)..... Ti(t + 3: involve partial gradient computations corresponding to job-l (see Fig. 2 in the Appendix).
Fixed mini-task assignment: Computations done as part of first two mini-tasks Ti(1; 0), Ti(4; 1) are fixed for all f. Specifically, mini-tasks along the "diagonal" (1 0) and 1;;1) involve computing (2x(t) and 92:+1 (t), respectively.
Adaptive mini-task assignment:
The other two mini-tasks Ti( + 2) Ti(t + 3;3), which also involve partial gradient computations corresponding to job-l, are assigned adaptively, based on the straggler patterns seen in previous rounds. Specifically, if master did not receive g2s(t) in round-t, Tt( + 2:2) involves computing 92s (t). Else if master did not receive g2++((t) in round- (t+ 1), (i(t + 2:2) involves computing g2i+1 In similar manner, if master did not receive (2)+1(() in rounds (t+1) and (t + 2). (t + 3;3) involves computing 12)+1(t). Note that so far we have described only partial gradient computations with respect to data chunks in Dj- In round-(t + 2), if (2x(t) and (2++1(t) are already available to master, T.(t + 2, 2) will involve computation of three partial gradients hes+())))))))+))) and obtaining the linear combination (1,((() = = Oi.)))+((1) (applying a (4, 2C-G). Using properties of GC-scheme, if master has access to any two among (fo.o(t).... ..... (t)) 9s (t) + (o()) + (iu + 911 can be obtained. Similarly, in round-(!+33) (3), (2)(() and 92141 (t) are already available to master, Ti(t 3, 3) involves computing (1) = -jj(ss--- 12., Master can recover (12 + (la(() + (1) + (15(() from any two results among (t)...)..... (t),...,,,,,, ... } This completes the description of the M-SGC scheme. Note that number of data points involved is the same in both fixed and adaptive mini-tasks
and hence, computational load remains the same in both situations.
Analysis of straggler patterns: We will now show that the scheme tolerates any straggler pattern conforming to the (B = 2, W = 3, = 2)-bursty straggler model. In Fig. 6 (included in the Appendix), we illustrate mini-task assignments with respect to a straggler pattern conforming to this model. As jobs are indexed in the range [1 J]. mini-tasks corresponding to job-t, & [1 J] are indicated using in the figure. These are trivial mini-tasks which do not incur any computation. Consider the computation of 9(2) (i.c., job-2) based on Fig. (6 Since, worker-O is straggler in round-2 and worker-1 is a straggler in rounds 2 and 3, computations of (2), 92(2), gs (2)) failed initially, got reattempted and succeeded. From (2) and (3,0(2) (both finished in round-4), the master can recover 9s(2) + g2) + (10(2) + (2), owing to the use of (4, (4.))-C.. Similarly, g)2(2) + 91a(2) + g14 (2) + (2) can be recovered using ( and (2) in round-5. Hence, master computes g(2) _ (2) + ........... + (2) after round-5 (delay T = W + 3).
3.3.2 GENERAL SCHEME
Data placement: Assume that dataset D contains d data points. D is partitioned into (W Data chunks D A+1 (Do,Di..... Di...., .....,,DWwip 1Iw- are all equally sized and contain ((B+(W-I((+T)) d data points each. Similarly, D2 & (D)
1 + B)n unequally sized data chunks (Do, D DI...., D(..,,,WW-+------
-Iy D(W-1+B)x-11 are also equally sized and contain MB++ (e-+W-ijie DJA+Dy d data points each. Data chunks in D, are divided into n groups consisting of (W 1) data chunks each. Every worker will store one of these groups of data chunks. Pre- cisely, worker-i stores data chunks -D -I) Similarly, D2 is divided into B groups consisting of n data chunks each. Group-j, j E [0 : - 1], consists of data chunks The n equally sized data chunks in each group will be treated
(D(w-1+j)n... D [W+j)nn- partitions of data set in an (n, X)-GC scheme (see Sec. 3.1 and will be stored in workers accordingly. ie., from each group-j. j. worker-i stores the (A + 1) data chunks [Di]te(w (ooee(W-++))eeee 11:
Mini-task assigument: In round-t, each worker-i sequentially performs (W - 1 B) mini-taso labelled as (T((t: ()... Ti(t; W 2 - B)}. A mini-task involves either (i) computing partial gradient with respect to one of the data chunks in D2 or else (ii) one partial gradient each with respect to X + 1 data chunks (thus, X ++ 1 partial gradients in total) in Dz. As noted in the example, failed mini-tasks belonging to scenario (i) will be reattempted whereas those in scenario (ii) will be compensated via use of (n, AJ-GC scheme. Recall that delay T = W 2 + B. In Algorithm 2 we

---

Published as a conference paper at ICLR 2023
describe how mini-tasks assigned. We have normalized load:
(A+1
A < n,
LM-SaC
B
-IMA++1]-
W-1+B
if
nWW
Remark 3.2 (Case of À = n). For the special case À = n, data set D will be partitioned into (W-1)) 11) equally sized data chunks D _ (Do, DI...., (( D(w-1)m-1)- i.e., effectively we have Dz _ (null set). For notational consistency, set partial gradients gu (t) a 0, [(W-1)n: -W-1+ These are trivial partial gradients which do not incur any computation in Algorithm 2
Remark 3.3. It is straightforward note that for given {n, W. B)} normalized load is the largest when À = As B < W, we thus have LM-SGC S π irrespective of the choice of X. In contrast, normalized load s+1 SR-SGC scheme scales with À (s _ I W 1).
Algorithm 2 Algorithm used by master to assign mini-tasks in round-t
for i (0 n do for j E [0: W- do Assign computation of 9i(W-1)++ - j) mini-task T((t;)).
-
> Mini-task result is 9i(W-1)+5(t -
for j E [W- 1: W 22+ do if master received all of [9aw-1)+5 j prior to round-t then
Assign computation of (A 1) partial gradients {g - -))ee(ett)) as Tt(t;
Mini-task result is (1j(W-11) - j) = Eie 0ig1in+t((
Coefficients ox, defined in Sec. 3.1
else
2 for j' E 10: 2 do if master has not received Assign computation of 91+-1)++ (1 j) as mini-task Jt;
(t j] prior to round-f then
> Mini-task result is 9i(W-1)+5" (t -))
break
breaks the j for loop
Proposition 3.2. Consider the M-SGC scheme designed for parameters {n. B, W. A}, where 0 S The scheme tolerates
S n, < B < W, = W - 2 + B and LM-sGC as in equation [ any straggler pattern which conforms either the (B, W, X)-burstt straggler model or else, the (N = B'W' W + B 1, X' = X)-arbitrary straggler model.
Remark 3.4 (Near-optimality. Based on information-theoree details), we observe that when À straggler pattern conforming to the (B, W, buuussyy straggler model. Moreover, for fixed n, B and X, the gap between the proposed load in equation I and optimal load decreases O w Analogous results are derived with respect to the (N, W X X straggler model as well.
bounds (see Appendix for more 1 or n. M-SGC scheme is optimal scheme tolerating any
Remark 3.5. If (s + 1) divides nı, there exists a simplification to the GC scheme. Both SR-SGC and M-SGC schemes can leverage the existence of such simplified scheme. We discuss this in App. G
EXPERIMENTAL RESULTS
In this section, evaluate the performance of proposed schemes by training multiple neural network models concurrently. We use the AWS Lambda, a fully-managed and cost-efficient serverless cloud computing service. Workers are invoked from the master node using HTTP requests, and task results are received in the HTTP response payload. Appendices H and provide detailed discussions on the network architecture, experimental setup and potential applications.
[
4.1 ANALYSIS OF RESPONSE TIME
Our experiment setup consists of master node and 256 workers. In Fig. 1 we demonstrate statistics of response time across 100 rounds, where each worker calculates gradients for batch of 16 MNIST images CNN involving three convolutional layers, followed by two fully connected
7

---

Published as a conference paper at ICLR 2023
layers. Fig. a shows the response time of each worker every round. White cells represent stragglers. As discussed in Sec. 2 a worker is deemed straggler when its response time exceeds (1 μ1) times the response time of the fastest worker in the round. For the sake of consistency, we choose 7 for all experiments. Nonetheless, such a choice of J. is by no means critical to observe stragglers. This can be seen in Fig. ( where the empirical CDF of workers' completion time exhibits relatively long tail. Fig- ( plots the number of straggler bursts of different length over this response profile. can be observed that our response profile does not include nodes that continue to remain stragglers for long duration. This motivates the of coding actoss the temporal dimension as proposed in the present work.
(
3.0
20
2.0
Round
40
1.5
80
1.0
80
0.0
20
60
80
100
120
140
160
180
200
220
240
Worker
Number aaooereee bursts
1.000
Ralto of completed workars
1.0
865
800
0.8
800
0.6
400
0.4
122
Burst Length
Time (5)
Figure 1: Statistics of response time for 256 workers across 100 rounds. Each worker calculates
gradients of the loss for a batch of 16 MNIST images on convolutional neural network. (a) Each white cell represents a worker (x-axis) who straggler the corresponding round (y-axis). (b) Histogram of stragglers' burst lengths. (c) Empirical CDF of workers' completion time, averaged over 100 rounds (shades represent standard deviation).
4.2 COMPARISON CODING SCHEMES
Using the setup described in Sec. 4.1 we train M = 4 CNN classifiers for MNIST concurrently following the approach stated in Remark 2.1 In every round, master samples a batch 4096 data points and distributes them among the workers. Non-straggling workers compute partial gradients and return task results to the master at the end of each round. After completion one update, master uploads the updated model parameters to shared network file system, accessible to the workers. We use cross entropy as the loss function and ADAM as the optimizer. Moreover, the same dataset and architecture used for all the models.
In each experiment, we run a total of J = 480 jobs (120 jobs per classifier) using the three schemes, namely GC, SR-SGC and M-SGC. As baseline, wherein the master node should wait for all the workers to return their task results. Finally, each experiment is repeated 10 times report the first and second-order statistics of total run times. Before training the models, we perform some shorter experiments to choose the best- cest-performing parameters for each of the three coding schemes. Specifically, for GC, we perform a grid search over s and select the value corresponding to the shortest run time. We refer readers to Appendix [or detailed discussion on the procedure of selecting the parameters for SR-SGC and M-SGC schemes, as well as analysis of sensitivity to parameters.
also train the classifiers without any coding
Table presents the total run time achieved by each coding scheme, along with the selected parameters and resulting normalized loads. Selection of small values for parameters B and W in our sequential

---

Published as a conference paper at ICLR 2023
coding schemes matches the empirical evidence Fig. lTb) that isolated short-length-bursee are prevalent. It is interesting to note that the effective value of parameter in SR-SGC (s 12) turns be close to that of GC = 15). Fig. a plots total number of completed jobs (for all M models) across time, and Fig. 2(b) shows the course of training loss (of the first model out of the 4 models) as a function of time, for all coding schemes.
Table 1: Total run time achieved by different coding schemes
Scheme
Parameters
Normalized Load
Run Time (s)
M-SGC
B 1, 2, 2 27
0.008
891.37 43.10
SR-SGC GC
B B = 3, = 23 (s= 12)
0.051
994.22 = 43.66
$
0.062
1064.96 + 46.72
No Coding
0.004
1307.79 61.88
141
(3-1, Wi-,, A-27)
MDGC (3+1, MH2 1-27)
222
Codira
No
Nenve 4f)t 0000
1.75
502
Trustn 2000
1.50
309
102
0.50
Figure 2: (a) Number of completed rounds vs. clock time, averaged over 10 independent experiments. (b) Training loss vs. clock time for the first model (out of four concurrently trained models), averaged over 10 independent runs. Shades here represent standard deviation.
The first clear observation from Table I is that our proposed M-SGC achieves 16% lower run time while maintaining smaller normalized load compared to the classical GC scheme. Furthermore, compared to GC, SR-SGC shows slight improvements in total runtime and normalized load simulta- neously, demonstrating the potential of incorporating selective repetition into GC. Next, as shown in Fig. 2 and Table T1 the existence of stragglers is validated by the fact that any of the coding schemes significantly outperforms the case of not using any coding. This is indeed in line with the empirical observation of Figure (c). where the tail of the cumulative distribution of workers' completion time signals the existence of stragglers. Appendix K discusses how the overheads of decoding time and parameter selection time can be completely removed in the training process. Appendix L we present analogous results for concurrently training four ResNet- 18 models on CIFAR- 100 dataset.
CONCLUSION
We develop class of gradient coding schemes that exploit coding across the temporal dimension. in addition to the spatial dimension (i.c., coding across workers) considered in prior works. Our first scheme, SR-SGC uses the GC scheme in Tandon et al. (2017) base scheme and enhances it by performing selective repetition of tasks based on the past sequence of straggler patterns. Our second scheme, M-SGC multiplexes gradient coding and selective repetition of tasks over the dataset in novel way that dramatically reduces the computational load per worker, when compared to both GC and SR-SGC. In addition, we demonstrate that the computational load of M-SGC can approach an information theoretic lower bound in certain cases. We validate our schemes through experiments over large scale AWS Lambda cluster involving 256 worker nodes. We first analyze the response time of workers and provide empirical evidence of straggler patterns that are consistent with our modeling assumptions. We then demonstrate that the M-SGC scheme provides significant gains over all the other schemes in real world experiments.

---

Published as a conference paper at ICLR 2023
REFERENCES
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for Plyper-Paramenn Optimization. In Proc. Annual Conference on Neural Information Processing Systems, 2011.
Neelkamal Bhuyan, Sharayu Moharir, and Gauri Joshi. Multi-Model Federated Learning with Provable Guarantees. CoRR, abs/2200.04330, .04330, 2022.
Jean-Chrysostomee Bolot. End-to-End Packet Delay and Loss Behavior in the Internet. Proc. ACM SIGCOMM Conference on Communications Architectures, Protocols and Applications, pp. 289-298. ACM, 1993.
Rafael Valente da Silva, Jinho Choi, Jihong Park, Glauber Brante, and Richard Demo Souza. Mul- tichannel ALOHA Optimization for Federated Learning With Multiple Models. JEEE Wirel. Commun. Leut, 1 11(10)2210021844 2022.
Jeffrey Dean and Luiz André Barroso. The tail at scale. Commun. ACM, 56(2):74-80 2013.
Sanghamitra Dutta, Mohammad Fahim, Farzin Haddadpour, Haewon Jeong, Viveck R. Cadambe. and Pulkit Grover. On the Optimal Recovery Threshold of Coded Matrix Multiplication. IEEE Trans. Inf. Theory, (6(1))278-301 2020.
G. Forney. Burst-Correcting Codes for the Classic Bursty Channel. IEEE Trans. Commun. Tech., 19 (5):772-781, 1971.
Wael Halbawi, Navid Azizan Ruhi, Fariborz Salehi, and Babak Hassibi. Improving Distributed Gradient Descent Using Reed-Solomon Codes, In Proc. IEEE International Symposium on Information Theory, ISIT, pp. 2027-2031. IEEE, 2018.
Swanand Kadhe, Onur Ozan Koyluoglu, and Kannan Ramchandran. Communication-Effiica Gradient Coding for Straggler Mitigation in Distributed Learning. In Proc. IEEE International Symposium Information Theory, ISIT, pp. 2634-2639 IEEE, 2020.
M. Nikhil Krishnan, Seyederfan Hosseini, and Ashish Khisti. Coded Sequential Matrix Multiplication For Straggler Mitigation. In Proc. Annual Conference on Neural Information Processing Systems, 2020.
M. Nikhil Krishnan, Erfan Hosseini, and Ashish Khisti. Sequential Gradient Coding for Packet-Loss Networks. IEEE J. Sel. Areas lnf. Theory, 2(3):919 930. 2021.
Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, and Kannan Ram- chandran. Speeding Up Distributed Machine Learning Using Codes. IEEE Trans. Inf. Theory, 64 (3):1514-1529, 2018.
Songze Li and Salman Avestimehr. Coded Computing. Found. Trends Commun. Inf. Theory, 17(1): 1-148, 2020.
Raj Kumar Maity, Ankit Singh Rawat, and Arya Mazumdar. Robust Gradient Descent via Moment Encoding and LDPC Codes. In IEEE International Symposium on Information Theory, ISIT, pp. 2734-2738. IEEE, 2019.
Emin Martinian and Carl-Erik W. Sundberg. Burst erasure correction codes with low decoding delay. IEEE Trans. Inf. Theory, 50010):244-2500, 2004.
Aditya Ramamoorthy, Li Tang, and Pascal O. Vontobel. Universally Decodable Matrices for Dis- tributed Matrix- Vector Multiplication. In Proc. IEEE International Symposium on Information Theory, ISIT, pp. 1777-1781. IEEE, 2019.
Aditya Ramamoorthy, Anindya Bijoy Das. and Li Tang. Straggler-resistant distributed matrix computation via coding theory. CoRR, abs/2002.03515,, 2020.
Netanel Raviv. Itzhak Tamo, Rashish Tandon, and Alexandros G. Dimakis. Gradient Coding From Cyclic MDS Codes and Expander Graphs. IEEE Trans. Inf. Theory, 66(12):745-77489 2020.
Amir Saberi, Farhad Farokhi, and Girish N. Nair. State Estimation via Worst-Case Erasure and Symmetric Channels with Memory. In Proc. IEEE International Symposiun on Information Theory, ISIT, pp. 3072-3076. IEEE, 2019.
10

---

Published as a conference paper at ICLR 2023
A. M. Subramaniam, Heidarzadeh, and R. Narayanan. Random Khatri-Rao- Rao-Produut Codes for NumericallyStable Distributed Matrix Multiplication. In Proc. Allerton Conf. on Comm.,, Contr, and Comp., pp. 253-259, 2019.
Rashish Tandon, Qi Lei, Alexandros G. Dimakis, and Nikos Karampatziakis. Gradient Coding: Avoiding Stragglers in Distributed Learning. In Proc. International Conference on Machine Learning, ICML, volume 70, pp. 3368-3376, PMLR, 2017.
Haozhao Wang. Song Guo, Bin Tang, Ruixuan Li, and Chengjie Li. Hcterogeneity- Gradient Coding for Straggler Tolerance. In Proc. IEEE International Conference on Distributed Computing Systems, ICDCS, pp. 355-564. IEEE, 2019a.
Hongyi Wang, Zachary B. Charles, and Dimitris S. Papailiopoulos. ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding. CoRR, abs/1901.09677 2019b.
Yanzhao Wu, Ling Liu, and Ramana Kompella. Parallel detection for efficient video analytics at the edge. In Proc. IEEE International Conference on Cognitive Machine Intelligence, CogMI, pp. 1-10. IEEE, 2021.
Chien-Sheng Yang, Ramtin Pedarsani, and Amir Salman Avestimehr. Timely Coded Computing. In Proc. IEEE International Symposium on Information Theory, ISIT, pp. 2798-2802. IEEE, 2019.
Min Ye and Emmanuel Abbe. Communication-Comei International Conference on Machine Learning. ICML, volume 80, pp. 5606-5615 PMLR, 2018.
Efficient Gradient Coding. In Proc.
Qian Yu, Mohammad Ali Ali, and Salman Avestimehr. Polynomial Codes: an Optimal Design for High- DiggnnDDnnsi Coded Matrix Multiplication. In Proc. Annual Conference Neural Information Processing Systems, pp.
2017.
Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and Amir Salman Avestimehr. Lagrange Coded Computing: Optimal Design for Resiliency, Security, and Privacy. In Proc. International Conference on Artificial Intelligence and Statistics, AISTATS, volume 89, pp. 1215-1225. PMLR, 2019.
Qian Yu, Mohammad Ali Maddah-Ali, and Amir Salman Avestimehr. Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding. IEEE Trans. Inf. Theory, 66(3):1920-1193)) 2020.
Zhi-Hua Zhou. Ensemble methods: foundations and algorithms. CRC press, 2012.

---

Published as a conference paper at ICLR 2023
A
SUMMARY OF NOTATIONS
Table 2: Table of notations
Symbol
Meaning
Number of workers
J
Number of jobs
Delay parameter
The set of all integers
aa:
{i E Z a S S b}
la 6
{i mod i E [a b]}
++ [a: 6]T
ictilie [a b]
D
Dataset
D;
i-th data chunk
g(t)
Gradient corresponding to job-t
(i(t)
i-th partial gradient corresponding to job-t Number of data chunks
n
mlt)
Number of partial gradients computed by worker-i in round-t
Upper limit on the number of stragglers per round (GC, SR-SGC schemes) Tolerance parameter
(4(1)
Normalized computational load worker-i round-/
W.
Window size for the bursty straggler model Window size for the arbitrary straggler model
W
A
Upper limit on the number of stragglers in any window (bursty straggler model)
X
Upper limit on the number of stragglers in any window (arbitrary straggler model) Upper limit on the length of burst
B
N
Upper limit on the number of straggling rounds of a worker in any window Task result corresponding to job-l returned by worker-i (GC, SR-SGC schemes) j-th mini-task of worker-i in round-t (M-SGC scheme) Task result corresponding to job-t returned by worker-i (M-SGC scheme)
G()))
T((t:))
(t(())
B A BRIEF OVERVIEW ON THE USE OF CODING FOR STRAGGLER MITIGATION IN DISTRIBUTED COMPUTING SYSTEMS
Stragglers, or slow processing workers, are common in distributed computing systems and potentially delay the timely completion of computational jobs. One may use the following analogy understand the importance of erasure codes in the context of distributed computing. Consider an [n,, ki erasure code which encodes i bits of data to produce which could erase a few bits. Even if part of the n coded bits are erased by the channel in this case, the redundant (n k)) bits aid in data recovery. The final job result be obtained by the master in a distributed computing system may be compared to the k-bit data which is being encoded. Computations undertaken by worker may be thought of coded bit of an erasure code. Naturally, delayed responses due to stragglers correspond to bit erasures. The core idea behind existing works in the literature that erasure codes offer a way efficiently add redundancy to computations or data so that jobs can still be completed on schedule, even when some computations are unavailable. The use of erasure coding to combat stragglers in distributed computing systems is initially investigated in the work Lee et al. (2018) (in the context of distributed matrix multiplication). The survey Li & Avestimehr (2020) provides a comprehensive summary of recent developments in the area.
io coded bits for transmission over channel
Consider the following toy example to demonstrate the key idea employed in Lee et al. 2018).
Assume that the master node wants to distribute the job of computing A x across n = 3 workers, where any one of the workers could be straggler. The master will partition the columns of A as and 2,
[Ag A1]. It will now pass (Au, z}. {Ai x and {A₂ & (Ao A1), 2) workers respectively. Worker-i will attempt to compute AT x and return the result. Clearly, the master can compute A A x as soon receives results from any two workers and hence the system is resilient against one straggler.
12

---

Published as a conference paper at ICLR 2023
The gradient coding framework proposed in Tandon et (2017 examines the possibility of using erasure codes to perform distributed stochastic gradient descent in straggler-resilient manner. We borrow the following example from the original paper to highlight the key idea. Let the dataset D be partitioned into Do. D₃ and D2. Workers 0, and 2 store (Du, D1), (D1, D2} and (D2. Du respectively. Worker-O supposed to compute partial gradients {gu, 91 on data chunks (Du, D1} and then return tg _ du 2
+ 91 to the master. Similarly, workers and attempt to return & _ 91 92
and E - + 92. respectively. It can be inferred that _ 9u + 91 + 92 can be computed from the results returned by any two workers. For instance, suppose workers and have returned their results and worker-2 is a straggler. In this case, we have 2 2 + 91) (0) 92) 260 f
C ON THE USE OF GILBERT-ELLIO MODEL FOR STRAGGLERS
The Gilbert-Ellio (GE) model is 2-state probabilistic model with state transition probabilities as outlined in Fig. 3 In the context of modeling stragglers, a worker is a straggler if and only if it is in state S and non- straggler otherwise. a worker a straggler in a given round, will continue to be a straggler in the next round with probability (1 ps). Similarly, non-straggler will continue to remain so in the next round with probability (1 - PM)) In essence, the GE model suggests that straggling behavior occurs periodically and is often followed by non-straggling behavior.
PN
1- - PN
N
S
1 - ps
ps
Figure 3: The 2-state Gilbert-Elliot model.
In distributed systems, stragglers occur due to reasons such as resource sharing, communication bottlenecks, routine maintenance activities etc. The periodic spikes in latency that are caused by several of these factors (see Dean & Barroso (013);; Boooot (1993)) are naturally captured by the GE model. The authors of Yang et al. (2019) make an empirical observation that the GE model can accurately track the state transitions of workers an Amazon EC2 cluster, particularly in the context of applying erasure codes for straggler mitigation. using deterministic, sliding blddigg-indoww window-baat based models since they are more tractable in terms of code design. As our experiments indicate, such design strategy finally led to techniques that outperform the baseline GC
the current study, we approximate the GE model
Amazon Lambda cluster.
We will now present an intuitive justification on why candidate model straggler behavior in our work. Note that the diding-window-basee models introduce constraints on the local structure of straggler patterns. For example, in the bursty model, burst of straggling rounds is followed by a period when the worker a non-straggler. This provides a simplified approximation of the GE model, capturing the dominant set of straggler patterns associated with the GE channel (any other straggler pattern will be handled through wait-outs). Similarly, in the arbitrary straggler model, window without requiring that the straggling rounds consecutive. Finally, in our proposed setting of sequential gradient coding, it turns out that modeling local constraints straggler patterns using the sliding-window siindow-straggle model is a natural for job that starts in round-i and is completed in round-(i A), the straggler patterns around the interval [ A] are relevant.
wwwdwww-wdwwwaae -baee models are a natural
put a constraint on the total number of straggling rounds in each
D PROOF OF PROPOSITION 3.1
Consider a straggler pattern which conforms either (i) the (B, W, bubrssyyy straggler model or else, (ii) the s- e-stragglers-per-romm
model, in any window of rounds W, A [j : + W 1], j E [1 J + W + Let t' e [] J + TT] denote the first round in which there are more than
13

---

Published as a conference paper at ICLR 2023
stragglers. All the tasks attempted in round-t' correspond to job-t'. By assumption, the straggler pattern, when restricted to the W rounds [t' : t' + xB3 conforms to the (B, W, AJ-bursty straggler model. Let there be Åo > s stragglers in round-t'. In round-(t' + B), Au s tasks corresponding to job-t' will be attempted by Ao - s workers who were stragglers in round-t' (see Fig. 4 Because of the straggler model assumption, none of these workers will be stragglers again in round-(t' + B) and hence, job-l' will be finished in round-(l' + B) with delay B. Clearly, round- + B) is "deviation" from the (n, s)-GC scheme as not all tasks this round correspond to job-(1' + B). Suppose now there are a stragglers in round-(t' (t' + B). Thus, number of task results corresponding to job-(t' + B) returned by workers in round- + B) is given by n - ^ - λo + 8. If this quantity is greater than equal to n 8, job-(t' B) can be finished in round- (t' + B) itself and there will be a "reset" in round- + 2B) as all tasks there correspond to job-(t' + 2B). On the other hand, if (n- ->1- Ag 8) < (n 1a-55 s). (Ao +} 2s) tasks corresponding to job- ot' + B) will be attempted in round-(l' + 2B) by workers who did not return task results corresponding to job-(L' + B) in round-(t' + B). These workers can either be stragglers in round-(L' + B) or else, be processing tasks corresponding to job-t' in round- + B). In either case, these workers cannot be stragglers in round-(t' + 2B) owing to the straggler model (see Fig. 4.. Hence. job-(t
B) will finish in round- (t' + 2B) will delay B. Now, if not enough task results corresponding to job-(t' + 2B) are returned in round-(t' + 2B), the minimum-requie
number of additional tasks corresponding to this job will be attempted in round-(t' + 3B) and so on. We will now show that there exist an & E [1 2] such that jobs t", f' + B....,,' I' + (8 (8-18 B) are finished with delay precisely B and job-(t' + BB) is finished with delay 0. i.e. there is reset happening in round-(!' + (e+ + B).). In order to show this, (x B)B have some of their tasks attempted with delay B (i.e., no reset in rounds t' + 2B,, ........ t' + BB) Because of the straggler model, all these delayed tasks are guaranteed to succeed and hence all these jobs finish with delay B. We should now prove that there is reset in round-(t' (x + 1)),, i.e., f= = x. For j E [0 2 let ) indicate the number of stragglers in round-(t' + jB). Number of tasks corresponding to job-(t' + (x - B) attempted in round-(t' - xB) is given by Ào + \ + +................. A 1 28. Thus, number of task results corresponding to job-(t' + x3) received by master in round-(t' + BB) is given by:
assume that jobs t', ,',t' + B...., t'
n - A= - -Ao + A1 + Ao-1 - xs)
= λo
A1
Au + xS
z n + xs
2 n A
1 + 1) + x8
I x+1
= n 8(x + 1) +
8,
where have used the fact that do +... + Ar S X owing the straggler model. Hence, in summary, we have showed that if all of jobs 1', 1 + B, B....,'' l'
(x - 1)B finish with delay B, then t' xB finishes with delay 0 and there will be a reset in round-(t' + (x+ + B). Thus, there exist L E [1: æ such that all jobs t', + B, B...., t' + (f 1)B finish with delay B and job-(t' + BB) finishes with delay O. Because of the reset happening in round-(t'
((++))), the "effeet" of | is now confined only to rounds t', t' + B, B.....'' t' + LB. We can now safely regard rounds t', + B, .......''' t' + LB as straggler free as these rounds contain only tasks corresponding to jobs C',l' + B, B,...,,' + can now essentially repeat all these steps starting with finding the next "first" round-l' having more than stragglers. After repeating these arguments sufficient number of times, eventually, we will be left with jobs R C [1: : J]. where all rounds in R has at most s stragglers. Workers in each round-r, r E R, attempt only tasks corresponding to job-r. Thus, all these jobs can be finished with delay 0.
Algorithm
EB and we have shown that all these jobs succeed with delay at most B. We
This completes the proof.
E PROOF OF PROPOSITION 3.2
Consider the computation of (t), E [1 : JJ in the presence of a straggler pattern conforming to one of the following: (i) (B. W, X)-bursty straggler model or else, (ii) (N = B, 2,WW" = W B - X, = A)aarbitrary straggler model. By design of Algorithm 2 for each worker-i, mini-tasks OT) (i + 1;1),..., T,(t + W 2 + B; W 2 + B}} correspond to job-t. Master has to
14

---

Published as a conference paper at ICLR 2023
Tadls job-tr
Talls COTMED pob
Tublo
job (1)) 28)
corveo
Talb
de Aest
sorvep to
Talls coreip
Workers
A2
CONTRA to
Tasks
jab-t -
As
Tadks conrae pob-""
jes-0" +
Tasls (1
Tasks ornee job--"
Ap
job-12
Tadic
t'+
e'+ 2B
t tB
t' (f 1)8
Round
Figure 4: An illustration of task assignment in SR-SGC. In the initial rounds, the task assignment is precisely as in an s)-GC scheme and all tasks round-t correspond to job-t. any such round-f, if there are at most stragglers, job-t can be finished in round-t itself. Let t' denote round where all tasks correspond to job-t' and there are Àu stragglers. Stragglers are indicated in grey color. In round-(l' + B). there is deviation from the (n, s)-GC scheme as Å tasks corresponding to job-l' will be attempted this round (these tasks which are attempted with delay are indicated in orange). These tasks are attempted by workers who did not return task results corresponding to job-t' in round-t'. round-(t' + B). n A1 Ào + s workers return task results corresponding to job-(t' + B). If this quantity is lesser than
Åo + 0 2s tasks corresponding job- (t' + B) will be attempted in round-(t' + 2B) by workers who did not return task results corresponding to job-(t' B) in round-(t' B). The process is continued in similar manner. If the straggler pattern in the window of rounds [t' t'' BB conforms to the (B, W, A}-bursty straggler model, there exists an l E [1 -] such that in round-(t' + (f + B) "reset" happens back the (n, s)-GC scheme, ie., in round-(f" (t' + (E + 1)B) all tasks correspond to jtb-(t' + (e + 1)
Round
J((s.0)
T(600)
J,0:0)
7,0%,0)
7,0%00
T,010,0)
1((x1)
T(6:1)
7,0x1)
7,00
7,0:1)
7,00,11
T(5:2)
T(6:2)
7x7:2)
7,08:2)
(,9:2)
3,00:2)
T(5:3)
T(6:3)
7,(:3)
7,08:)
7,0:3)
3,(10:3)
Mini-tasks corresp. to job-5
Figure 5: Figure corresponding to the M-SGC example provided in Sec. 3.3. scheme, all mini-tasks across "diagonal" correspond to the same job.
For M-SGC
15

---

Published as a conference paper at ICLR 2023
9u(1)
9u(2)
[o(3)
8e(4)
(e(5)
Bu(
91(1)
(:(2)
0:(3)
(:(4))
Si (5)
Worker-0
0
(o(1)
(o(2)
(3)
(4)
(x(1)
(2)
(o)
9x(1)
9x(2)
(2
(2(4)
(2(5)
9z(6)
9s(1)
8:(2)
8:(3)
(x(4)
gs(5)
Worker-1
9x(1)
(2)
(2)
(4)(4)
0
(1(11)
8a(2)
(1)
(x(1)
(x)
(3)
(x(4)
(x(5)
(x(
0
9s(1)
8s(2)
8s(3)
(s(4)
@s(5)
Worker-2
0
(2)(1)
(2,0(2)
(2)
0s(4)
(1)
(2x(2)
(2)(3)
(6(1)
9x(2)
86(3)
86(4)
8c(5)
5.(6)
9-(1)
(+(2)
(:(3)
4x(4)
9-(5)
Worker-3
0
0
(0)(1)
(2,0(2)
(3)
(s)
0
0
(1,((1)
Pax(2)
(3,(3)
1
Round
Figure 6: Figure corresponding to the M-SGC example provided in Sec. 3.3.1 Rectangles depict mini-tasks (shaded ones have failed due to stragglers). Reattempted mini-tasks are indicated in red. Mini-task results in blue are linear combinations of 3 partial gradients.
compute:
g(t) -
Σ
(t) +
Σ
(t
JE[D:(W -1)=-1]
LE[(W 1]n: Bmn
g'(()
by the end of round-(t + 7", where T W 2 B. If = only have the g'() part and set
(t) 0. We will now show that master will be able to compute each of (g'(t), (t)} individually by the end of round-(t-2) + W - B) in presence of straggler patterns conforming to one these straggler models.
Computing (t): From Algorithm| 2 it can be noted that mini-task Ti(t + j:J). E [0: W
involves computing B)4-1)4 (t). worker-i is not straggler in all the rounds i t W 22,
clearly, master can compute Σ ((( in the end of round-(t (t + W - 2).
Now, consider the remaining situation that worker-i is straggler in at least of the rounds within [t ::: t + W 2]. We initially discuss the case that the straggler pattern conforms to (B, W, A)-bursty straggler model. Worker-i experiences at most B straggling rounds (see Fig. among rounds it:t+ W + B). Suppose worker-i is a straggler in x' rounds, x' E [1 B, within rounds 11 W 2]. Thus, x' partial gradients among ()(W-1)+;(())) [ are returned by worker-i in rounds [t t + W 2]. However, Algorithm| 2 reattempts those failed partial gradient computations in rounds [t - W -1:t+ W 2 B). Even there are B x'' straggling rounds among it + W- 1 --::: successfully computed. Hence, using mini-task results returned by worker-i, master can compute by the end of round-(t (t + W 2 + B). By accumulating results from all the n workers, master will able to compute g' (t) by the end of round-(t + - B).
W - B), in the remaining x' rounds, the failed partial gradients will be
E5e (:(WW[WW+++
We now consider the case where straggler pattern conforms to the (N B, W" WW X)- arbitrary straggler model. As per the model, a worker can be a straggler in at most N = rounds in any sliding window consisting of W' W 1 + B consecutive rounds. Let worker-i be straggler in z" rounds (x." E [1 B) within rounds [t : + W- - and at most - rounds within [t + W 1 t W - + B). Clearly, z" mini-tasks among {9. (((w))))(tt) fail in their first attempt. However, as worker-i is non-straggler in at least x" rounds within
16

---

Published as a conference paper at ICLR 2023
+ W - 11:+++W - 2 BJ. these mini-tasks will eventually be repeated and finished. Thus, master computes 2je(0.w-3
by the end of round-(t++ + W - 2 + B). Collecting results from all the n workers, master will be able to compute g' (t( by the end of round-(t (t + W 2 B).
Computing (t):): Again, we begin with discussing the case where a straggler pattern conforms to the (B, W, XJ-bursty straggler model. For any straggler pattern conforming to this straggler model, there exist (n Ah-A, workers who do not have any straggling rounds among any window of rounds of the form W; _ [i= j - I]. In particular, consider the rounds in Wt. Assume that worker-i does not have any straggling rounds in the window W,. Thus, mini-tasks {Ti(t + I; 1/ partial gradients
W-2 will be successful and (t) W- will be computed in the first attempt. Hence, from Algorithm 2 it can be inferred that the mini-task (t(t. + W W 1) involves computing (t). As worker-i not straggler in round-(t + W 1), master receives the linear combination (t)) As there are (n X) such workers returning (t)(s)'s. owing to the use of (n, A)-GC, master can compute =e:( 9: (1) by the end of round-(t + - 1). Similarly, due to the (B, W, A)-bursty straggler model assumption, there are (n A) workers who do not have any straggling rounds in the window W++1
+ t + W]. Let worker-i' be one such worker. All the mini-tasks (T& + 1; To + W 2: W 2)} will be successful and (or(w-1)=+(t)}=>
will be computed in their first attempts. round-t, worker-j' can possibly be a straggler. However, as worker- i' is not a straggler in (f + W - 1). the failed computation of (1) will be reattempted and finished in round-(t + W - 1). Thus, by the end of round-(t + W -1), all partial gradients W- are guaranteed to be computed. Hence, mini-task Ti-(1 + W; W) involves computing (4). As round-(t + W) is a non-straggling round, master will receive (t) in the end of round-(t + W). Using (n X) such & (t)'s, s, master can compute Eielw +1)m- 9 (t). In a similar manner, it can be argued that, for m E [0: B 1], master will able to compute 9: (4) in the end of round-(1 + W - + m). Hence, by the end of round-(t+ W + B), master is able compute gt).
In the case if straggler pattern conforms to the (N = B, W B 1, = A)-arbitrary
straggler model, there n workers who do not have any straggling rounds in [L: [1: 1.:+ W 2 BB For any such worker-i, computations of (9r(W- 1)+
are all finished by the end of round- (t + W - -2). Hence, in round-(t + f). E IW - W - 2 + B). worker-i will compute and return #:j-w+1(() to master. Using (n, A)-GC, results from n - À such workers can be used by master to obtain Σie(m(++)>=)) ((). Thus, by the end of round-(1 + W 2 B), master is able to compute (t).
( (t)
F NEAR-OPTIMALITY OF M-SGC SCHEME
As seen earlier, SR-SGC scheme offers a clear advantage over GC scheme, as tolerates a super set of straggler patterns; bursty and s-stragglers peeess-pe--ouuudd straggler patterns, for the same normalized
W
B
Worker
Round
W
(a)
W 1--1y
Workers
Round
i+y
W
(b)
Figure In the figure, shaded boxes depict straggling rounds. Consider straggler pattern conforming to the (B, W, -b-burstty straggler model. The straggling rounds, if any, seen by worker-i among rounds [t +++++ W 2 B) will be subset of the B straggling rounds indicated in either situation (a) or (b). Here E [1 B). y E [0 W - 1].
17

---

B) rounds where Published as a conference paper at ICLR 2023
load of s+1 In the case of M-SGC scheme, the normalized load substantially smaller as we note in Remark 3.3) We will now show that the M-SGC scheme is near-optimal in terms of normalized load. In the theorem below, we derive a fundamental lower bound on normalized load of any sequential gradient coding scheme which tolerates straggler patterns conforming to the (B, W, X)- bursty straggler model.
Theorem F.1. Consider any sequential gradient coding scheme, which tolerates straggler patterns permilted by the (B, W, Xj-bursty straggler model. Let the normalized load per worker be constant, T oc and the number of jobs J + co. We have the following:
W-I+B
if < W
L L
-
if W.
Proof. We divide the proof into two cases; B < W and B = B.
B < W: Consider the periodic straggler pattern shown in Fig. 8 which conforms to the
(B, W. X)-bursty straggler model. Consider now the first (
17 0 is large enough integer. There are nB straggling rounds faced by workers among these r7(W 1 B). The workers can compute at most gradients (e[t))/w1: in these rounds. However, the computations that workers can perform is also limited by the normalized load L. Specifically, a worker has normalized load L, is able to compute L fraction of job (full gradient) in round. As there are nBA straggling rounds faced by workers [0 : À 1] in rounds 7 1 + B)], the number of jobs that will be finished by non-straggling workers in these rounds is most:
[min (Ln(W 1 B), LL(WW - 1 B) BA)))J
gradients. If < Li. we have nL(n(W - + B) -B) < nW - 1 + B) and thus, in the end of first n/WW 1 B3 rounds, there are
[n(W + - - -
B) BX) > 0
pending jobs among | ( - + B)] which need to be finished. The number of pending jobs clearly increases as increases. In order to satisfy the delay constraint T, is necessary that all these pending jobs need to be processed in rounds 1 B) + n(W - + B) + T7. On the other hand, the number of jobs that can finished in these rounds is at most [T (under the best-case scenario that all the workers are stragglers in these T rounds), which bounded. As T < oo, for a sufficiently large n, + B) (T[nn(W- + B) B))]. Thus, at least one of the jobs in [ : vW - 1 + B)] cannot be finished with delay T < L.g. Thus, we have 2 Lig.
[ [n][W
B = W: Consider the periodic straggler pattern depicted in Fig. 9 which conforms to the (B, W, X)-bursty straggler model when B W. Here, L Li there are (n X)] pending jobs after rounds [1 v]- Following similar arguments as in the B < W case, for sufficiently large y) delay criterion T cannot be met and thus it can inferred that L.j.
Worker-O
Worker 1)
W
Worker
Round
Figure 8: A periodic straggler pattern conforming to the (B, W, bu-usssytty straggler model, when B < W. Here, the shaded boxes indicate stragglers.
18

---

Published as a conference paper at ICLR 2023
Worker-O
Worker-(A 1)
Worken
Worker-
Round
Figure 9: A periodic straggler pattern conforming to the (B, W, A)- straggler model, when
B = W. Here, the shaded boxes indicate stragglers.
An analogous result can be shown with respect to (N, W W', arbbbirtayyy straggler model as well.
Theorem F.2. Consider any sequential gradient coding scheme, which tolerates straggler patterns permitted by the (N, W", -'rbbitry straggler model. Let the normalized load per worker L be constant, T < co and the number jobs J + co. We have:
W
if < W IN W.
L2LA A
N N
(3)
Proof. The proof here follows in similar manner that of Theorem F. and hence, details omitted. For the case N < W", consider Fig. [0] (analogous to Fig. 8). Considering first 7/W' rounds, if L L number of pending jobs is given by ((W'))nL(ww)
NA) If sufficiently large, we have [n]]] < [' - nb(nWW' NA) and hence, at least one of the jobs cannot be finished with delay T. Thus L 2 L When N W" if is replaced with X' in Fig. 9 we obtain a straggler pattern conforming to the (N, W X')arritryyy straggler model. The proof follows precisely as in the case of
Theorem F.1 (with À replaced by X).
W
N
Worker-I
Worker-(2' 1)
Worker-X
Worker (e 1)
N
W +
2W"
Figure 10: A periodic straggler pattern conforming to the (N, W "V,,A-rrrittrary straggler model, when N < W'
Remark F.1 (Optimality). From equation Ianiiionnaand equation it can be observed that when À = n or n, M-SGC scheme optimal as scheme tolerating any straggler pattern conforming the (B, W, X)- bursty straggler model. In an analogous manner, using equation and equation shown be optimal when X'
3 M-SGC can be
(with respect the (N B, W W - A)- arbitrary straggler model), Moreover, for fixed n, B and X, the gap between equation and equation 2 decreases O ).). In Fig. [1 we plot normalized loads of SR-SGC and M-SGC schemes and compare it with equation Similarly, gap between equation and equation decreases as 0 ((1)))
19

---

Published as a conference paper at ICLR 2023
Optimal SR-SGC
M-SGC
Normalizeed Load
0.12
0.10
0.08
0.06
10 15
20 25
W
Figure 11: A comparison of normalized loads incurred by SR-SGC and M-SGC schemes when {n 20, B 3, À 4} and W is varied. Note however that delay parameter I values in the case of SR-SGC and M-SGC schemes are given by and W + B, respectively. Hence, terms of scheduling tasks (see Remark 2.1 SR-SGC scheme offers more flexibility.
Worker 0
fd11
4,01)
4,03
Kg151
fg(5)
Worker-0
Hgl1)
(g(2)
8,13)
9,44
8,151
9,161
8613)
0
8613)
9.15)
Worker-1
6,01
4,04)
4,(3)
6,03)
6,151
4,05)
Worker-1
((11)
((22)
8.(3)
[.(4)
0.(51
9,(6)
81(3)
0
9.(3)
(915)
Worker
8,13
(,12)
4,131
(,64]
4,151
8,161
Worker-2
8:13)
8:(2)
8.133
8.(4]
9:151
9:161
8:(1)
9,13)
Worker-3
F,(3)
4,(2)
4,(3)
(,(4)
k,(5]
f,(61
Worker-3
85(3)
85(2)
87(33
89(4)
9,151
9g161
(9.13
.915)
Round
Round
(a)
(b)
Consider parameters {n - 1, 2, 2 4); (a) SR-SGC scheme: reattempted tasks are indicated in red (b) M-SGC scheme.
Figure 12:
Example F.1. In Fig. 12 perform comparison of normalized load incurred by SR-SGC and M-SGC schemes for parameters (n = 4, B W = 2, = 4]. We consider a straggler pattern conforming to the (B = 1, W 2, = 4)-bursty straggler model, where in alternate rounds (rounds both the schemes, data set is partitioned into 4 data chunks (Do. D1, D2, D3). In Fig. 12 (a). show the SR-SGC scheme. Here, the quantity (t( is linear combination of 3 partial gradients {t) (application of (4, 2)- Hence, normalized load is 3. On the other hand, in the case of M-SGC scheme (Fig. 12 (b)), each worker in round computes 2 partial gradients and hence, the normalized load is 2- In both the schemes, even though all the workers are stragglers in round-(2t 1) (t 1, master is able to compute g(t - 1) and (2t) together after receiving task results from workers in round-2/. In the SR-SGC scheme, the increased computational load is due to the use of (4, 2)-GC to compute 2 jobs in round-21 (corresponding
1,3, .,...). all the workers are stragglers.
each of jobs (2/ 1) and 2/, there are tasks being performed in round-2(), Being a scheme where coding is only across workers (and not across rounds), in the (4,2) GC scheme, partial gradient computations on each data chunk are attempted by 3 distinct workers and this contributes to an increased load. On the other hand, in the M-SGC scheme, by repeating mini-tasks across rounds, we achieve optimal load which matches equation
G GRADIENT CODING: SIMPLIFICATION FOR SPECIFIC PARAMETERS
The gradient coding approach in general works for any such that S s n. For instance, let = 2 and n 6. As per the general (n, s)-GC scheme (see the description in Sec. 3.1), the master partitions the dataset D into n data chunks Do...., D5- These data chunks are then placed across = 6 workers shown in Fig. 13 Here, worker-O is expected to compute the partial gradients
20

---

Published as a conference paper at ICLR 2023
90:91 91. 92 and then return to a0,090 + 00,191 20,292. Similarly, worker- I supposed return
01119 + 01,292 + 01 .393 and so on. The master can reconstruct g - 90 + 91 + ... + as linear combination of any (n 8) returned their results to master initially. The master will now perform the decoding step of computing (,0,2.455). 11..2....00..55 2,5,,,4,5),5$3, However, in the work Tandon et al. (017)) the authors note that for the special case when (s + 1) divides n, there exists an alternative, simpler approach that only requires trivial decoding procedure. We will now demonstrate this idea for 6, 2. In Fig. 14 we outline how data fragments
L'ss. For instance, assume that workers 0, 2, 4,
g (00,2,455),00 + (,5,2,4,5,.244
placed in this simplified GC s+1 = groups. The computations done across workers
scheme. Here, workers are divided into
within each group are simply replications of each other (for this reason, we will refer to the simplified GC scheme as GC-Rep). In particular, workers in group-0 are supposed to compute Jo- 91: 92 and
return ((0) go + 91 + 92. Similarly, workers in group-1 need compute y3, 94, 95 and return ((1) 9s + 94 95- In order to decode g. the master just needs to compute the sum g(0) g(1), which always possible there are only 8 2 stragglers. decoding, the GC-Rep scheme offers improved straggler resiliency in the following sense. If there more than s stragglers, there is no guarantee that GC will recover However, GC-Rep can tolerate the straggler pattern long one worker in each group is non-straggler. For instance, the GC-Rep scheme succeeds even workers 1, 1,2,3 and are stragglers. Since neither worker-O) nor worker-4 computes the partial gradient 93. GC will fail in this scenario.
addition the simplicity with respect to
Both M-SGC and SR SR-SGC schemes can leverage the existence of the GC-Rep scheme. If (A + 1) divides n, may the GC-Rep scheme in combination with the M-SGC scheme, since the latter employs an (n, A)-GC scheme to protect some of the computations from stragglers. We will refer to this modified M-SGC scheme as the M-SGC-Rep scheme.
RA 1 may GC-Rep instead of Similarly, in the case of RRC scheme where W
GC as the base scheme if (s + 1) divides (let the new scheme be called SR-SGC-Rep). In order exploit the fact that all workers within group-i return the same result g(3) in the GC-Rep scheme, present below minor modification of Algorithm[] | Recall the definition of N M(t,, which denotes the number of task results corresponding to job-t returned master in round-t.
D
D
D
D
D
D 5
D
D2
D
D
D
D
D2
D3
D
D
D
D 1
Worker-0
Worker-1
Worker-2
Worker-3
Worker-4
Worker-5
Figure 13: An illustration of the placement data chunks across workers the general GC scheme for parameters 6, 2.
21

---

Published as conference paper at ICLR 2023
Do
Do
Do
D3
D3
D3
D
D
D1
D
D 4
D
D2
D2
D2
D5
D
D 5
Worker-0
Worker-1
Worker-2
Worker-3
Worker-4
Worker-5
Worker group-0
Worker group-1
Figure 14: An illustration of the placement of data chunks across workers for the simplified GC scheme when n = 6, = 2. Here, worker-i belongs to group-L=4f)
Algorithm 3 The algorithm which may be used by the master to assign tasks in round-t for the SR-SGC-Rep scheme (valid only if (s 1) divides n).
Initialize (t B). for i (0:n 1] do
if (( B) is returned by some worker in group- 1.4 in round-(t- B) then Worker-i attempts to compute e(lotr!)(t))
else if 8 n and J( B) is not returned previously by worker-i in round-(t B)
then
Worker-i attempts to compute ((( B). Set 8 = +1
else
Worker-i attempts to compute (().
is worth noting that the computational load for GC-based and GC- -ec-Ree-adeed schemes is the same. Although decoding in GC-Rep- based schemes is simpler, decoding time may be included into the master's idle time (see Appendix K). this will not have any impact on the total run time. However, enhanced straggler resilience of GC-Rep-based schemes may lessen the number of rounds in which the master must perform wait-outs, potentially reducing the overall run time.
Under identical load conditions, the SR-SGC-Rep scheme always permits strict superset of straggler patterns compared to the GC-Rep scheme, as is the case between SR-SGC and GC. Therefore, SR-SGC-Rey anticipated outperform GC-Rep. direct comparison between M-SGC-Rep and GC-Rep is not feasible in terms of the straggler patterns tolerated by these schemes. However, because M-SGC-Rep requires substantially lower computational load than GC-Rep, is expected to perform better than the latter.
H AWS LAMBDA ARCHITECTURE
This section discusses the overall architecture, limitations, and additional details about the setup and usage of the AWS cloud resources used in our experiments (Sec.
We use AWS Lambda functions as workers in our distributed training experiments. Each Lambda instance has 2500 MB of RAM. 1 vCPU, and supports Python 3.8 runtime environment. A Lambda layer is used to inject external dependencies into the runtime environment (e.g. Py Torch. Torch Vision, NumPy etc). Since the size of required external libraries exceeds the 200MB limit of Lambda layers, we zip some libraries in the layer package and unzip them at the time of Lambda instance creation. Note that this will not affect workers' run times as we perform a warm-up round before each experiment to ensure that our Lambda instances are initialized and functional.
22

---

Published as a conference paper at ICLR 2023
Another limitation concerning the use of Lambda functions for training ML models is the total payload size quota of 6 MB. i.c., the total sum of payload sizes in the HTTP request and response cannot exceed 6 MB. Note that ideally the master includes current model weights in the HTTP request payload, and receives the task results via the HTTP response payload. This incurs a serious limitation on any reasonably-siae neural network. To overcome this, we need use proxy storage service to communicate model weights and task results.
Fortunately, we have two storage options; Amazon (Simple Storage Service) and AWS EFS (Elastic File System). We use the latter, it will provide higher throughput. EFS is shared network file system that will be mounted on all Lambda instances at their time creation. This way, can be used means for communication between the master and workers. In our experiments, the payload limit for the task result communication, and use EFS to communicate updated model weights workers, as depicted in Figure L3 (a). The overall architecture of our cloud resources is shown in Figure 15 (b). We use AWS Serverless Application Model (SAM) tool to define, manage, and deploy the cloud resources (included in the code submitted supplementary material).
reserve
HTTP
VPC
(3) Involi
Master
(1) Upload Model Weights
Cloud
(4) Send Teak Rleults
Mounr Target
(3) Read Model
Weights
Workers
(b)
Figure 15: (a) Communication between master and Lambda workers at each round. (b) The overall architecture of AWS cloud resources used.
I EXPERIMENTAL SETUP AND POTENTIAL APPLICATIONS
We provide here more detailed discussion of the experimental setup in Section 4.2 We consider training M 4 neural networks, denoted by NN,, NN,, NN3 and NN,. For neural network NN; where j = 1, 2, 3, 4, we let w denote the initialized weights and w." denote the weights after total of i rounds of gradient descent updates i.e.,
(f)
(i-1) C gj
(4)
(8-1) denotes the gradient associated with neural network NN, with weights w (f-1) and e where g denotes the learning rate. We assume that the training NN NN2, NN, and NN, is interleaved across rounds i.c., model updates for the interleaved training uses the following schedule:
23

---

Published as a conference paper at ICLR 2023
Weights of INN1 1 are updated in rounds:
(Initialization), 5, 9, 13, ...
Weights of NN2 updated in rounds: 2 (Initialization), 6, 10, 14,
Weights of NN3 updated in rounds: 3 (Initialization), 7, 11, 15,
Weights of NN4 are updated in rounds: 4 (Initialization), 8, 12, 16,
Thus if we consider the training of say NN1, then there two steps:
Step 1: At the start of round- (4i + 1), the server will generate w (6) It will have decoded the
gradient vector gi ((-1) by the end of round-4i and performed the SGD update in equation 4
Step 2: The server will issue a request at the start of round-(4i + 1) to the workers to compute the associated partial gradients such that the gradient vector g(" can be computed by the end of round-(42 + 4).
By following a similar approach for each model it is clear that for neural network NN,, when computing the gradient gj request will be issued by the server to the clients at the start of round-(4i + j) and the computation must be completed by the end of round- + j + 3). Thus our interleaved approach is designed so that that each of the gradient vectors can be decoded within span of M rounds.
Our method can be viewed as pipelined approach for training of multiple neural networks. Note that in our current setting we assume that the parameters of only one model can be updated in each round, which arises in resource constrained devices. Our method also naturally complements other approaches for parallel training of multiple models and leverages on the temporal structure of straggler patterns to achieve speedups. We also emphasize that we do not require the multiple neural network models be trained on the same dataset. Each neural network model can be trained on different dataset. We also do not require that the architecture of the neural network models being trained to be identical. Nevertheless we point out that our setting would be most efficient when the compute time for the gradients for each model is approximately the same. We believe this is rather benign requirement. Finally we discuss a few applications where multiple-model training arise naturally.
In the training of deep learning models, we are often required to perform search over various hyperparameters and this done through some form a grid search (Bergstra et al.) (011). Each choice of hyperparameter corresponds hyperparameters are selected through a validation set.
model. Ultimately the ideal
In ensemble learning (Zhou 2012), a number of models need to be trained simultaneously. Their predictions are then combined through some averaging mechanism.
Since approach can completely different datasets for each of the models, it is also applicable in settings of "multi-model learning" (Bhuyan et al. 2022 da Silva et al. [2022). where multiple datasets are used for different models. For instance, sensors deployed in vime-narying or periodic environment (e.g., day/night camera images, orbiting satellite data etc.) or collecting different modalities (speech, images etc.) would naturally generate multiple datasets and different models should be trained for each one. Multi-model learning has also been applied real-tine time video surveillance applications (Wu et al. 202T).
J SELECTING CODING SCHEME PARAMETERS
This section discusses the parameter selection method used for our proposed sequential gradient coding schemes, SR-SGC and M-SGC. We begin by noting that the total number of valid parameter combinations for each of these schemes are too large for grid search to be feasible, as evaluation of each parameter combination requires training models for multiple rounds. Instead, we utilize the observation that increasing the normalized load will linearly increase the average runtime of the workers. Fig. shows the average job completion time of 256 workers across 100 rounds for multiple values of load in [0, 1].
We can exploit the observation above to estimate the delay profile corresponding to various coding schemes with variable normalized loads. After estimating the slope of linear fit in Fig. 16 (1et this
24

---

Published as a conference paper at ICLR 2023
3.0
Linear Fit
2.5
Avg. Run
Avg. run time (s)
2.0
1.5
1.0
0.5
0.0
0.0
0.2
0.6 Normalized Load
0.4
0.8
1.0
Figure 16: Average run time (256 workers, 100 rounds) scales linearly with workers' computational load.
be a), our distributed training experiment for T proe 80 jobs with no coding, and store the observed runtime workers across rounds (we call this the reference delay profile). Note that the normalized worker load in case of coding will be 1/n.
Next, consider a coding scheme with fixed parameters B, W, X, and a fixed normalized load of L. We estimate the runtime of our coding scheme by feeding the reference delay profile to the master node to simulate the run time of workers. Based on our previous discussion, we should take into account the increase in the workers' run time due the increase of the load from I/n to L, by adding (L (--1nn)e seconds to our reference delay profile. Using this load-adjusted delay profile and the considered coding scheme, the master node will try resolve stragglers at each round, and if not, will wait out all the workers, resulting in simulated total run time for the coding scheme.
Fig. 17 shows the estimated runtime of 80 rounds for different choices of parameters B, W, in SR-SGC and M-SGC. For each of the two schemes, we select the parameters corresponding to the smallest estimated training runtime, denoted by the blue circles on Fig. and listed in Table
J.1 SENSITIVITY TO PARAMETERS
The Fig. 17 also demonstrates sensitivity of the coding schemes to their parameters, where observe smooth changes in training time with respect to coding parameters.
For SR-SGC, the normalized load varies significantly with the choice of parameters: L s+1 with
BA [ w - B ]. Specifically, the load directly proportional to As observed in Fig. 17 (left), for each choice of B and W. increasing above certain threshold leads significant increase in the runtime. Therefore, À should be chosen carefully as it will affect the load and runtime heavily.
On the other hand, the computational load in M-SGC is less dependent on selected parameters, as Therefore, the choice of À does not play
the load is upper-bounee bounded by 2/n (see Remark 3.3 crucial role as long is above the typical number of stragglers. Also, as observed in Fig. 17 (right), runtime is fairly insensitive to the choice of B as long as W and B are close.
Remark J.1. Recommendations for selecting parameters of M-SGC and SR-SGC:
Keeping W close B seems to be the right rule of thumb for both schemes. Also, the dependence of both schemes on B is less critical and increasing W is generally not preferred it reduces the straggler correction capability of the coding schemes.
For M-SGC, the choice of not critical as long as is above a certain threshold, but for SR-SGC it is an important consideration it affects the load significantly.
25

---

Published as a conference paper at ICLR 2023
Therefore, is recommended start with fixed B, choose W as close possible to B, and find large enough À for M-SGC or a small enough À for SR-SGC, based on the straggler pattern.
DH2
D+2
120
1.00
300
155
310
300
24C-
150
1.5
132
250
122
355
300
:00
Figure 17: Estimated runtime of 80 rounds for different choices of parameters B, W, A. Left: SR-
SGC, Right: M-SGC. Blue dot marks the shortest runtime (selected parameters).
Next, we evaluate the sensitivity of parameter selection the number of rounds used in the selection process probe- Table 3 lists the selected parameters using different values of Tprobe. For each unique set of parameters, we performed the experiments discussed in Section 4.2 10 times and included the average runtime well. As expected, we observe a general trend of improvement in total training time by increasing Trobee. Moreover, for M-SGC even few number of rounds are enough to tune the coding scheme, as M-SGC with parameters selected over only 10 rounds outperforms other coding schemes across other values of T probe-
26

---

Published as a conference paper at ICLR 2023
Table Selected parameters using different values proee
Scheme
T prohh
Selected Parameter
Load
Runtime (avg. + std.)
10
(1, 2, 24)
0.007512
8
20
(1, 2, 24)
0.007512
872.78 80.67 (s)
M-SGC (B, A)
40
(1, 27)
0.007543
871.99
60
27)
0.007543
871.99 59.76
80
(1,
0.007543
871.99 + 59.76
10
3,)
0.035156
20
12)
0.035156
1226.90 (s)
SR-SGC (B, W, X)
40
(2,3,20)
0.042969
60
(2,
0.046875
964.06 # #3.488 (s)
80
(2,3,23)
0.050781
984.37=51.00
10
(9)
0.039062
7288.57
20
(10)
0.042969
1261.61 $0.161
GC (8)
40
(11)
0.046875
1168.67
77.60
60
(14)
0.058594
1142.01 1 # (8)
80
(15)
0.062500
1067.56 40.92 (8)
K ANALYSIS OF OVERHEADS
In this section we discuss two overheads in proposed sequential gradient coding schemes, well as ways to effectively remove those overheads in practice.
K. DECODING TIME
At the end of each round, the master node decodes the task results obtained from subset of workers to calculate gradients. Both sequential coding methods proposed in this paper use GC as their core
BA coding/decoding method: SR-SGC with parameters {B, W. uses an (n, w w-1+B 1GGG and M-SGC uses independent (n, X)-GC schemes. (n, s)GG, gradients are simply obtained by linear combination of task results from workers (Tndon et al., 2017). Therefore, decoding consists of two steps:
1. Finding the decoding coefficients based on the observed straggler pattern. This can be done solving linear matrix equation.
2. Calculating the linear combination of task results from non-straggling workers, using the coefficients from step 1.
Table summarizes the decoding time for the main experiment presented in Section 4.2
Table 4: Decoding time of different schemes
Scheme
Parameters
Decoding Time (avg. std.)
Longest Decoding
Fastest Round
M-SGC
B = W = 2, 27
290 = 18.7 ms
479 ms
1177 ms
SR-SGC
B W =3, 23
309 + 20.1 ms
401 ms
1349 ms
GC
= 15
204 + 20.6 ms
408 ms
1379 ms
We would like to point that if training of more than T' models is pipelined, the decoding can be done in the master's s idle time, and the decoding time will not add any overhead to the training and
time. As stated in Remark 2.1 and further explained in Appendix [ when the decoding delay of the sequential coding scheme is 7 rounds, training at least M = T + models needs to be pipelined. rounds, the gradient of each model ready to be decoded D = M - T rounds earlier than the next round of the model begins. In case of M T 1, the gradients of model are ready for decoding just before the next round for the model begins (D= 0). However, when M T + 1. i.c. D > 0, the master node has at least one
Specifically, with M models and decoding delay
27

---

Published as a conference paper at ICLR 2023
gap round decode the gradients, and therefore can run the decoding at its idle time while workers are performing their assigned tasks. We emphasize that this is indeed applicable to the experiments presented in Section 4.2 where M and the delay of all models smaller than M
3.
As an example, let us consider the SR-SGC scheme with parameters { 2, W = 3, A - 23} discussed in Section 4.2 where M and T 2. Calculations of gradients for model start at rounds f = f2 = 5, t3 = 9, ... Calculating the first gradients of model starts at round & 1. By the end of round 1 of model are to be calculated at round 12 5. Therefore, the master node can perform the decoding during its idle time over round 4, when it is waiting for the worker nodes (note that as can be seen from Table the longest decoding time is shorter than the fastest round time). This way, the gradients are decoded before round t2 = 5 begins and thus no decoding overhead imposed.
3, the gradients are ready be decoded. Note that the second gradients
K.2 PARAMETER SELECTION TIME
In Section discussed the process of selecting parameters (B, W. }} for the coding schemes. This process requires running uncoded training for some number of rounds (Tproee) and storing the job completion time of workers. This delay profile is then used search for the best coding parameters. In the experiment section 4.2 we started coded training from round-1 (delay profile measurement and selection of best parameters are done beforehand). However, in practice, one can opt start with uncoded training in round-1 and then switch to coded training after prete uncoded rounds (a few additional rounds will be needed to perform the exhaustive search for the best parameters as well). This way, the time to be spent initially for delay profile measurements can be utilized towards completion of jobs.
Fig. 18 demonstrates this method in which training starts uncoded, and after Torohe 40 rounds, master node uses the observed delay profile from the past rounds to perform an exhaustive search for the best parameters of the coding schemes. In this experiment, it took ~ 8 seconds for SR-SGC, 2 seconds for M-SGC, and less than a second for GC to search over all valid parameters. The training then switched to coded mode after the search is over. Here, still observe significant gains from M-SGC compared to uncoded and GC methods.
MSGC
SRSGC
400
No Coding
Number jobs done
300
SR990 No Ceding
200
coding slarts!
extchex untodal
100
ooded tniinin
searching parameters
0
200
400
600
800
1000
1200
1400
Time (s)
Figure 18: The same setup in Section 4.2 but training starts uncoded and switches to coded mode after T prote 40 rounds. The delay profile measured from the initial 40 rounds is used to select the coding parameters. Plot shows average + std. over 10 independent trials. Transition to SR-SGC is zoomed in.
28

---

Published as a conference paper at ICLR 2023
L TRAINING RESNET-18 ON CIFAR-100
Here, we present the results of concurrently training M = 4 ResNet-18 models on CIFAR-100 over AWS Lambda, using the different coding schemes. ResNet- 18 has 11,227,812 parameters and hence, the size of model weights and gradient updates are roughly 22.5 MB in 16-bit floating point format. This is much larger than the 6MB payload size limit AWS Lambda (see Section HD. This means the master node and workers have essentially use shared storage (Amazon EFS) to communicate the model weights and coded gradients at each round, as depicted in Fig. 19 (a). At each round, the master node first uploads updated model weights to the dedicated shared storage and invokes Lambda workers via an HTTP request. Lambda workers then read the model weights from the storage and
proceed calculate the task results. Finally, each worker uploads the coded gradients to the shared storage and signals the master node via the HTTP response.
(a)
(b)
1.0
0.3
litoe Heihht
AMC
0.5
Signall Sis
0.4
HR Unvoai
0.2
Meights
8.0
Tim
Figure 19: (a) Communication between master and Lambda workers each round. (b) Empirical CDF of workers' completion time, averaged over 100 rounds and 256 workers (shades represent standard deviation. Each worker calculates gradients for batch of 2 CIFAR- 100 images on ResNet- 18, and uploads the gradients to EFS.
The process of uploading the task results the shared storage will significantly increase the commu- nication delay, given the write throughput limits of EFS. This is clearly observed in the empirical CDF of workers' completion time in Fig. (b). Note that for the CNN model used in Section 4 the task results were directly sent to the master node in the payload of the HTTP response. Therefore, given the increased variance of workers' completion time, we opt choose a higher value of μ for this case to let more workers finish at each round.
We used n 256 Lambda workers to train M 4 models concurrently for 1000 rounds (250 rounds for each classifier). A batch size of 512 samples and ADAM optimizer is used. Fig. 2ig.20pplo plots the the number of completed jobs (for M models) over time for the three coding schemes, as well as uncoded training. Coding parameters are selected based on the method discussed in Section using Probe = 20 rounds. The results showed that M-SGC finishes training 11.6% faster than GC (while maintaining significantly smaller normalized load), and 21.5% faster than uncoded training.
1000
MSGC (B=1, W=2, A= 230)
SRSCC (B11, W-2, A- 205) CC (4= (aw114 114)
Codlng
Number of jobs doce
400
200
5000
10000
15000
20000
25000
Figure 20: Training 4 ResNet-18 models on CIFAR-100. Number of completed rounds (for all M models) vs. time.
29


Reviews:
[{"review_id": "nvX8_E3oWd", "reviewer": "Reviewer_82EB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new coded distributed gradient descent approach to mitigate the effect of stragglers in the distributed computation of gradients. The authors combine prior schemes on coded distributed gradient computation with repetition of unfinished tasks from straggling nodes across computation rounds with the assumption being that the overall computation can tolerate a finite amount of delay. Experiments on a distributed gradient descent task on AWS Lambda shows improvements over prior uncoded and coded approaches.", "summary_of_the_review": "The paper introduces a new coded distributed gradient computation approach for mitigating stragglers in distributed gradient descent. While the approach improves over baselines if a finite delay in the computation can be tolerated, it is unclear where such delays would be acceptable in practice. Moreover, given the added cost/latency associated with choosing the hyperparameters for this approach the net gain over the uncoded approach is not yet clear.", "strength_and_weaknesses": "Strengths:\n\n1. The approach considers sequential computations and is designed based on the trends in straggling over time. The temporal aspect of straggling has not been considered by most prior coded distributed computing works and is arguably more practical in real scenarios (as also demonstrated by the experiments in this work).\n\n2. The proposed approach is faster than baselines in real serverless computing settings (AWS Lambda) and reduces the computation load at workers which may be especially relevant for emerging frameworks like serverless computing where the individual instances do not have a lot of computing capacity.\n\nWeakness:\n\n1. The approach will improve over prior gradient coding works only when a finite amount of delay ($T>0$) can be tolerated. The authors consider a scenario where multiple neural networks are trained on the same dataset in their experiments where such a delay can be tolerated. However, it is unclear when this would happen in practice because typically gradient descent is a sequential operation with successive iterations of a single model being performed where such a delay would not be acceptable because the gradient from each round is needed for the next round. Please provide some examples/references to back this claim.\n\n2. The proposed approach seems to strongly depend on the choice of hyperparameters ($B$, $W$, etc.). Indeed, the authors perform additional experiments to select the right hyperparameters. Given, the extra cost/latency of performing these added experiments, and the extra cost/latency of decoding the coded gradients, neither of which is included in the time measurements, it is unclear if the proposed schemes will give any net improvements over the uncoded scheme, especially since model training is a one-time operation where a small amount of straggling may actually not be a very significant issue. Therefore I would like to see either that the gain is significant after taking these factors into consideration or that incorrect/different choices of hyperparameters for the same setting do not lead to much differences in performance since that would imply that the extra experiments to choose the hyperparameters will not be needed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "jPVVKY6fA1", "reviewer": "Reviewer_dEGh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper propose 2 extensions of gradient coding, by adding extra tolerance of stragglers and introducing asynchrony (staleness) to the updates. The theoretical analysis is provided for the computational load. The empirical results show that the proposed schemes are more efficient than the previous works. ", "summary_of_the_review": "This paper propose 2 extensions of gradient coding, by adding extra tolerance of stragglers and introducing asynchrony (staleness) to the updates. The theoretical analysis is provided for the computational load. The empirical results show that the proposed schemes are more efficient than the previous works. I recommend to add experiments for the algorithms' sensitivity to the hyperparameters, and theoretical analysis for the convergence. ", "strength_and_weaknesses": "Strength:\n1. This paper propose 2 extensions of gradient coding, by adding extra tolerance of stragglers and introducing asynchrony (staleness) to the updates. The idea is natural and makes sense.\n2. The theoretical analysis is provided for the computational load. \n3. The empirical results show that the proposed schemes are more efficient than the previous works. \n\nWeakness:\n1. The experiment setup (CNN + MNIST) is too simple and small for distributed training. Such a simple task can be finished quickly on a single computer. To justify the efficiency of the proposed methods in practice, larger tasks such as resnet on cifar-100 or imagenet is highly recommended.\n2. I recommend to show the sensitivity to the hyperparameters, i.e., how the curve of convergence (training loss) vs. time changes when using different B and W. It is important to show the readers how robust the proposed algorithms are, which will also be helpful for the new users when tuning these hyperparameters.\n3. It seems that no convergence proof is provided. Although I think the convergence proof will be trivial since the proof can be reduced to the one for a simple asynchronous SGD algorithm, a convergence proof will make this work more thorough.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jMKt09EI5mM", "reviewer": "Reviewer_euSx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Gradient Coding is a general approach distributed computation (of gradients) in the presence of straggling nodes. The paper introduces two new schemes for GC, where coding is not only done across compute nodes, but also across the time dimension, measured by compute rounds. The first scheme uses the original GC but with selective repetition of unfinished tasks. The second scheme, and main contribution, combines two classes of tasks, one that uses GC and the other that uses repetition. The two classes are multiplexed over workers and rounds in an adaptive manner.  An experimental evaluation is performed on AWS with 256 worker nodes, showing the performance of the new scheme. ", "summary_of_the_review": "The paper proposes new CG schemes where that use the temporal dimension, and coding is done both across worker nodes and across compute rounds. As a result the normalized load per worker is reduced. Various design parameters are used to accommodate for different straggler models. The experimental evaluation is very good, and shows the performance of the new scheme.", "strength_and_weaknesses": "Strength:\nUsing the temporal dimension in GC improves the normalized load per worker. The schemes cover various straggler models (e.g., bursty, arbitrary, fixed number per round). The experimental evaluation is performed in a real AWS environment, with a sizable number of nodes. \n\nWeaknesses:\nThe presentation is often hard to follow, due to the heavy and involved notation, although the high level ideas are relatively clear.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9edZtStq5s", "reviewer": "Reviewer_9BzY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper develops schemes to protect distributed gradient descent from stragglers building on previous work that induces redundancy in computation via error correcting codes. The authors specifically build on a technique called gradient coding that enables a master node to recover the sum of the gradients from $n$ distributed works, even if a certain prescribed number ($s$) nodes straggle (i.e., fail to provide their computation within a time-out). \n\nWhile gradient coding can protect each of the $\\binom{n}{s}$ straggling patterns in every iteration, the authors here aim to be less conservative and aim to protect a subset of the straggling patterns that seem to occur more commonly in practice. They make two assumptions (1) there is some negative correlation in the straggling patterns - a node that  straggles in a given iteration is assumed to not straggle in $B$ iterations later, and (2) that the number of distinct stragglers in any given time-window is limited. For these assumptions, the authors develop new coding schemes that improve upon gradient coding in terms of the amount of redundancy required.", "summary_of_the_review": "The paper advances the development of introducing coding based redundancy in training towards mitigating stragglers, and builds on a recent line of work that is of interest to the machine learning community. The recognition of spatial and temporal dependencies in stragglers, and the corresponding coding techniques are novel. However, the application of the techniques is limited to a relatively narrow use case of concurrent training of multiple models on the same data set. \n", "strength_and_weaknesses": "Strengths:\n+The redundancy of gradient coding can be quite a lot, and the recognition of structure among the set of stragglers in AWS lambda and reducing the overall redundancy is a positive contribution.   \n+The developed coding schemes are novel and clever - even though they do build upon the idea of gradient coding.\n+ The results are experimentally validated, and the experimental results are quite promising, and indicate the usefulness of carefully designed redundancy in AWS Lambda.\n\nWeaknesses:\n- The main use case for the developed technique is the application of training $M$ distinct models on the same data set. This seems to be a narrow - perhaps even contrived - use case as I see it. It is also inevitable that the developed technique cannot be applied to the most common use case of training a data set, due to the coding scheme incurring a delay in decoding (the sum of partial gradients at iteration $t$ is decoded at iteration $t+B$).\n\n- In gradient coding, the load is $s+1$ times the load of the common case. Note that this is the same overhead as if the data sets were repeated $s$ times (which is much simpler!). The main benefit of gradient coding, as I understand it, is that it does not necessarily require $s+1$ to divide $n$, whereas replication would require this. In fact, notice that this replication scheme is also a candidate for the experimental results in Fig. 4, as $s=15,n=256$.\n\nI would like the authors to clarify if the above property is also true for the developed coding schemes. If we allowed some additional divisibility criteria to be satisfied among the parameters, then do simpler schemes such as replication match the performance of the developed schemes?\n\n- There is no statement/result on whether the developed schemes can be improved, or gap to optimality.\n\n\n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster