Group-wise Verifiable Distributed Computing for Machine Learning under Adversarial Attacks
Authors: Sangwoo Hong
Heecheol Yang
Youngseok Yoon
Jungwoo Lee
Venue: Submitted to ICLR 2023 (2023)
Keywords: Adversarial attack
Verifiable computing
Distributed Computing
Coded computing

Abstract: Distributed computing has been a promising solution in machine learning to accelerate the training procedure on large-scale dataset by utilizing multiple workers in parallel. However, there remain two major issues that still need to be addressed: i) adversarial attacks from malicious workers, and ii) the effect of slow workers known as stragglers. In this paper, we tackle both problems simultaneously by proposing Group-wise Verifiable Coded Computing (GVCC), which leverages coding techniques and group-wise verification to provide robustness to adversarial attacks and resiliency to straggler effects in distributed computing. The key idea of GVCC is to verify a group of computation results from workers at a time, while providing resilience to stragglers through encoding tasks assigned to workers with Group-wise Verifiable Codes. Experimental results show that GVCC outperforms the existing methods in terms of overall processing time and verification time for executing matrix multiplication, which is a key computational component in machine learning and deep learning. 

Under review as a conference paper at ICLR 2023
GROUP-WISE VERIFIABLE DISTRIBUTED COMPUTING FOR MACHINE LEARNING UNDER ADVERSARIAL ATTACKS
Anonymous authors Paper under double-blind review
ABSTRACT
Distributed computing has been promising solution in machine learning accelerate the training procedure on large-scale dataset by utilizing multiple workers in parallel. However, there remain two major issues that still need be addressed: i) adversarial attacks from malicious workers, and ii) the effect slow workers known as stragglers. In this paper, we tackle both problems simultaneously by proposing Group-wise Verifiable Coded Computing (GVCC), which leverages coding techniques and group-wise verification to provide robustness to adversarial attacks and resiliency straggler effects in distributed computing. The key idea of GVCC is to verify a group of computation results from workers time, while providing resilience to stragglers through encoding tasks assigned to workers with Group-wise Verifiable Codes. Experimental results show that GVCC outperforms the existing methods in terms of overall processing time and verification time for executing matrix multiplication, which is key computational component machine learning and deep learning.
INTRODUCTION
Recently, machine learning and big data analysis have achieved huge success in various areas such as computer vision, natural language processing, and reinforcement learning, etc. Since they usually demand massive amount of computation on large dataset, there has been increasing interest in distributed systems, where one node is used as master and the others are used as workers.
One possible option distributed computing DDacíín al. 2005 2011), where the workers compute partial computation task received from the master. distributed computing. the master divides and distributes tasks (which require far small memory than the original task) to workers, and they compute the assigned tasks and send results back master. Distributed computing can be utilized to compute matrix multiplication in machine learning, the most important and frequent computation block. In distributed setting, however, there exist two foremost considerations embed distributed computing in machine learning applications. i) stragglers and ii) adversarial workers.
Stragglers are workers that return their computation results much slower than others. It has been reported that stragglers can be a serious bottleneck to performing large-scale computation tasks (Dean & Barroso 2013; Huang et al. 2017 Tandon et al. 2017). To handle straggler effects, coded computing was first suggested in Lee et al. (2018). In coded computing, a master encodes a computation task with a coding technique while retaining redundancy in task allocation. Due to the redundancy arisen from the coding technique, a master does not need all results of tasks to achieve the final output and can ignore stragglers. This approach has been applicd to various computation tasks, especially on matrix multiplication (Dutta et al. 2016 Yu et al. 2017 Park et al. 2018 Reisizadeh al. 2019 Dutta al. 2019: Yu et al. 2020).
Moreover, some of the workers could be adversarial workers, which send perturbed results to the master to contaminate degrade the performance of neural networks. Many studies (Biggio al. 2012 Blanchard et al.) 2017] ET Mhamdi et al.] 2018), (Sohn et al., 2020) [Badasaryan et al.) 2020) Wang et al. 2020) demonstrate that adversarial workers slow down the overall training process and

---

