Sageflow: Robust Federated Learning against Both Stragglers and Adversaries
Authors: Jungwuk Park
Dong-Jun Han
Minseok Choi
Jaekyun Moon
Venue: NeurIPS 2021 Poster (2021)
Keywords: Federated Learning
Stragglers
Adversaries

Abstract: While federated learning (FL) allows efficient model training with local data at edge devices, among major issues still to be resolved are: slow devices known as stragglers and malicious attacks launched by adversaries.   While the presence of both of these issues raises serious concerns in practical FL systems, no known schemes or combinations of schemes effectively address them at the same time. We propose Sageflow, staleness-aware grouping with entropy-based filtering and loss-weighted averaging, to handle both stragglers and adversaries simultaneously. Model grouping and weighting according to staleness (arrival delay) provides robustness against stragglers, while entropy-based filtering and loss-weighted averaging, working in a highly complementary fashion at each grouping stage,  counter a wide range of adversary attacks. A theoretical bound is established to provide key insights into the convergence behavior of Sageflow. Extensive experimental results show that Sageflow outperforms various existing methods aiming to handle stragglers/adversaries.

Sageflow: Robust Federated Learning against
Both Stragglers and Adversaries
Jungwuk Park' KAIST savertmOkaist.aco ac.
Dong-Jun Han" KAIST djhan930kaist.ac.kk
Minseok Choi
Jeju National University e jaqmf @ e junu, ac kr
Jaekyun Moon KAIST
jmoonkkaist. edu
Abstract
While federated learning (FL) allows efficient model training with local data edge devices, among major issues still to be resolved are: slow devices known as stragglers and malicious attacks launched by adversaries. While the presence of both of these issues raises serious concerns practical FL systems, known schemes or combinations of schemes effectively address them at the same time. We propose Sageflow, staleness-awan grouping with entropy- baased filtering and loss-weighted averaging, to handle both stragglers and adversaries simultaneously. Model grouping and weighting according staleness (arrival delay) provides robustness against stragglers, while entropy-based filtering and loss-weighted averaging, working in a highly complementary fashion each grouping stage, counter a wide range of adversary attacks. A theoretical bound is established provide key insights into the convergence behavior of Sageflow. Extensive experimental results show that Sageflow outperforms various existing methods aiming to handle stragglers/adversarie.
Introduction
Large volumes of data collected at various edge devices (i.e., smart phones) are valuable resources in training model with a good performance. Federated learning [T8 12 7 is promising direction for large-scale learning, which enables training of global model with less privacy concerns. However, among major issues that need to be addressed current federated learning (FL) systems are the devices called stragglers that are considerably slower than the average and the adversaries that enforce a various form of attacks.
Regarding the first issue, simply waiting for all the stragglers each global round significantly slow down the overall training process. To handle stragglers, asynchronous FL schemes [13] 22
25 [4] update the global model every time the server receives local model from each device; especially in FedAsyncc [25]. the global model is updated asynchronously according to the device's staleness r, the time difference between the current round & and the past round when the device first received the global model. While the asynchronous schemes are highly effective in handling stragglers, the one-by-one update nature does not lend itself well for integration with established aggregation methods to combat the second issue, the adversaries.
There are different forms of adversarial attacks that significantly degrade current FL systems. In untargeted attacks, attacker can poison the updated model the devices before it is sent to the
Equaa contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

server (model poisoning) 3 9 or can poison the datasets of each device (data poisoning) 16]. In
targeted attacks (or backdoor attacks) 4 20), the adversaries cause the model to misclassify the
targeted subtasks only, while not degrading the overall test accuracy that much. Robust federated averaging (RFA) of [19) a well-known method proposed to handle adversaries in Fl., employs geometric-median-bee baaeeddd-- aggregation to provide fair level of protection. Other various aggregation schemes (e.g., Multi-Krum) also successfully handle adversaries in distributed learning [3] 28 [5) Unfortunately, however, the performance of these methods are substantially degraded when the portion of adversaries is large. The presence of stragglers can drive the attack ratio higher (e.g., by ignoring stragglers), significantly degrading the performance of current aggregation schemes.
While the presence of both stragglers and adversaries raises significant concerns in practical FL, to our knowledge, there are currently no existing methods or known combinations of ideas that can effectively handle these two issues simultaneously.
Main contributions. We propose Sageflow, awwre grouping with entropy-based filtering and loss- weighted averaging, robust FL strategy which can handle both stragglers and adversaries at the same time. Targeting the straggler issue, our strategy is to perform periodic global aggregation while allowing the results sent from stragglers to be aggregated in later rounds. In each global round, we take advantage of the results sent from stragglers by first grouping the models that come from the same initial models (i.e., same staleness), to obtain a group representative model. Then, we aggregate the representative models of all groups based on their staleness, to obtain the global model. Our periodic aggregation strategy is not only effective in neutralizing stragglers but also provides great platform for countering adversaries, as discussed below.
Targeting each grouping stage of our straggler-mitigating idea, we propose an intra-group defense strategy which is based on our entropy- -bsed filtering and loss-weighted averaging. The entropy filtering first filters out the models with high entropies, i.e., outliers, and the loss- bos--weighted averaging of the survived models enables model aggregation according to the measured qualities of the received local models. These two methods work in highly complementary fashion to effectively counter wide range of adversarial attacks each grouping stage. Here, in computing the entropy and loss of each received model, we utilize public data that we assume to be available at the server. In fact, the utilization of public data is not a new idea, as seen in recent FL sctups of [30] 27 [ This is generally reasonable setup since data centers typically have some collected data that can be accessed by public. For example, different types of anonymous medical data are often available for public research in various countries. We show later via experiments that only a very small amount of public data is necessary at the server (1-2% of the entire dataset, which is comparable to the amount of local data at single device) to successfully combat adversaries. Our main contributions are as follows:
We propose Sageflow, handling both stragglers/adveessuries simultaneously in FL, via a novel staleness-awan grouping combined with entropy filtering and loss- weighte averaging.
We derive the theoretical bound for Sageflow based on key parameters and provide insights into the convergence behavior.
Experimental results on different datasets show that Sageflow outperforms various combina- tions of straggler/adversary defense methods using only a small portion of public data.
21 have recently tackled the straggler issue in FL. The basic idea allow the devices and the server to update the models asynchronously; the global model is updated every time the server receives model from a device. However, critical issue is that grouping- (or aggregation-baa bbsed) methods designed to handle adversaries, such as RFA 3 or the presently proposed entropy/loss based idea, are hard to be implemented
Related works. The authors of [1 25
[19]. Multi-Krum in conjunction with these schemes since the model update is performed one-by-one asynchronously. Compared to the asynchronous schemes, our staleness- aware grouping can be combined smoothly with various aggregation rules against adversaries; we can apply RFA, Multi- Krum or our entropy/loss based idea in each grouping stage to obtain the group representative model.
To combat adversaries, various aggregation methods have been proposed in a distributed learning setup with IID (independent, identically distributed) data across nodes [28] 29
5 24] The authors
of [5] suggests geometric-mediee mean approach is proposed which removes fraction of largest and smallest values of each element among the received results. In Multi- Krum []) among N workers in the system, the server tolerates f Byzantine workers, where 2f + < N. Targeting FL. with non-lII data distribution, RFA of [19] utilizes the geometric median of models sent from devices, similar to [5). However, as
based aggregation rule of models or gradients. In 28 a trimmed