Under review as a conference paper at ICLR 2023
train acc
Worker
A
Encoding
B
Master
Adversurial worker
The set of Adversucial Workers
75%
55%
Results from non-
Verification
R
Struggler
1.76
workers
P4
11.25
C AB
Decoding
0.0
202
Worker E
(a) Training curve neural (b) Distributed computing for matrix multiplication C AB
networks under adversarial under adversarial workers and stragglers. attacks.
Figure 1: Training curve of neural networks under adversarial workers and system model for distributed computing
severely degrade the performance of neural network. this paper, we mainly consider attacks from adversarial workers (i.e. Byzantine workers) in distributed computing, where they try to contaminate the final computation product by returning wrong computation results for the assigned task.
To demonstrate the effect of adversarial workers in distributed computing, we trained neural network under adversarial attack. Fig (a) shows the training curve of neural networks CIFAR-
100. 32 workers were used for training and adversarial workers send random values with the same magnitude as the original results during training. As we can see in the figure. the training accuracy of a neural network degraded severely when there exist adversarial workers. The training accuracy of a neural network converged to 0.99 after 560 epochs when there is no adversarial worker. However, with only 3.125% adversarial workers, the training accuracy the neural network was only 0.89
after 1000 epochs
To be robust against adversarial attacks, master check whether the computation results from workers are correct or not to figure out adversarial workers. Based on this idea, there have been some recent studies that suggest an encoding scheme for assigning computation tasks workers tolerate wrong computation results when obtaining the final computation product, and to identify adversarial workers from the returned computation results (Yu et al. 2019 Soleymani et al. 2021 Hong et al., (022). Another line of research, which we call verifialee computing, has focused on identifying adversarial workers with fast verification procedure. In verifiable computing, a master verifies the correctness of computation results by using verification key (Freivalds) 1977 Tang jet al. 2022).
In this paper, we focus designing fast and robust distributed computing system for matrix multiplication. We use both coding approach and verifiable computing to combat adversarial attacks from malicious workers and straggler effects. Our system model is depicted in Fig [[b)] where a master encodes the computation tasks, distributes them to the workers, and decodes the final product after receiving and verifying the computation results from the workers.
To be specific, we suggest a novel encoding scheme that enables verifying a large number of computation results time, and decoding the final computation product from a part of computation results from the workers to mitigate straggler effects as well. We experiment with various settings and demonstrate that proposed scheme can identify adversarial workers and obtain the final computation product much faster than existing methods. The main contributions of this paper are as follows.
We propose Group-wise Verifiable Coded Computing (GVCC), handling both straggler effects and adversarial attacks in distributed computing for matrix multiplication tasks. To be more specific, we suggest group-wise verifiable codes (GVC) for encoding the computation tasks of workers and provide suitable group-wise verification algorithm.
We provide more explanation and detailed experiment settings in Appendix A.
2

---

Under review as a conference paper at ICLR 2023
We first provide process of group- wise verification trial (GVT), then propose two-stage verification algorithm based on GVT. We also provide modified verification algorithm that can be utilized under straggler effects.
We demonstrate the performance of GVCC via experiments in terms of overall processing time and verification time for executing matrix multiplication tasks in distributed computing under ad adversarial attacks and straggler effects. According to experimental results, GVCC speeds up overall processing time and verification time up to x..11 and x3.34 compare to that of the existing verifiable coded computing scheme in [Tang et al. (2022), and speeds up up to x2.46 and 174 than group testing based adversarial attack identification scheme for coded matrix multiplication in Hong et al. (2022). respectively.
Notations. For a, b Z. la denotes {a, a.aa+l..... I.....b..
2 PROBLEM SETTING
We consider a distributed computing scenario for matrix multiplication task with one master and E workers {Wi) i= i= A master wants to perform a matrix multiplication
AB on input matrices A E Faxb and B pobe for a sufficiently large finite field Fg. The master generates encoded matrices using A and B, then distributes them to workers to allocate tasks. To be specific, the master encodes A, B, and sends them to W, for i E [1 : E}. After receiving A, and B,, each worker Wi computes the allocated task
We assume that some of the workers could be adversarial workers or stragglers. We list our assumptions on adversarial workers and stragglers as follows:
There exist adversarial workers We, where L denotes a set of adversarial workers for L [1 E] and [C] 1.
Stragglers occur randomly depending on the network condition and currently available computing resource each worker.
Adversarial workers have knowledge about input matrices A and B, and all the protocol of distributed computing including encoding, task allocation, and decoding, only except the random key that is used for verification
A master cannot aware the number adversarial workers in advance.
Adversarial workers cannot collude with each other, which implies that they cannot access the information about assigned tasks of other workers.
To improve the performance of distributed computing systems under adversarial attacks and stragglers, we aim to reduce verification time and overall processing time distributed matrix multiplication.
3 BACKGROUND: VERIFIABLE COMPUTING AND CODED COMPUTING
In this section, we first introduce two methods that are leveraged in GVCC: i) verifiable computing that enables identifying adversarial workers and ii) coded computing that mitigates the effects of stragglers.
VERIFIABLE COMPUTING FOR ADVERSARIAL ATTACK
The authors of Freivalds (1977) proposed verification method (Freivalds' method) that uses random key to verify the computation results. Freivalds' method for matrix multiplication can be summarized in three steps as follows.
Computation assignment: A master assigns a matrix multiplication task C AB for A E Raxb and B E Faxe to an available worker. The worker executes the assigned task, and returns its result C' to the master.
Proteettng the random key from the adversarial workers can be realized by randomly generating at the master, after receiving results from the workers.
3

---

Under review as a conference paper at ICLR 2023
Verification key generation: The master generates random key E Fx and computes verification key $1 rA.
Correctness check:
The master computes 52 B rAB rC and sy' rC' from the received result. By comparing $2 and 2/2 the master can verify whether is correct or not.
It has been known that the master identify adversarial workers using this verification process with probability procedure, the master computes ab + be + ca scalar products while the original task C = AB requires abe scalar products.
in the finite field Fg (Sahraei & Avestimehr 2019). In this verification
3.2 CODED COMPUTING FOR STRAGGLERS
In distributed computing, several methods have been proposed mitigate straggler effects. One traditional method is to replicate computational task and allocate it to multiple workers (Wang al.] 2014). However, this replication-bast -based method inefficient as it requires K additional workers to tolerate single straggler, when the computational task is divided into K smaller tasks. To handle straggler effects more efficiently, coded computing was suggested in Lee al.] (2018). By using coding theoretic approach for allocation of tasks to workers, the master retrieve the final product after receiving enough number of workers. We now define an important metric that has been used in many coded computing researches.
Recovery threshold R: The minimum number of computation results of tasks from non-adversarial workers that the master requires to obtain the final product for the worst-case scenario
In coded computing, the master can decode the final output from R out of E results and it is able to tolerate up to E R stragglers. Therefore, coded computing requires S additional workers for handling S stragglers, while the replication-basel method requires KS additional workers for S stragglers.
GROUP-WISE VERIFIABLE CODED COMPUTING
In this section, we provide GVC and propose an algorithm for group-wise verification. We also suggest modified algorithm for GVCC under straggler effects.
4.1 ENCODING OF GROUP-WISE VERIFIABLE CODES (GVC)
We now explain the encoding procedure of GVC that facilitates group-wise verification at the master. In GVC, the master divides input matrices A and into sub-matrices of equal size A, E F xb
for [1 m). and Bg are given by
hx A for [1 n]. Then input matrices and their product C AB
A1
A
A
A
B = B
B ]. C
(1)
Am
A
Am
B
To generate the encoded matrices, the master uses encoding functions PA and pB constructed by using sub-blocks of A and B as coefficients, which are given by
PA (x)) = =m
(B E
where represents the variable of encoding functions and PB. f(x) is the basic building component for constructing Pв and we now introduce the conditions on f(x) that enable group- wise verification of G
'It should be noted that previous works have included stragglers or adversarial workers in the recovery threshold and in this case, the recovery threshold of GVC can he expressed as R' + S +
'The condition for f(z) was also used in squeezed polynomial codes (Hong et al. 2020 in order to reduce communication load in distributed computing.
4

---

Under review as a conference paper at ICLR 2023
Condition I: The polynomial function f()) used in the encoding function pa (z) should satisfy the following conditions.
i) f(z) is mth order polynomial function.
ii) f(x) has at least E sets of m evaluation points 1111, 1,12. ag a.m that satisfy f(a,1)
f(ar2) ..... f() = wt for t E [1 _
cUsing the encoding functions and evaluation points satisfying Condition I, the master generates the encoded matrices Ar, and Br for 1 E [1: El and E [1 m]
A (a -i= A,a
(3)
B Br, = (B(a)
Eル Byw
=B,,.
where w, = ()) for E [1 m]. which are the values of encoding functions PA and PB at the evaluation points x Ctt.u
Remark 1. (Quantization and embedding into the finite field) In this paper, assume that input matrices are defined on finite field Fg while the dataset for machine learning and polynomial function f(z) used for encoding based on the real field IR. To express real field data and function in the finite field, we quantize matrices A, B. and f(x) using v bits, and embed them into a finite field F, of integers modulo prime q. Quantization of real numbers and embedding into the finite field have been used several previous works (Yu et al.) 2017: Di et al.) [202]] Tang et al.) [2022). To analyze the effect of quantization training of the deep neural network, we provide experiment in Appendix B.
Remark 2. (Polynomials for GVC) GVC be constructed using any polynomial satisfying Condition I. For instance, Chebyshev polynomial, which has been used in several coded computing studies (Fahim& Cadambe 2021 Hong et al. 2021). can be used as f(x) by using quantization as stated in Remark 1. We also provide the proof Appendix C.
Remark 3. (Reduced Computational overhead for encoding) In GVC, since is guaranteed B = Br,., Vu E [1 m] for E [1 E instead of encoding 2E matrices in the conventional methods. Thus, the computational overhead for encoding can be lowered by GVC.
my the master encodes (1 + J E matrices to assign E tasks,
4.2 TASK ASSIGNMENT AND COMPUTING AT WORKERS
To assign the tasks to workers, the master randomly rearranges workers into E groups of same size, which can be denoted Wr,
t. for i [1: E and u [1 m], and distributes A B a W....
Each worker W., computes the assigned task Čr, = Á... Br,. which corresponds to the value of the evaluation function (c the evaluation point an,u. where Pc(x) is given by
pc(x)= = PA(x) x (B(#) m E A.B A(B
(4)
After each worker finishes the assigned task, returns its computation result to the master.
4.3
GROUP-WISE WISE VERIFICATION FOR GVC
After receiving the results from workers, the master begins a verification process. We first explain a group-wis wise verification process and suggest two-stage verification algorithm based on this process.
4.3.1 A GROUP-WISE VERIFICATION TRIAL (GVT)
Let us denote workers with finished computation among (W..) 1s by Te for E [ E. By GVC, a master can verify results from group T, in a single trial. In conventional verifiable computing approach, a master verifies the computation result Č for i E [1 E] individually. However, if the tasks are encoded by GVC, it is ensured that Σ,, Cr. ΣT, A., Σ,, Ar, E,y, At, a Br for group of workers T₁ among (W, (W. where [Tel k (k & m). Therefore,
pm
5

---

Under review as a conference paper at ICLR 2023
the master verify computation results Ar, Br.u in group by verifying Σy, A.,. u, B,, instead. On the basis this fact, we suggest a process for group-wise verification trial (GVT).
Verification key generation: For each trial of group-wist verification, master generates random key F2 F1x E and computes verification key $1,t F, Ar,
Group-wise Correctness check: The master computes $2, R. ST, A,, x Bi,, = T,ET, (Ar,BBBl = ryΣy, Ct, and 22 = rrEr,C,, from the received computation results. If 82, # 22 then the master marks the output of verification trial as Positive, which implies there exist more than adversarial worker in the tested group Te, and marks as Negative otherwise
Br,. S1, B
4.3.2 TWO-STAGE VERIFICATION ALGORITHM
We now provide a two-stage verification algorithm of GVC, given by Algorithm 1
Algorithm 1: Group-wise Verifiable Coded Computing
Two-stage group-wise verification: After receiving all computation results from workers, the master begins group-wise verification. for t E [1 _ do
The master verifies m workers using GVT in Section 4.3.1 where Tr (Wt,) ym if Group-wise verification result for Ti is negative then
L Put all workers in T; to a set of aov-addersarial workers T
// Stage
else
L Put all workers in Tr to set of possible adversarial workers TP.
[T" 2 R then
break;
if |T"| R then
11
The master verifies each worker in T using GVT for k = 1, and put non-adversarial
workers whose verification result negative 7 until [T R. // Stage
Two-stage gisep-wise verification: After receiving all computation results of tasks from workers, the master starts group-wise verification based on GVT. However, one thing we should take into account that GVC can verify up m results at once. Thus, we propose a two-stage group-wise verification algorithm adjusted to the parameter m.
Stage 1: The master groups (We, W.ahh ) as Ti for t E [1 E]. The master performs group-wise verification T, using GVT.
Stage The master verifies each computation result in if group-wiss wise verification result for T, is positive, until it achieves R non-adversarial workers to obtain C.
4.4 DECODING THE MASTER
After verifying R non adversarall computation results, the master starts decoding. As we can see in equation] I and equation 4 A, B, for E m], j E [1 n2] can be retrieved from Pc(z) to achieve C. Since C,,, = (a and pc(x) is polynomial of degree mn 1, can be interpolated from mn distinct value of C,, Hence, the master needs any fastest mn aoversaaall computation results to decode the final output C. Thus, the recovery threshold of GVC is R = mn.
It should be noted that group-wise verification trial has the same accuracy with the individual verification Freivalds (1977). We demonstrate this by experiment under various adversarial attacks Appendix D. We do not consider straggler effects here for simplicity, but provide modified verification algorithm of
GVC that considers straggler effects in Section 4.5

---

Under review as a conference paper at ICLR 2023
Decoding can be done by the inversion of the coefficient matrix in
31 0
$1 m-1
f(31)
B1 81m-11 ((3,)
A B
2
l x
x
Cmn
8mn
0
Bmn m
f f(8mn)
8mn m f(8mm))
Am B
(5)
where C2 and 3x for l [] mn] denote the fastest computation results and the evaluation points of them, respectively and @ denotes Kronecker product. It can be also achieved by interpolation (Kedlaya & Umans 2011) of pc(x) and extracting A, A, from Pc(x) by repeated division of f (Ir). We provide more detailed decoding process in Appendix E.
Remark 4. (Optimal Recovery threshold) It has been known in Yu et al. (2017) that the optimal recovery threshold for coded matrix multiplication is mn when A and B are divided into m and partitions in a row-wise and column-wise manner, respectively. Thus GVC also achieves the optimal recovery threshold.
Remark 5. (Upper bound of tolerating adversarial attacks) Since GVCC requires mn computation results to obtain the final product, GVCC can tolerate up to lupper workers, where S denotes the number of stragglers.
E - S mn adversarial
4.5 MODIFIED VERIFICATION ALGORITHM OF GVCC UNDER STRAGGLER EFFECTS
We now provide modified algorithm that can be used under straggler effeets...
Two-stage group-wise verification in modified GVCC:
Stage 1: The master groups V.taaJc 1m as Te for t E [1 E as in GVCC. The master establishes a certain threshold 2. The master starts a group-wiss wise verification for the computation results of all groups received up to that time when the master receives computation results from workers.
m
Stage 2:
The master first individually verifies the computation results that arrived late, and verifies each computation result in T, if group-wise verification result for Te is positive, until it finds R non-adversarial workers to obtain C.
By setting a proper threshold z, the modified verification algorithm can efficiently deal with straggler effects. However, it may lose some of the benefits of group-wise verification trade-off because the master verifies a smaller group of workers in single trial. The impact on overall processing time will be analyzed in Section 6 via experiment.
RELATED WORKS
In distributed computing, there have been several studies on handling adversarial attacks and straggler effects simultaneously. First, to have tolerance over adversarial attacks and provide resiliency to straggler effects, Lagrange coded computing (LCC) has been suggested in YY et al. (2019). In LCC, a master requires 2K additional non-adversarial workers to be robust against K adversarial workers. In addition, list-decoding approach has been applied to distributed matrix multiplication in (Subramaniam et al.] (2019), and it reduces the additional cost of tolerating adversarial attacks by a factor two asymptotically compared to LCC. However, the computational complexity to perform list-decoding increases quadratically with the number of workers.
Recently, verifiable computing has been introduced to coded computing schemes. The authors of Tang et al. (2022) have suggested AVCC to counter straggler and adversarial workers. In AVCC, a master only requires K additional computation results from workers if there exist K adversarial workers, because it can verify each computation result using verification key. However, since the master can verify only a single computation result at a time, the verification process can be a bottleneck for overall processing if the master utilizes numerous workers in the system.
In addition, there have been several studies that are based on a group-wise identification to find adversarial workers, while mitigating straggler effects using coded matrix multiplication. First,
7

---

Under review as a conference paper at ICLR 2023
group testing algorithm has been applied to coded computing in Solanki al. (2019). However, since it has a constraint on the minimum testable size for group testing, the number of test trials can be significantly large. To mitigate this limitation, hierarchical group testing (HGT) has been proposed in Hong et al. (2022). However, HGT imposes high computational complexity on a decoding identify adversarial workers, whereas verifiable computing requires matrix-vector multiplications to verify them.
master since it requires matrix inversion
6
EXPERIMENTAL RESULTS
overall processing
overall processing time
120
HGT
AVCC
66
HGT
AVCC
100
GVCC (proposed)
64
(proposed)
time (S)
62
80
60
58
56
0.0
0.02
0.05
0.1
0.2
byzantine workers
Straggler probability
(a) Number of adversarial workers /
(b) Straggler probability
overall processing time
overall processing time
AVCC
45
AVCC
HGT
GVCC (oroposed)
40
GVCC (proposed)
30
25
Square
20 60
112
Matrix shape
workers
(c) Matrix shape
(d) Number of workers
Figure 2: Overall processing time of AVCC, HGT, and GVCC (proposed).
In this section, we provide the performance of GVCC and modified GVCC terms of overall processing time, and compare with the two existing schemes, AVCC (Tang al. 2022) and HGT (Hong et al. 2022). We proceed distributed matrix multiplication cloud, and use 12.2xlarge node done by MPI4py (Dalcín et al., 2005) and matrices are randomly generated by NumPy. We set the verification time limit as 100 seconds and if the verification process takes than 100 seconds, terminate the experiment and mark it as failure. We run four experiments and evaluate the overall processing time. Each experiment is repeated 20 times and the result depicted in Fig. We also list stage-wise processing time (encoding (Enc), task assignment (SA), computation & return (CR), verification (Ver), decoding (Dec), and overall processing times) experiments Appendix F.I.
a cluster of Amazon EC2 master and use 12. 12.micro nodes workers. Implementation
In Fig. ((a) we compare overall processing time with different number of adversarial workers 1, when A 63000 B E 1=300x 3600, m 5, n 9, and E 60. GVCC speeds up overall processing time compared to AVCC for all cases, and also shows faster overall processing than HGT when / 2 As we have claimed Remark 3, the computational overhead for encoding the tasks can lowered by GVC, which results in reduced encoding and overall processing time compared to AVCC. Furthermore, for the verification time HGT increases significantly with the number of workers, the verification and overall processing time of GVCC is much lower than HGT when / > 3. To be specific, GVCC speeds up verification time up to x3.34 than AVCC, and k174 than HGT, and HGT even fails to proceed verification process in the given time limit (100s) when / = 5.
In Fig. 2(b) we show the overall processing time with stragglers distributed computing systems, where A x3500x6300 B |6600036000 m 5. E 60, and
3. To
8

---

Under review as a conference paper at ICLR 2023
simulate straggler effects in distributed computing, randomly pick stragglers with probabilities p = O, 0.02, 0.05, 0.1, and 0.2. Stragglers are forced to run background thread which slows down the execution of assigned tasks. In this experiment,
use the modified algorithm in Section 4.3 for GVCC (= = R = 63) and compare with AVCC and HGT. Since verification is done asynchronously for the received computation results in GVCC, verification time is added to computation & return time. As we can see in the Fig 2 GVCC outperforms AVCC and HGT for all cases. Thus, it is claimed that GVCC can efficiently handle straggler effects while leveraging a group-wise verification approach. We also provide additional experiments with a modified algorithm on another parameter setting in Appendix F.2.
In Fig. [ we compare overall processing time with different shape of input matrices with three parameter settings: i) Square (A E F )1500x4500, iii) Fat (A E q 17270077000 1 13600036000 B E F8000x3600), ii) Tall (A E F4500x1500 B E 17700x27000) where m = 5, = 9, 3, and E = 60. GVC speeds up overall processing time compared to AVCC and HGT, regardless of matrix shapes.
9
The performance of GVCC with the different numbers of workers is depicted in Fig. 2 We run experiments to multiply two input matrices A E F2100x and B E Fg F4000x3561 with three parameter setting (E, m,n), n)): i) (60, 5, 9), ii) (84, 6, 11), iii) (112, 7, 13), where = 3. GVCC achieves the lowest overall processing time in every setting. To be specific, GVCC speeds up verification time up to x3.5 than AVCC and x57.29 than HGT. Furthermore, GVCC speeds up overall processing time up to x 1 1.20 than AVCC and x x.100 than HGT.
Group-wise verifiable size m
Matrix Size N
Verification time (ms)
900
1800
3600
HGT
2750
1920
2440
2348
9554
42163
AVCC
140
170
210
16
45
163
GVC
48
48
46
5.6
17
62
Table 1: Verification time of GVC, AVCC, and HGT with different matrix size and m.
Furthermore, it should be noted that GVC shows more benefit than AVCC as N or m gets bigger.
In specific, methods have verification complexity of O Et 22) while AVCC has O(RN2). To show the performance of GVC with different m and N, we indicate the verification time of GVC
and the other schemes in table We used parameter setting ((E, m, n): i) (60, 5, 9). ii) (84, 6, 11), fiii (112, 7, 13), where 1 = 3 (which are same setting with experiment in Fig 2 We indicate the verification time of HGT, AVCC, and GVC in Table 1 We can see that the verification time of GVC remains the same value, while other methods show an increase in the verification time. This is because other methods require the verification of more results as the recovery threshold increases, but GVC has the same number of groups that needs to be verified. Moreover, to show the benefits of GVC, we conduct additional experiments. We experimented with the same parameter setting in Fig ((a) when I= = 3 and only changed the size of the matrix (m, n = 5,9, E = 60, = 3 and a c N). We have changed the size of input matrix N from 900 to 3600 to show the benefit of GVC as N increases, and indicate the verification time in Table 1 As we can see in the table, verification gap between GVCC and other scheme becomes larger as N increases. In specific, HGT shows far larger verification time than GVC. Moreover, gap between AVCC and GVC increases x2.66 when N becomes x2, and x9.36 when N becomes x4.
7 CONCLUSION
In this paper, we propose GVCC, a robust and fast distributed computing scheme for matrix multiplication that can deal with two important problems: adversarial attacks and straggler effects. By combining the verifiable computing with coded computing, GVCC allows master to verify a group of computation results at a time, reducing verification time to find adversarial workers and provide resiliency to straggler effects simultaneously. Consequently, GVCC is shown to have significant reduction in verification and overall processing time, and experimental results demonstrate the effectiveness of GVCC in distributed computing systems.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 2388-994.. PMLR, 26-28 Aug 2020.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In ICML, 2012.
Peva Blanchard. El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, volume 30, 2017.
Lisandro Dalcín, Rodrigo Paz, and Mario Storti. Mpi for python. Journal of Parallel and Distributed Computing, 65(9): 1110-111111111111 2005.
Lisandro Dalcín, Rodrigo Paz, Pablo Kler, and Alejandro Cosimo. Parallel distributed computing using python. Advances in Water Resources, 34(9):1124-1133) 2011. ISSN 0309-1708.
Jeffrey Dean and Luiz André Barroso. The tail scale. Commun. ACM, 56(2):74-800 2013.
Sanghamitra Dutta, Viveck Cadambe, and Pulkit Grover. transforms distributedly using coded short dot products. In Advances in Neural Information Processing Systems, volume 29, 2016.
Short-dot: Computing large linear
Sanghamitra Dutta, Mohammad Fahim, Farzin Haddadpour, Haewon Jeong, Viveck Cadambe, and Pulkit Grover. the optimal recovery threshold of coded matrix multiplication. IEEE Transactions Information Theory, (6(1))278-301 2019.
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in Byzantium. In Proceedingy of the 35th International Conference Machine Learning, volume 80, pp. 3521-3530. PMLR, 10-15 Jul 2018.
Mohammad Fahim and Viveck R. Cadambe. Numerically stable polynomially coded computing. IEEE Transactions on Information Theory, 67(5):2758-2777 2021.
Rusins Freivalds. 1977.
Probabilistic machines can use less running time. In IFIP congress, volume 839,
Sangwoo Hong, Heecheol Yang, and Jungwoo Lee. Squeezed polynomial codes: Communication- efficient coded computation in straggler-exploiting distributed matrix multiplication. 1EEE Access, 8:190516-190528, 2020.
Sangwoo Hong, Heecheol Yang, Youngseok Yoon, Taehyun Cho, and Jungwoo Lee. Chebyshev polynomial codes: Task entanglement-based coding for distributed matrix multiplication. In Proceedings of the 38th International Conference Machine Learning, volume 139, pp. 4319- 4327. PMLR, 18-24 Jul 2021.
Sangwoo Hong. Heecheol Yang. and Jungwoo Lee. Hierarchical group testing for byzantine attack identification in distributed matrix multiplication. IEEE Journal on Selected Areas in Communications,
2022.
Peng Huang, Chuanxiong Guo, Lidong Zhou, Jacob R. Lorch, Yingnong Dang, Murali Chintalapati. and Randolph Yao. Gray failure: The achilles' heel of cloud-scale systems. In Proceedings of the 16th Workshop on Hot Topics in Operating Systems, HorOS 2017, Whistler, BC, Canada, May 8-10, 2017, pp. 150-155. ACM, 2017.
Ruowan Ji, Asit Kumar Pradhan, Anoosheh Heidarzadeh, and Krishna Narayanan. Squeezed random khatri-rao product codes. In 2021 IEEE Information Theory Workshop (ITW), pp. 1-6, 2021.
Kiran Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. SIAM Journal Computing, 40(6): 2011.
10

---

Under review as a conference paper at ICLR 2023
Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris S. Papailiopoulos, and Kannan Ramchandran. Speeding up distributed machine learning using codes. IEEE Trans. Inf. Theory, 64(3):1514-1529, 2018.
Hyegyeong Park. Kangwook Lee, Jy-Yong Sohn, Changho Suh, and Jackyun Moon. Hierarchical coding for distributed computing- In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 1630-1634, 2018. doi: 10.
Amirhossein Reisizadeh, Saurav Prakash, Ramtin Pedarsani, and Amir Salman Avestimehr. Coded computation over heterogeneous clusters. IEEE Transactions Information Theory, 65(7))4227- 4242, 2019.
Saeid Sahraei and A. Salman Avestimehr. Interpol: Information theoretically verifiable polynomial evaluation. In 2019 IEEE International Symposium on Information Theory (ISIT), pp- 1112-1116, 2019.
Jy-yong Sohn, Dong-Jun Han, Beongjun Choi, and Jackyun Moon. Election coding for distributed learning: Protecting signsgd against byzantine attacks. In Advances in Neural Information Processing Systems, volume 33, pp. 14615-14622 2020.
Atnav Solanki, Martina Cardone, and Soheil Mohajer. Non-colluding attacks identification in distributed computing. In 2019 IEEE Information Theory Workshop (ITW), pp. 1-5, 2019.
Mahdi Soleymani, Ramy E. Ali, Hessam Mahdavifar, and A. Salman Avestimehr. List-decodable coded computing: Breaking the adversarial toleration barrier. IEEE Journal on Selected Areas in Information Theory, 2(3):867-778, 2021.
Adarsh M. Subramaniam, Anoosheh Heidarzadeh, and Krishna R. Narayanan. Collaborative decoding of polynomial codes for distributed computation. 2019 IEEE Information Theory Workshop (ITW), pp. 1-5, 2019.
Rashish Tandon, Qi Lei, Alexandros G. Dimakis, and Nikos Karampatziakis. Gradient coding: Avoiding stragglers in distributed learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 3368-3376. PMLR, 06-11 Aug 2017.
Tingting Tang, Ramy E. Ali, Hanieh Hashemi, Tynan Gangwani, Salman Avestimehr, and Murali Annavaram. Adaptive verifiable coded computing: Towards fast, secure and private distributed machine learning. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 628-638, 2022.
Da Wang, Gauri Joshi, and Gregory Wornell. Efficient task replication for fast response times in parallel computation. In The 2014 ACM International Conference on Measurement and Modeling of Computer Systems, pp. 599 000,-600,20 2014.
Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy- yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos. Attack of the tails: Yes, you really can backdoor federated learning. In Advances in Neural Information Processing Systems, volume 33, pp. 16070-16084, 2020.
Qian Yu, Mohammad Ali Maddah-Ali, and A Salman Avestimehr. Polynomial codes: an optimal design for high-dimensional coded matrix multiplication. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 4406-4416, 2017.
Qian Yu, Songze Li, Netanel Raviv, Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and Salman A. Avestimehr. Lagrange coded computing: Optimal design for resiliency, security, and privacy. In Proceedings of the Twenty-Sccond International Conference on Artificial Intelligence and Statistics, volume 89, pp. 1215-1225. PMLR, 16-18 Apr 2019.
Qian Yu, Mohammad Ali Maddah-All Ali, and A Salman Avestimehr. Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding. IEEE Transactions on Information Theory, 66(3): 1920-19399 2020.
11


Reviews:
[{"review_id": "gyvb2LTW_1e", "reviewer": "Reviewer_Ma5n", "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": "This paper proposed an approach for distributedly multiplying two large matrices while handling active adversaries and stragglers. The design is within the framework of verifiable computing, where the adversaries are detected before recovering the final results. However, by modifying the encoding polynomials (using squeezed polynomial codes particularly), the required number of verifications is reduced. Therefore, the proposed design reduces the overall computation time compared to earlier proposed approaches, although requiring slightly stronger assumptions on the adversaries.", "summary_of_the_review": "The work in this manuscript is well-presented and interesting. The reviewer only observed one minor issue, which is easily fixable. ", "strength_and_weaknesses": "This manuscript was earlier submitted to Neurips 2022, and my main concerns were on the clarity and comparisons of prior works. The authors have revised the paper significantly. As far as the reviewer can see, all major issues on those aspects are resolved. I only have one minor suggestion on the definition of the recovery threshold. In prior works that consider strong adversaries and apply forward error-correcting approaches, the recovery threshold counts the total number of workers that returns the computation result, but here the definition only counts non-adversarial workers. The reviewer understands that in the framework of verifiable computing, the version presented in this work can be expressed in a simpler formula, which could confuse readers who have seen the other version. The reviewer suggests adding a discussion immediately after the definition of recovery threshold to clarify this difference.   ", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "VbCO-ndX5H", "reviewer": "Reviewer_4Emk", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 proposes group-wise verifiable coded computing with coding techniques and group-wise verification to tackle adversarial workers and the effects of stragglers.\nThe authors demonstrate the performance of group-wise verifiable coded computing in term of overall processing time and verification time.", "summary_of_the_review": "In a word, this paper is below the average level of other accepted papers. The proposed method is effective, but the experimental part needs to be improved and more innovations need to be explored.", "strength_and_weaknesses": "(1)According to the experimental results, group-wise verifiable coded computing can indeed improve the efficiency under different settings, however, this paper only describes the experimental settings in general without enough comparative analysis. The perspective to measure the experimental results is single, and the compared objects are not sufficient. It is necessary to add specific experiments for adversarial workers and the effects of stragglers, and try to apply the proposed method on more complex tasks.\n(2)The structure of this paper can be adjusted and some of the statements in the paper could be better. \n(3)The proposed method is effective and the description in this paper is detailed. However, method description should be less and experimental analysis could be added.\n(4)Although the proposed method can alleviate both problems at the same time, the target task is relatively monotonous.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4IQlqZzUPX", "reviewer": "Reviewer_Z7en", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper develops techniques for distributed matrix multiplication with adversarially corrupt nodes and stragglers.  A error correction coding scheme is developed that simultaneously detects corrupt computations via random-key-based verification, and can decode in the presence of stragglers. ", "summary_of_the_review": "The paper has several major weaknesses including (1) a weak model for adversary, (2) lack of precision in writing some parts, and (2) lack of satisfactory experimental evaluation details for the ML applications mentioned. The positive side (lower computation overhead) seems too thin for large matrices to compensate for the above drawbacks.\n", "strength_and_weaknesses": "Strengths:\n+ The simultaneous handling of polynomial-based verification and stragglers in a distributed computing context seems new.  \n\nWeaknesses;\n- A natural scheme is to verify each node separately to check if the result is adversarial. The benefit of the proposed scheme over this approach, as I understand it, is that it is computationally more efficient - but the gain appears to be small for large matrices. Assuming that all matrices are $N \\times N$,  verification is of order $O(N^2)$. The proposed scheme performs one verification for every $m$ nodes, instead of one for every node, but I am not convinced that this is practically very important when $N \\gg m$. Note that gain in computational complexity comes at the cost of a significant assumption - that the adversarial nodes do not collude. This is quite a weak assumption in the context of security literature. \n\n- Although matrix multiplication is important, the paper (main body) does not directly test their results in the context of a machine learning application. The supplemental section does seem to have an application, but it is too sparse in the details for reproduciblity (e.g., how are the codes applied? What is the developed accuracy? What are the wallclock times of various schemes?).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "0l657itiGXl", "reviewer": "Reviewer_d7sM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 submission proposed a distributed computing scheme for matrix multiplication that can handle two problems: adversarial attacks and straggler effects. The experimental results demonstrate the robustness and fastness of the proposed approach by comparing it with two baselines. ", "summary_of_the_review": "I have no recommendation for this paper. However, I will decide my score based on other reviewers' comments after the authors' response time.", "strength_and_weaknesses": "Strength:\n\n1. The motivation is clear.\n\nWeaknesses: \n\nI have no significant comments about this submission since the targeted topic is not relevant to my research area. In fact. I do not know why this paper is assigned to me. Therefore, I provide a score of 6 for this paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": {}}]

Author rebuttal:

Decision: Reject