---

already implied, these methods are ineffective when combined with straggler-mitigaton scheme (e.g., iggoring stragglers), potentially degrading the performance of learning. Compared Multi- Krum and RFA, our entropy/loss based scheme can tolerate adversaries even with a high attack ratio, showing remarkable advantages, especially when combined with graggler-mitigation schemes. Moreover, our approach enables defense against a wider variety of attacks by considering both entropy and loss, which are shown to play highly complementary roles.
Finally, we note that the authors of [26]. the server to handle adversaries, but distributed learning setup with IID data across the nodes. Compared to Zeno+, our Sageflow targets non-IID -ID data distribution in FL setup. While Zeno+ adopts a fully asynchronous update rule (without considering the staleness) with the loss-based score function, our Sageflow integrates staleness-awee aware grouping, a semi-sy samni--ynchooouus straggler- -anglegg method, with entropy filtering and loss-weighted averaging. harmonized means to provide protection against wider variety of attacks. We show later via experiments that our Sageflow outperforms Zeno+ in practical FL setups having stragglers and various types of adversaries.
proposed Zeno and Zeno+ that also utilize public data
Proposed Sageflow for Federated Learning
We consider the following federated optimization problem:
w
argmin F(w) argminn Σ mk
F& (w),
(1)
m
where N is the number of devices, my is the number of data samples in device k, and = -k=1 my is the total number of data samples of all N devices in the system. By letting Tk.jj be the j- th data sample in device k, the local loss function of device k, Fe(w), is written as Fx(w) me j= (w.j)..)
2.1 Staleness-Aware Grouping against Stragglers
In the t-th global round of a practical FL setting, the server sends the current model w, to K devices in S,, a randomly selected subset of N devices. We let C K/N be the ratio of devices that participate in each global round. Each device in S₁ performs E local updates with its own data and sends the updated model back to the server.
In handling slow devices, our idea assumes periodic global aggregation at the server. At each global round the server transmits the current model and time stamp, (w,, t), to the devices in S, Instead of waiting for all devices in St, the server aggregates the models that arrive by a fixed time deadline Ta to obtain Wi+1, and moves periodically with every Ta. A key feature here is that we do not ignore the results sent from stragglers not arriving by the deadline T... These results are utilized at the next global aggregation step, even later, depending on the delay or staleness. Let (+t)) be the group of devices selected from the server at global round l that successfully sent their results to the server at global round for i 2 L. Then, we can write S, = , where (:(() n nT
the next global round t + 1. Hence, model aggregation is performed
for * j. Here, U.Q can be viewed as the devices that are selected at round f but failed to successfully send their results back to the server. According to these notations, the devices whose training results arrive at the server during global round belong to one of the ++ 1 groups: U, S ..... U.() Note that the result sent from device k E u,(%) is the model after local updates starting from w,, and we denote this model by w, (k:). At each round f, we first perform FedAvg as
(E) '+
Σ kEC:()
my
wr(k)
EvErto my m
for all = 0, O......, aggregated result of locally updated models (starting from w:) received at round with staleness
t. Here, v 1+1 can be viewed as a group representative model, which is the
1-i+1. Then from the representative models of all groups, vi+1 (1)
vii1.... 1if1 we take weighted Exeefo
averaging according to different staleness: Ei aj (0) (1)
(A)V
141 Here, ( x (1-++1)+ is
normalized coefficient that is proportional to the number of data samples in v,(0) and inversely proportional to (t - + 1)², for given staleness exponent À > 0. Hence, we have larger weight
3

---

Q
Su
Recuivad gloual
Loss weighted
by Wows
8/-1
Ratropy hosed Chbrring
Aseroginng
S:
global
Ressived ae
(Wess.
S
glsied round
Figure 1: Overall procedure Sageflow. At global round f, each received model belongs of the
sets: U(") U7 ..... U/9, After entropy-based filtering, the server performs loss-weighted averaging for the results that belong to ( (Ees) to obtain 1+1' Then aggregate (v(1) (1t1/ied M with to obtain We+1, and
(t)
move on to the next round
for V 1+1 with a smaller / + 1 (staleness). This is to give more weights to more recent results having smaller staleness. Based on the weighted sum Eizo at (A)v we finally obtain Wx+1 as
W++1 (1 - 7) W.
1 (A)+
where y is the time-average coefficient. Now move to the next round + 1, where the server selects S1+1 and sends (W1+1, t 1) to these devices. Here, if the server knows the set of active devices (which are still performing computation), S441 can be constructed to be disjoint with the active devices. If not, the server randomly chooses S:41 among all devices in the system and the selected active devices ignore the current request of the server. The left-hand side of Fig. 1 describes our staleness-aware grouping method.
The key characteristies of our approach against stragglers can be summarized as follows. First, by periodic global aggregation at the server, our scheme is not delayed by the effect of stragglers. Secondly, our scheme fully utilizes the results sent from stragglers in the future global rounds.
2.2 Entropy-based Filtering and Loss- Weighted Averaging against Adversaries
In this subsection, we propose a two-stage solution against adversaries which not only shows better performance with attacks but also combines well with our staleness-aware grouping scheme compared to existing aggregation methods to handle adversaries. Our idea to utilize a small amount of public data collected the server. Data centers typically have their own public data samples as utilized in recent FL setups of [30 [I), e.g., various anonymous medical data that are open for public research. We provide the following two solutions which can protect the system complementary fashion against various attacks including model poisoning, data poisoning and scaled backdoor attacks using only a very small amount of public data. It is shown later Section of Supplementary Material that our idea works well even with class- iaas-immallacee public data.
highly
1) Entropy-based filtering. Let ppub be the number of public data samples in the server. We also let Fp be the j-th sample in the server. When the server receives the locally updated models from the devices, it measures the entropy of each device by utilizing the public data as
Byub
E(k)
Emprnt, (k),
(4)
Teprbb
5=1
where Enpurn (k) is the shannon entropy of the model of the k-th device on the sample Tpucy written
as Expun, (1)) Σの p(.) (k) log p!y).. (k)). Here, Q is the number of classes of the dataset and p(1) (k) is the probability of prediction for the q-th class on a sample Zpub, using the model of the k-th device. In supervised learning, the model produces a high-confident prediction for the
ground truth labels of the trained samples and thus has low entropy for the prediction. However, as can be seen from Fig. 2(a) with the FMNIST dataset (23), under specific model poisoning attacks (reverse sign attack with scale 0.1 in this case), the models compromised by adversarics tend to

---

25
25
20-
where Adlussar spnaa
Energy
4.5
15
levign disice
Eneraay
0.3
0.5
ASHenaraidpraa
Dan gn dedic
40
100
Global round
Global round
Global round
Global round
(a) Model poison, entropy (b) Model poison, loss
(c) Data poison, entropy
(d) Data poison, loss
Figure 2: Model poisoning ((a), (b)): We can filter out the models of adversaries via entropy, but not via loss.
Data poisoning ((c), (d)): We can reduce the impact of adversaries via loss, but not via entropy.
predict randomly for all classes and thus have high entropies compared to the models of benign devices. Even when the local dataset of the benign device is biased, has a high-confident prediction (i.e., low entropy) the classes that in their local dataset, making the entropy lower compared to the model of the adversaries (as seen in Fig. 2(a) Based on this observation, we let the server to filter
the models that have entropies greater than some threshold value Ein- We note that the inflicted
models cannot be filtered out based on the loss values in the setting of model poisoning in Fig. (see
Fig. 2(b), which confirms the importance of the role of entropy. It is shown later in Section that Es is a hyperparameter that can be easily tuned since there is huge gap between the entropy values of benign versus adversarial devices. We also note that our entropy- attacks even with a large portion of adversaries, since it just filters out the results whose entropies are greater than Ex.. This is a significant advantage compared to current aggregation methods against adversaries, whose performances are substantially degraded when the attack ratio is high.
filtering robust against
We note that there are the model to be biased toward specific classes. Data poisoning is one example of such attack. In such cases, the models of the adversaries generally produce high loss values and thus loss-weighted averaging (which will be described shortly) can play a key role.
cases where entropy cannot play role, e.g., when the attacker forces
2) Loss-weighted averaging. The server also measures the loss of each model using the public data. Based on the loss values, the server aggregates the models as follows:
W
Σ kES.
(5)
(6) & (F)))
(6)
m&
and
(6) =
(6)
KES.
Here, (k)k) is the locally updated model of the k-th device at global round t. Fpuil (w. (k)) is defined as the averaged loss of (k)k) computed on public data at the server, i.c., Fmub (w (k))
pub Ryub 2Ø=1 (ww,()); (puts))))) Finally, 8(2 0) in (-)3 is a loss exponent related to the impact of the loss measured with public data. We note that a setting ö 0 in (5) reduces our less-weighted averaging method to FedAvg of (T. Under the data poisoning attack or model replacement backdoor attack (or scaled backdoor attack) in M. the models of adversaries have relatively larger losses compared to others. Fig. 2(d) shows an example with FMNIST dataset under data poisoning attack.
By the definition of 3! (k)) (8), the data data-poisoned model would be given small weight and has a less impact on the next global update. By replacing FedAvg with the above loss- weighted averaging, we are able to build system that is highly robust against data poisoning and scaled backdoor attacks. As can be seen from Fig. [ the impact of data poisoning cannot be filtered out via entropy measures, since the benign and infliced models have similar entropy values. This indicates that the loss measure has its own unique role, along with the entropy measure.
Entropy-basee filtering and loss-weighted averaging can be easily combined, and work complemen- tarily to tackle model poisoning, data poisoning and scaled backdoor attacks. Utilizing only one of these methods significantly degrade the performance, as shown later in Section F of Supplementary Material.
5

---

2.3 Sageflow
Finally we put together Sageflow, which can handle both stragglers and adversaries at the same time by applying entropy-based filtering and loss-weighted averaging in each grouping stage of our grraggle--mitigating staleness- aggregation. The details of overall Sageflow operation are described in Algorithm| and Fig. [
We stress that Sageflow performs well with only very small amount of public data the server, 1% of the entire dataset, which is comparable to the amount of local data at single device. This would not cause large delay as the server generally has large computing resources compared to that of devices. The computational complexity of Sageflow depends on the number of received models at each global round, and the running time for computing the entropy/loss of each model. Assuming that the complexity of computing entropy or loss is linear to the number of model parameters as in [26]. the time complexity of our scheme can be written as (fpab) [w]K) (where |w] is the number of model parameters), which scales linearly with K, the number of devices. The time complexity of Zeno is the same as ours, but suffers from performance degradation as can be seen in the experimental results in Section 4 Compared to RFA, Sageflow requires higher complexity by the factor Nypub This additional computation of Sageflow compared to RFA is the cost for considerably better robustness against adversaries.
Algorithm 1 Proposed Sageflow Algorithm
Input: Initialized model wo, Output: Final global model wr
Process at the Server
1: for each global round = 0, 1,..., T 1 do
2: Choose S. and send the current model and the global round (ws, t) to the devices
3: Wait for Ta and then:
4: for i 0, 1, ..... do
5:
U. (Et)
{K [E()) Fea) // Entropy-basee based filtering in cach group V141 = E EnEUS" (FeN) g( (8),.())
6:
(1)
/eLosswwegghted averaging in each group (with same staleness)
7: end for
8: Wi+1 = (1 w/w: + Y Ei oe (A)v/)) Averaging of representative models (with different
staleness)
9: end for
Process at the Device: Device l receives (wa, f) from the server and performs local updates to obtain (k)).. Then each benign device l sends (wr(k), E) to the server, while malicious adversary sends poisoned model depending on the type of attack.
Convergence Analysis
In this section, we provide insights into the convergence of Sageflow with the following standard assumptions FL
13 25
The global loss fuction F defined in (7) is p-strongly convex, i.e., F(x) < F(y)+ VF(x) (I -)- ve-ylla for all x, y. Moreover, F is L-smooth, i.e., F(x) F(g)+VF(() v) f1 w112 for all x, y-
Assumption
Assumption Let w be the model of the k-th benign device after i local updates starting from global round t. Let (k) be set of data samples that are randomly selected from the device for 1)-th local update. Then, 1....NN N and = 1,...,E. E.
& pr holds for all t and k
Let B,S0) and M be the set for benign and adversarial devices of U(()) respectively, satisfying 0.() B(S') U M(( and B((d) n (M()) 0. Similarly, define (((') (Ees) and M. (Ea) as the sets obtained after entropy-basee filtering is applied to 13(() and ( Now we have the following definition which describes the effect of the adversaries.
Definition Let 22 (Eens 5) be the weighted sum of loss weights for the adversaries k E M( (En) and their loss differences from F(w*):
2 (Et,,
Σ
(K))
(7)

---

90
60
Teat aocurany
80
Test accursey
Tost aocuracy
5o
-.
40
18
Satetlow (Cuus)
80
Sasetow (aors)
Bapeloow (Dars)
Vas partill Twdfvng
Was stagglers
Fedligg
40
Ignore shagglers Footing
Wast atruppare Feshhng
Taskkync
20
Wall pertill stagples Foshio
Wett striggiees Feedkyg
Foohig
30
20
40
60
50
40
60
80
100
200
400
600
800
1000
1200
Running time
Running tmm
Punniing time
(a) MNIST
(b) FMNIST
(c) CIFARIO
Figure 3: Performance with only stragglers: The performance of Sageflow is comparable to FedAsync while outperforming other schemes. However, to he shown in Fig. 5 FedAsyne performs well with only stragglers; it does not integrate naturally with methods that counter adversaries.
Based on the above assumptions and definition, we state the following theorem which provides the convergence bound of Sageflow in terms of staleness exponent X, entropy threshold Esg and loss exponent 8. The proof is in Section L of Supplementary Material.
Theorem Suppose Assumptions !
hold and the learning rate 1j is set to be less than 1. Then
Sageflow satisfies
((F(WT) F(w")) s of (F(oo) F(w*)]+ (1-2²)((A, Fen,
(8)
where v = 1 7(1 =
P1 +1+ + mazmaz (A) + 2p (Era, 8)
(A, Eeh,
(9)
201112
G Gmaa(() max E ai (A)e Mmax((Exs)) 6) max 26 (Eih, 8), el = = F(w:))F((w.) ISTST
2,5tt
In (8) above, we see a trade-off between vF, which determines the convergence speed, and (1 - -f ) which represents an error. Note that v is function of both 7. which the weight on the new model during time-averaging of models in 3 and E. which is the number of local updates. If we increase y, we have a higher convergence speed (i.e., small v²)) ) but larger error term, which is the same tradeoff observed in (25) when there are only stragglers. With adversaries also considered, however, our scheme allows a separate control on the error term Z(), Esh, 5) through staleness exponent X, frittp--iltering threshold Es, and the loss-weighted exponent 8. Here, in Z(A, Ein. 8) of (9). Gman( (A) the eтror term caused by stragglers controlled by X, and 1mman 5)) the error caused by adversaries controlled by E. and 6. First, to gain insights Gmaz (A), assume that the loss of the global model decreases as global round increases, i.e., F(w;) < (F(w) for i > j. Then, we (t-1)
have et
(0) (1) ....> > Gt
(5) (5) we have to increase the 0. In order to reduce Σiz1 at (A)e,
(4) (A) for a large i (weight for the group with small staleness) while reducing (2) for small (weight for the group with large staleness). By choosing an appropriate X, we can control the error term Gmez while taking advantage of the results sent from stragglers. As for the adversary-induced error 4yna (Eih 6). by imposing a threshold Er.. we can reduce the portion of adversaries (with high entropies) in each group U,(0) (Feg), which in turn reduces (7). Likewise, by introducing ö, we can reduce the loss-weights 3 g(4)( (8) (defined in (6) of the adversaries with large losses, which again reduces 12 according to (7). These effects can significantly reduce 2maz of (9) compared to the scheme that does not utilize the entropy/loss based idea (Es.. co, 5 = 0). A more detailed discussion on the effects of X, E.,. 5 on Gmaz (A) and Q EEn, 8) is described in Sections M and N of Supplementary Material. In the next section, we show via experiments that Sageflow in fact successfully combats both stragglers and adversaries simultaneously and achieves fast convergence with small error term.
staleness exponent À to increase at
Df according
Experiments
In this section, we validate Sageflow on MNIST 10, FMNIST 23 and CIFARIO g The dataset split into 60,000 train and 10,000 test samples for MNIST and FMNIST, and split into 50,000 train and
7

---

Teat accurany
-2
8
Tost accurazy
50
60
1PA
Fozing
Test
Sageline 10
80
(OURE))
40
Pees
800
20
50
150
150
100
150
200
400
600
800
1000
1200
Global round
Global round
Global round
(a) MNIST
(b) FMNIST
(c) CIFARIO
Figure 4: Performance with only adversaries (model poisoning): Sageflow shows better over performance
than other schemes.
Table 1: Performance with only adversarics
Medel prisoning
poisoning (Test accuracy)
Scaled buckdoor attick
(Test accuracy)
(Atlack success rale)
Methods: Datasels
||
MNIST
FMNIST
CIFARIO
MNIST
FMNIST
CIFARIO
MNIST
FMNIST
CITARIO
FedAAg
22.168
33.70%
10.00%
93.58%
81.54%
53.02%
90.90%
99.88%
98.07%
7anss
34.09%
31.00%
10.00%
94.115
84.05%
57.88%
0.4%%
2.94%
3.07%
RFA
95.9%
68.01%
16.48%
96.73%
83.079
65.0218
67.254
66.6%
86.868
Sagellow (Ours)
97,55%
86.65%
65.47%
97.60%
85.14%
64.46%
0.39%
1.718
2.14%
10,000 test samples for CIFARIO. A simple convolutional neural network (CNN) with 2 convolutional layers and 2 fully connected layers is utilized for MNIST, while CNN with 2 convolutional layers and fully connected layer is used for FMNIST. When training with CIFARIO, we utilized VGG-11.
We consider N = 100 devices each having the same number of data samples. We randomly assigned two classes to each device as in [8] to create non-III situations. We ignored the batch normalization layers when training VGG-11 with CIFAR1O. At each global round, we randomly selected a fraction C' of devices in the system to participate. For the proposed Sageflow method, we sample 2% of the entire training data uniformly random to be the public data and performed FL with the remaining 98% of the train set. We note that Sageflow performs well even with a smaller amount of public data (less than 2%) and even with a flass-imbllaneed public data, as described in Supplementary Material. The number of local epochs at each device is set to 5. The local batch size is set to 10 for all experiments except for the backdoor attack. In addition, we used tuned hyperparameters for Sageflow and other comparison schemes; the details are described in Supplementary Material. Here, we emphasize that the performance of Sageflow not highly sensitive to the hyperparameters such as loss exponent 8 and entropy threshold Eth, as long as they are chosen in reasonable range. These results are also shown in Section of Supplementary Material.
Experiments with stragglers. To confirm the advantage of Sageflow, we first consider the scenario with only the stragglers. The adversaries are not considered here. With only stragglers, we compare Sageflow with the following methods. First is the wait for stragglers approach where FedAvg is applied after waiting for all the devices at each global round. The second scheme is the ignore stragglers approach where FedAvg is applied after waiting for a certain timeout threshold and ignore the results sent from slow devices. The third scheme is the wail for a percentage of stragglers where FedAvg is applied after waiting for specifie portion of the selected devices in each global round. In the main manuscript, we consider a scheme that waits for 50% of selected devices, while the results with other portions are shown in Section of Supplementary Material. Finally, we consider the asynchronous scheme (FedAsync) [25] where the global model is updated every time the result of each device arrives. For Sageflow and FedAsyne, 7 decayed while the learning rate is decayed in other schemes.
In Fig. 3 we plot the test accuracy versus running time on different datasets with C = 0.1. For fair comparison, the global aggregation at the server performed with every Tą =1 periodically for Sageflow and other comparison schemes (ignore stragglers, FedAsyne). To model stragglers, each device can have delay of 0, 1, 2 global rounds which is determined independently and uniformly random. In other words, at each global round t, we have S, 0:(() U U U v-(t)
6+2- Experimental results in a more severe straggler scenario (delay of 0 to global rounds) is shown in Section of Supplementary Material. Our first observation from Fig. 3 is that the ignore siragglers scheme can lose significant data at each round and often converges to a suboptimal point with less accuracy. The wait for stragglers scheme requires the largest running time until convergence due to the delays caused
8

---

50
Test socuBby
Test sccunbty
Sagellow Daan
Sog RIAA
Slag 1910
more shopppiee R04
E
30-
(ywen siwaytees RSA
Well partial araggles RPA
lyneeeragggleen AFA
Weat for atraglecs RIA
Vea for 1i wogero- 177
20
10
100
100
100
100
0
200
400
600
800
1000
1200
Rurning time
Punning time
Running
(a) MNIST
(b) FMNIST
(c) CIFARIO
Figure 5: Performance with both stragglers and adversaries (model poisoning): Sageflow outperforms
various combinations aiming to handle stragglers/adversariiss.
Table 2: Performance with both stragglers and ad adversaries
Model poisoning (Test accuracy)
Datt paisoning
Scaled backdoor attock
(Test aecuracy)
LAttack success rate)
Methods) Datasets
MNIST
FMNIST
CIFAR10
||
MNIST
FMNIST
CIFARIO
||
MNIST
FANIST
CIFARIO
Zeno-
9.95%
9.21%
12.27%
10.00%
10.00%
Ignore stngggers + REA
10.04%
10.055
10.00%
97.38%
80.78%
64.31%
Wait for partial straggeen REA
78.29%
35.29%
10.00%
97.59%
70.15%
62.13%
32.16%
98,29%
82.26%
Walt for stragglers RFA
96.201
70.01%
17.17%
96.60%
801.0195
55.51%
3.17%
42.791
81.74%
Sag XIA
95.78%6
73.64%
10.00%
97.60%
64.19%
99.97%
59.97%
90.2916
Pod/syncc ellow
84.7%
66.38%
53.03%
83.47%
18,80%
51.28%
99.99%
99.861
91.24%
Sageflow (Ours)
97.27%
85.23%
63.76%
97.38%
X5.0156
64.87%
0.21%
3.79%
5.56%
by slow devices. The wait for percentage of stragglers scheme achieves a similar performance with wait for stragglers scheme. Finally, it observed that the performance of Sageflow is comparable with FedAsync, the state-of-the-arr straggler-mitigating scheme. However, FedAsync is not an ideal candidate for our target scenario with both stragglers and adversaries, which will be shown in Fig.
Experiments with adversaries. Next, confirm the performance of Sageflow in Fig. 4 under synchronous scenario with only adversaries. We compare our method with geometric-medine based RFA 199 and FedAvg under the model update/data poisoning and backdoor attacks. We also consider Zeno+ (27 which utilizes public data at the server: the server first computes the difference between the loss of the received model and the loss of the previous global model. If this loss difference is above a certain threshold, the corresponding model is filtered out. Since there are no stragglers in Fig. we considered synchronized version of Zeno+ where the models are aggregated via FedAvg after the filtering process. For a fair comparison, we let 2% of the training data to be the public data and the remaining 98% to be distributed at the devices, as in our Sageflow. Comparison with other robust aggregation methods including Multi-Krum is done in Section E of Supplementary Material. For model poisoning, each adversarial device sends -0.1w to the server, instead of sending the true model w. For data poisoning attack, we conduct label label-flipping 22), where each label i is flipped to label i + 1. For both attacks, we set to 0.2 and the portion of adversarial devices is assumed to be r 0.2 at each global round. Additional experimental results with varying portion of adversaries are reported in Section J of Supplementary Material.
For the backdoor, we use the model replacement method (scaled backdoor attack) [ in which adversaries transmit the scaled version of the corrupted model to replace the global model with a bad model. We conduct pixel-patter backdoor attack (6) in which the specific pixels are embedded in a fraction of images, where these images are classified as a targeted label. See Section B of Supplementary Material for the detailed setting. We measure the attack success rate of the backdoor task by embedding the pixel-pattern into all test samples (except data with label 2) and then comparing the predicted label with the target label. We applied backdoor attack in every global round after the 10-th round for MNIST and FMNIST, and after the 1000-th round for CIFARIO.
In Fig. 4 and Table I we compare performance of different schemes with only adversaries. The performance of the table is obtained at a specific global round (see Section A of Supplementary Material for description) by averaging the accuracy over 3 independent trials. FedAvg does not work well on all datasets, and the performance of RFA gets worse as the dataset/neural network model become more complex. Although Zeno+ utilizes public data, it does not perform well under model poisoning attack. This is because the models of adversaries cannot be filtered out based on losses in the beginning of training (see Fig. 2(b).. making Zeno+ difficult to filter out the poisoned

---

models when the scale factor is 0.1. Zenot also has lower performance compared to others in data poisoning, since the loss difference between the global model and the model of adversary is not significant. However, in scaled backdoor attack, we have a large loss difference for Zeno+. Hence, Zeno+ performs well under the scaled backdoor attack. Overall, the results confirm the advantage of Sageflow compared to other methods. The results on no-scaled backdoor attack, where the corrupted model is transmitted without scaling, are shown in Section B of Supplementary Material: to summarize the results, Sageflow can slow down the poisoning of the global model.
Experiments with both stragglers and adversaries. Finally in Fig. 5 and Table 2 we consider the setup with both stragglers and adversaries. We compare Sageflow with various straggler/adversse defense combinations, including Zenot. We consider an asynchronous version of Zeno+ as in [27] the server first subtracts each survived model (after filtering) from the previous global model to obtain the model difference. Then, the global model is updated asynchronously based on each model difference. Comparison with the Multi-Krum is illustrated in Supplementary Material. We set C² 0.2, r = 0.2 for model/data poisoning and C = 0.1, The stragglers and adversaries are modeled as in Fig. and Table ! respectively. Note that in scaled backdoor attack, we excluded the results for Zeno+ and RFA combined with ignore stragglers, since the models are not trained at all. We have the following observations. First, Zeno+ does not perform well since it does not take both the staleness and entropy into account. It can be also seen that the wait for stragglers scheme combined with RFA suffers from the straggler issue. Our next observation is that the RFA combined with ignore stragglers method exhibits poor performance. The reason is that the attack ratio could often be very high (larger than r)) for this deadline-based scheme, which degrades the performance of RFA. Due the same issue, RFA combined with our staleness-aware grouping (Sag) has performance degradation. FedAsync does not perform well when combined with entropy-based filtering and loss- weighted averaging (eflow), since the model update is conducted one-by-one in the order of arrivals. Due to the same issue, FedAsync cannot be combined with RFA. Overall, the proposed Sageflow performs the best, confirming significant advantages of our scheme under the existence of both stragglers and adversaries.
0.1 for the scaled backdoor attack.
5 Conclusion
We proposed Sageflow, a robust FL scheme that can handle both stragglers and adversaries at the same time. The staleness-aware grouping allows the server to effectively utilize the results sent from stragglers. The grouping-basee strategy also integrates naturally with effective defenses against adversary attack. In each grouping stage of our straggle-mittgating approach, entropy -baed filtering and loss-weighted averaging function in a highly complementary fashion to protect the system against wide variety of adversarial attacks. Theoretical convergence analysis provides key insights into why the suggested methods work well. Extensive experimental results show that Sageflow enables robust FL in practical scenarios with a large number of slow devices and adversaries.
An interesting future issue is how to combine existing secure aggregation methods with Sageflow. This presents challenge the server should have access to every received individual model to calculate the entropy and loss values in Sageflow.
Acknowledgments
This work was supported by IITP fund from MSIT of Korea (No. 2020-0-00626) and by National Research Foundation of Korea (No. 2019R111A2A020611
References
[1] Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How 2018.
to backdoor federated learning, arXiv preprint
[2] Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. arXiv preprint arXiv:1206.66 63896,6639908 2012.
[3] Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, pages 119-129, 2017.
10

---

[4] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv:1712.05526. 2017.
[5] Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems, 1(2):44, 2017.
[6] Tianyu Gu, Brendan Davitt,, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv: 2017.
[7] Jakub Konečný, H Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint 110.0:411, 2016.
[8] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[9] Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. In Concurrency: the Works of Leslie Lamport, pages 203-226. 2019.
[10] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (0(11))277822) 2324, 1998.
[11]
Qinbin Li, Bingsheng He, and Dawn Song. agnestsgnostic round-optimal federated learning via knowledge transfer. arXiv preprint arXiv:2010.01017, 2020.
[12] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. arXiv preprint arXiv: 07873, 2019.
[13] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data, arXiv preprint arXiv:1907002166 2019.
[14] Xingyu Li, Zhe Qu, Bo Tang, and Zhuo Lu. Stragglers are not disaster: A hybrid federated learning algorithm with delayed gradients. arXiv preprint arXiv:2102.063222 2021.
[15] Yanan Li, Shusen Yang, Xucbin Ren, and Cong Zhao. Asynchronous federated learning with differential privacy for edge intelligence. arXiv preprint arXiv:1912.07903 2019.
[16] Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. 2017.
[17] Xiaofeng Lu, Yuying Liao, Pietro Lio, and Pan Hui. Privacy-preserving asynchronous federated learning mechanism for edge network computing. IEEE Access, 8:48970-48981, 2020.
[18] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. coammunication-effiiennn learning of deep networks from decentralized data. In Artificial Intelligence and Statisties, pages 1273-1282, 2017.
[19] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning, arXiv preprint
2019.
[20] Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H Brendan McMahan. Can you really backdoor federated learning? arXiv preprint arXiv: 011199111076.. 2019.
[21] Marten van Dijk, Nhuong V Nguyen, Toan N Nguyen, Lam M Nguyen, Quoe Tran-Dinh, and Phuong Ha Nguyen. Asynchronous federated learning with reduced number of rounds and with differential privacy from less aggregated gaussian noise. arXiv preprint arXiv:2007.09208, 2020.
[22] Wentai Wu, Ligang He, Weiwei Lin, Stephen Jarvis, et al. Safa: a semiassynchronous protoooo for fast federated learning with low overhead. arXiv preprint arXiv:1910.01355. 2019. 2019.
[23] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 11Xfv:1708.00777,,20000 2017.
11

---

[24] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized byzantine-tolerant sgd. International Conference on Machine Learning. 2018.
[25] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint arXiv: Iet..09033.4444. 2019.
[26] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-base fault-tolerance. In International Conference on Machine Learning, pages 6893-6901. PMLR, 2019.
[27] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous sgd. arXiv preprint arXiv: 2019.
[28] Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. arXiv preprint arXiv: 1803.0149) 2018.
[29] Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Defending against saddle point attack in byzantine-robus distributed learning. arXiv preprint arXiv:/806.0050 2018.
[30] Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint ar arXiv:/806.00530 2018.
12


Reviews:
[{"review_id": "s1FBb7ak4F", "reviewer": "Reviewer_QeNU", "summary": "This paper proposes a robust FL approach to deal with stragglers and adversaries in federated learning. Model grouping and staleness dependent weighting of models is done at the server to deal with stragglers. For model poising attacks, entropy-based filtering is proposed, where a client model entropy is calculated on a public dataset stored at the server. Same dataset is used to calculate loss of different client models at the server to identify clients contributing data-poisoned models. Theoretical bounds on convergence of the proposed method are obtained. Experimental results with three image classification datasets show that the proposed approach outperforms existing solutions to deal with stragglers and adversaries in FL. ", "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": "The paper has some novel ideas, in particular the idea of using both entropy-based filtering and loss-weighted averaging provides protection against both model poisoning and data poisoning attacks. The proposed approach Sagerflow integrates techniques for straggler mitigation and adversarial robustness in FL. The work is technically sound and performance of Sageflow is much better against the baselines. \nThe paper is well written and the main ideas are explained clearly. \nMajor comments: \n1. Line 39-40: \"The presence ...aggregation schemes\". This sentence is not clear. What if attackers are also the stragglers ? In that case avoiding stragglers will drive the attack ratio lower. Right ? \n2. The assumption that you have access to public data at the server is very strong. First you do not know what is the distribution of the data across all the clients. What should be the data distribution of this public data ? You are using this public data for entropy and loss calculations of individual client models to identify if they are potential adversaries or not. Basically if the entropy is high or the loss is high you mark the device as adversarial. But entropy and loss can be higher every for benign devices if their local data distribution is very different than data distribution at other clients. \n3. Higher entropy may not always mean an adversary. Since you are calculating entropy using public data, it may happen that higher entropy of a client model with public data is simply because the client has a very different data distribution than the public data. If this is the case then  filtering out the client model and not using it in global model update is not a good idea. Your global model may never be able to learn from the data local to the client. \n4. You are accounting for all the stragglers in your update, even the one which arrive very late. I am not sure if this is a good idea as too stale weights will only make the training unstable. Why not just set a threshold on stragglers even for your grouping approach ? \n5. How does Sageflow computational overhead at the server scales with number of clients ? With more clients you need to calculate entropy and loss for more number of clients using the public data. You should show scalability of Sageflow with increasing number of clients . \n6. Why were batch normalization layers ignored when training VG-11 and CIFAR10 ?\n7. Line 283: What is parameter C ? \n8. Your results in the main paper are for very low staleness distribution (0,1,2). How does Sageflow perform with higher sateness values ? What is the final accuracy with Sageflow vs baselines in Figure 3. I would assume the benefits with Sageflow will diminish with high staleness and increased non-iid-ness of data distribution across clients. \n9. Use a better term instead of \"model update poisoning\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not discussed limitations of their work. You need to provide example of scenarios where your approach may not work. Since your approach requires availability of public data at the server which is representation of global data, your approach will not work in FL settings where such data is not available or no knowledge about global data distribution is available . ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "pj5Ujcmiqj", "reviewer": "Reviewer_voGc", "summary": "The paper addresses a scheme to protect federated learning against stragglers and adversaries at the same time. For straggler resistance, the authors propose to group and weight the model coefficients according to their age. For resistance against adversaries they propose entropy-based filtering and loss-weighted averaging. Combining these schemes leads to their proposed Sageflow approach. They also provide an upper bound on the expected loss function error after a fixed number of operations.", "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": "Although the paper is merely a combination of two different schemes, which seems to be orthogonal in its impact, the strengths of the paper are in my opinion the convincing numerical results compared to other schemes and the convergence analysis, which ties the performance limiting impacts of straggling and adversarial nodes together.\n\nOn the other hand, the paper has several weaknesses, mostly in terms of clarity. While the description with respect to the straggler resistance was near to me, I was not able to follow their strategy to combat adversarial actions:\n- I do not understand the underlying model to eq.(4) and why publicly available data helps. Specifically, how is P^{(q)}_{x_pub} computed? I must be fundamentally misunderstanding the idea as we do have these training examples the corresponding labels available. So isn't the corresponding probability always 1? The authors need to clarify this point in their response. \n- In line 180, why is the loss function computed between the weights and the data x? This does not make any sense to me.\n- The authors should also clarify the novelty of their approach. It is clear that perhaps the combination and the bound in Theorem 1 is new, but what about the individual approaches with respect to stragglers and adversaries?\n- Gradient coding is another method to provide straggler resistance in synchronous federated learning. It would be useful to compare their straggler approach with these synchronous schemes to properly assess the merit of their work.\n\nIf the authors satisfactorily respond to these questions (in particular to my first point), I am willing to increase my rating.\n\n---------------------\n\nAfter the authors's response: \nFrom reading the authors'c comments to my questions, the other reviews, and their response to those, I understand their scheme better now. Consequently, I am updating my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "alUEaRL9bY", "reviewer": "Reviewer_X8AG", "summary": "This paper studies and the interesting problem of presence of both stragglers and adversaries in Federated Learning (FL), and proposes a solution that simultaneously addresses both issues. There's no question that the challenges considered in this paper are important to the FL community. The solution is based on grouping the late model update from stragglers, incorporating them into the model update, and performing an entropy-based filtering to find the adversarial updates. The paper has really interesting and comprehensive experiments, and it is backed by theoretical findings. ", "questions": "", "limitations": "", "rating": 7, "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": "The paper proposes an original solution to address both stragglers and adversaries in FL. The idea is novel and very interesting. The claims in the paper are backed by theory and comprehensive experiments. The sheer number of experiments and ablation studies are quite useful in evaluating the claims of the paper. The paper is well-written and it is easy to read\n\nI have the following major comments:\n1. Complexity: It seems like the proposed solution has high running time complexity. In particular, the equation (4) is calculated for every update. Computing entropy seems to be of high complexity (I might be wrong, but I get this feeling by reading the paper, as it goes through all data samples in public dataset and also depends on number of classes in dataset). Can the authors explain the asymptotic time complexity of their algorithm? How does the asymptotic time complexity of their algorithm compares to the other related algorithms mentioned in the paper?\n\n2. Datasets: The authors have used the following datasets: MNIST, FMNIST, and CIFAR10. These datasets are not always representative of the challenges in FL. The gold standard benchmark for FL is LEAF: https://leaf.cmu.edu.\n\n3. Question: It would be great if authors could provide more explanation/justification why entropy is a good measure? In the current writeup of the paper, it seems a bit ad-hoc why entropy is a good measure to detect some attacks. \n\nSome minor suggestions:\n- when referring to supplemental material from the main text, it would be nice to refer to the exact section.\n- some figures can be improve. E.g. fig 2c and fig 6 have data points all over the figure which makes the figures hard to read.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss the limitations and negative societal impact of their work. I suggest authors think deeply about their scheme, and discuss these in the full manuscript. While it may not be very easy to find direct societal impact of this work, topics such as bias and discrimination (when we filter out adversaries, would it be possible that we are also discriminating?) might be easier to discuss. Also, I suggest the authors discuss the limitations of their work, as it would make their paper higher quality and would make it more honest about its assumptions and applicability of the solutions discussed in the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "FIJmlx8MTZ1", "reviewer": "Reviewer_BUwC", "summary": "This paper proposes an approach, Sageflow, that jointly handles stragglers and Byzantine users in FL. Sageflow groups the users based on their staleness to handle stragglers and uses entropy-based filtering and loss-weighted averaging to provide Byzantine-robustness. This approach depends on the assumption that the server has access to a public dataset or the users share part of their data with the server to to identify the Byzantine users. Several experiments show that effectiveness of the Sageflow against some of the prior approaches.  ", "questions": "", "limitations": "", "rating": 7, "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": "The proposed approach, Sageflow, handles stragglers and Byzantines jointly and prior works only focus on one of these two issues.\nThe idea of adapting the weights while aggregating the models based on the staleness is a nice idea as the the updates get less important as they become stale. Sageflow also combines between entropy-based filtering and loss-based averaging to handle Byzantine users, which is a good idea as each metric is more suitable for certain class of attacks. \n\nI overall like the proposed approach, but there are some issues that should be addressed as I discuss below.\n\n1- There are some prior approaches that also use data sharing to handle Byzantine users such as [1, 2], but this paper does not compare with them.\n\nWhile these works only deal with Byzantine users and do not consider stragglers, it is good to compare the proposed strategy with them. \nYou should also consider comparing with the OracleSGD [2] as a reference. \n\n2- Line 124: \"Note that the result sent from device $k \\in U_t^{(i)}$ is the model after E local updates starting from $\\mathbf w_i$\". \n\n3- The entropy-based filtering requires performing inference using the models of the users and the public samples at the servers. This seems significant and there's no discussion on the complexity of doing so. What's the complexity of this?\n\n4- I do not see why high entropy always means that the user in Byzantine, what if this is due to the non-IID data distribution?\nIt's mentioned later in line 162 that some attacks tend to make the entropy high as they make the predictions random, but some other attacks also may be biased toward specific class and hence they result in a low entropy. \n\n5- Line 139: It's mentioned that the active users who get a new request should ignore this request. It may be better for those users instead to respond to this request and ignore the computations that they are doing. This is intuitive as the fresh updates are more important than the stale updates. Why ignoring the new request is better? \n\n6- Line 170: You mention that your work can handle large number of adversaries, what's this number? and how do you decide the threshold for the entropy-based filtering? \n\nIn Multi-Krum, 2f+2<N, what about Sageflow?\n\n7- A limitation of this work also is that it does not consider the convergence for the non-convex case. \nThis seems to be doable as a recent work considering a similar problem has done this analysis.\n \nThis work appeared after the deadline for NeurIPS, so it's not an issue at all that you have not considered it. \n\n8- Why did you ignore the batch normalization layers in Section 4? Please explain and add results with batch normalization as well. \n\n9-  Line 86: You mention independent, identically distributed, but this should have been mentioned the first time the term IID is used. \n\n10- Line 292 has a typo: \"percantage\"\n \n[1] X. Cao et al. \"FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping.\" arXiv preprint arXiv:2012.13995 (2020).\n\n[2] S. Prakash, and A. S. Avestimehr. \"Mitigating byzantine attacks in federated learning.\" arXiv preprint arXiv:2010.07541 (2020).\n\n[3], J. Nguyen et al. \"Federated Learning with Buffered Asynchronous Aggregation.\" arXiv preprint arXiv:2106.06639 (2021).\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no discussion on the limitations and potential negative societal impact. Since the work focuses on Byzantine mitigation, it has a positive societal impact. Please also see my comments above for my suggestions. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a robust approach to dealing with stragglers and adversaries in federated learning by model grouping and staleness-dependent weighting of models at the server, combined with entropy-based filtering. Stragglers and adversaries are two key concerns in federated learning, and this paper makes progress along both fronts. The reviewers generally received this work well, and the authors’ responses helped address many of their concerns, leading reviewers to increase their scores. Overall, the consensus was that this paper is worthy of acceptance and makes a solid contribution to the federated learning literature. When preparing the camera ready, please make sure to address the questions that came up during the review process, especially around clarifying the proposed approach.
Decision: Accept (Poster)