Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of decentralized training in the presence of Byzantine peers. The paper proposes a Byzantine-tolerant algorithm which uses randomly chosen peers as validators. A validator recomputes the gradient and ‘accuses’ a peer if the computation is not correct. Towards this end, the paper proposes to leverage two primitives from secure Multi-Party Computation (MPC) literature: secure broadcast and multi-party random number generator. For robust aggregation, the paper relies on Centered Clipping proposed recently in [Karimireddy et al. 2020].
main_review: While there are a large number of papers on Byzantine robustness in the parameter server setting, there are relatively few papers for the decentralized setting. In this sense, the paper is timely and relevant. However, the paper lacks in giving sufficient details, which makes it difficult to understand the contributions and novelty. Detailed comments are as follows.

Major comments:

1. How can one ensure that the policy on page 6 where a worker can eliminate one other worker along with themselves, cannot be exploited by Byzantine workers? Can it happen that a Byzantine worker b eliminates an honest worker h, and ensures that another honest worker h’ eliminates b. In this case, (b,h) and (b,h’) will be eliminated. In other words, Byzantine worker b could eliminate two honest workers. It needs a proof that this type of attacks are not possible. Moreover, since the setup is decentralized how consensus happens to determine if a pair of workers to be eliminated. It will be important to give more details.

2. What is the computation and communication complexity at each peer for BTARD? Validators need to recompute the gradients, and in addition, in case if a peer accuses another peer, all other peers need to recompute the gradient. This suggests huge computation overhead. Would this recalculation of gradients outweigh the benefits of parallelism? It is crucial to quantify computation and communication costs explicitly. 

Moreover, how much additional communication cost is incurred by using secure broadcast and MPRNG? Appendices A.2.1 and A.2.2 treat these primitives at a very high level. It would be helpful to select a suitable protocol from the literature, and give enough details.

3. In experiments, baseline methods include coordinate-wise median and geometric median, How are these computed in the decentralized setting? It will be important to give more details. 

4. How much improvement the proposed BTARD algorithm gives as compared to baseline methods? From Figures 2 and 3, it seems like the improvements are very marginal. Can the authors quantify the improvements in terms of percentage increase in accuracy (or decrease in loss), and add a discussion on comparison?

5. The authors mention that they omit common (and powerful) attacks in [Baruch et al. 2019, Xie et al. 2020, Allen-Zhu et al. 2021] as these attacks are designed to bypass certain checks, which are not used by the proposed algorithm. The proposed algorithm does not use variance and magnitude checks does not mean that these attacks will fail. These attacks were proposed to show inefficiency of several well-known Byzantine robust schemes such as Krum and coordinate-wise median. So, it will be important to test BTARD against some of these attacks.

Other comments:

1. The paper assumes that training is performed on a public dataset, which can be accessed by all peers. It would be helpful to justify this assumption. In the Byzantine robustness literature, many papers consider data parallelism, where data is distributed across peers. In such a setup, it would not be possible to validate by recalculating gradient. It would be helpful to add a discussion on this assumption. 

2. The paper does not formally introduce the decentralized training setup being considered. How many peers in total, and how many are Byzantine? Can any peer talk with any other peer? Can Byzantine peers collude? A few details are given in Sec. 3.2 after the proposed methods. It will be important to describe these details up front.

3. The authors do not give any description or details about Algorithms 1-3 in the main text. It is difficult to understand the algorithms, and takes a long time for the reader. 

summary_of_the_review: The paper considers a challenging problem of Byzantine-tolerant learning in the decentralized setup (without a parameter server). However, the paper lacks in many details and does not quantify costs and gains of the proposed algorithm.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper develops a byzantine resilient algorithm for distributed training via SGD without a trusted centralized node. The key idea is that it improves upon recent decentralized algorithms by using cryptographic primitives. In particular, a multiparty random number generator is used to randomly verify subsets of devices in each iteration, enabling the algorithm to learn byzantine behavior that deviates sufficiently from the protocol. The paper provides rigorous theoretical result in terms of convergence guarantee, with a rate that depends on the number of byzantine adversaries. The derived rate depends on the fraction of nodes that are byzantine (capped by 50%, which is standard in this literature). In cases where no node is adversarial, the derived convergence rate matches that of the standard algorithms.
main_review: +The paper develops a careful protocol utilizing cryptographic primitives (MPC), unlike similar works that mainly aim to eliminate byzantine behavior by comparing the gradients provided by various nodes. The utilization of  MPC is novel, and the provable convergence guarantee is a strength of the paper. 
+/- While the paper's protocols work only in the case where nodes are able to sample i.i.d. from the overall data set (the "homogenous" setting), the paper refers to recent lower bounds that preclude byzantine tolerant algorithms in the heterogenous setting (at least in the worst-case).   
- The implementation of the cryptographic primitives to keep the byzantine behavior in check requires a number of all-to-all communication exchange. While the lack of a centralized trusted node is expected to make the protocols more expensive, a key missing ingredient of the paper is an explicit accounting for this communication cost. I believe it will greatly improve the contribution if this cost is explicitly characterized and reported.
- The algorithm explanation could improve in terms of clarity. For instance, the paper refer's to a butterfly all reduce procedure, which seems to suggest that each node receives the sum of all the numbers (gradients) that are transmitted in the step. However, the descriptions in Algorithms 1,2, only include "Send" and "Receive" primitives, and the algorithms in the appendix do not seem to do aggregation as a part of the communication primitives - it is done separately and explicitly in the centeredclip procedure. This can be explained more clearly. Note that the peer-to-peer communication (i.e., n^2 different messages being sent) also has an impact on the communication cost (referred to above). 
- The paper seems to provide distinct converge behavior for the case where the number of byzantine adversaries is explicitly known. A clear/intuitive explanation of why the behavior is distinct can enhance the paper.  

summary_of_the_review: Overall solid piece of work. It is worth considering the paper modulo addressing the comments above.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes BTARD-SGD, which is a Byzantine-tolerant training algorithm (via stochastic gradient descent) in decentralized environments (i.e., peer-to-peer architectures). BTARD-SGD does not require the presence of a trusted central server and introduces only a marginal overhead compared to a vanilla All-Reduce SGD algorithm. BTARD-SGD relies on an existing clipping algorithm in the literature called CenteredClip in addition to a series of checks to catch Byzantine nodes which might not follow the algorithm. The authors provide theoretical analysis in addition to a fair amount of experiments.
main_review: Thanks for submitting your work to ICLR2022. The paper addresses a very important and timely problem. While there is a lot of work addressing Byzantine resilience in ML, we need works that focus on their practicality in terms of performance and assumptions about the environment. I also like the motivating example of crowdsourcing computational resources from (possibly) untrusted parties. I appreciate the convergence rates that the authors derive in different scenarios (strongly convex, convex, and non-convex functions), and I like the fact that the overhead of the proposed algorithm does not depend on the model size. We, as a community, need to always think of such solutions (whose overhead is decoupled from the model size).

Yet, I believe the paper cannot be accepted as-is as it requires to be revised in a few aspects. In summary, (1) the authors make several assumptions that seem unrealistic and unjustified. (2) The most important parts of the paper are either unclear or deferred to the appendices; this makes it hard to understand the algorithm and to see its benefits. (3) As the main aim of the paper is to provide a computationally efficient algorithm, the paper should give clearly the computation complexity of all parts of the algorithm.

The first area of improvement is to clarify and back up the assumptions. Specifically, I'd like to point out 3 assumptions: The first is the public dataset assumption. Doesn't that make the problem trivial? Can you give examples in which this assumption is practical? Furthermore, many parts of the main algorithm require synchronous networks. It's important that the authors clearly state this in their assumptions. Synchronous networks are easy to achieve in a controlled environment like a datacenter. Yet, in a more challenging environment that the authors consider, I'm not sure how synchronicity can be achieved. The third uncommon assumption is about adversary capabilities. I do not understand the need for the second paragraph on page 6 (which describes the possible attacks). Byzantines should be able to do whatever they want [1,2]. Putting them in categories in which they can do only limited things raises the question of whether the considered model is really for Byzantine attacks or not.
[1] Lamport, Leslie. "The weak Byzantine generals problem." Journal of the ACM (JACM) 30.3 (1983): 668-676.
[2] Castro, Miguel, and Barbara Liskov. "Practical byzantine fault tolerance." OSDI. Vol. 99. No. 1999. 1999.

There are essential parts in the paper that are not described clearly and left to the appendices. One example is how the broadcast channels work in Section 2.3. The authors seem to describe consensus. Is that it? If yes, this concept is orthogonal to multi-party computation (MPC). If not, then what is the difference between the suggested method and consensus? The same comment goes for the main algorithm in the paper. Essentially, there is no appropriate (even high-level, intuitive) explanation of why it works, with all the proofs deferred to the appendices. The most important example is the CenteredClip algorithm, which is the main tool to tolerate the Byzantines. For example (more examples below in the additional comments/questions), from the description, I understand that the input to this algorithm is two gradients: the local one and the one gathered from all peers (by merging a small part of the gradient from each peer). If my understanding is correct, I do not see how clipping (based on two inputs only) can be effective in tolerating Byzantine behavior. It's crucial to understand at least intuition without looking at complex mathematical proofs. I also expected to see even proof sketches in Sections 3.2 and 3.3. The absence of these parts makes it very hard to judge the effectiveness of the proposed work.

Parts of the algorithm are not clear and the computation complexity is not rigorously quantified. For example, what is the cost of the validation step? If we need a lot of validators, why do we need distributed learning in the first place? If peers can compute their gradients and the others' gradients (for validation), why bother distributing? In addition, I believe many parts of the algorithm rely on consensus (even if that was never explicitly mentioned by the authors). Consensus is costly, and a careful analysis of its complexity is required. Along the same direction, I have two issues with the "accuse" procedure: (1) it's very costly because all peers have to compute the gradient of the accused peer; a Byzantine can use this trick to make learning very slow. (2) The procedure relies on consensus, which is also costly. Another unclear part is the cost of sampling the random direction z among all peers.

Additional comments/questions:
1. The authors mentioned that existing solutions either require a trusted server or have prohibitive communication costs. I know at least one paper [3] that does not require either. Can the author comment on that?
[3] El-Mhamdi, E. M., Guerraoui, R., Guirguis, A., Hoang, L. N., & Rouault, S. (2020, July). Genuinely distributed byzantine machine learning. In Proceedings of the 39th Symposium on Principles of Distributed Computing (pp. 355-364).

2. The third paragraph on page 6 is problematic. The authors mentioned an attack in which the system removes one Byzantine and one benign node. In this case, the Byzantines can do this attack until 2f nodes are removed (with f being the original number of Byzantines). Since the algorithm requires n > 2f+1 then, in extreme cases, this attack leaves the system with only 1 node! In other words, the authors seem to acknowledge that a Byzantine node can defeat the distribution of the algorithm, making it behave as if there is only one central node.

3. I do not understand the last line of Section 2.1. Why does **each** peer require O(dn) in the PS architecture? I believe each one requires only 2d: 1d to upload the gradient and 1d to download the model. Can you please clarify this?

4. The first sentence of Section 3.1 ("The core design principle behind our algorithm is that all types of Byzantine faults must have limited effect and a chance of being discovered.") is a bit weird. Usually, Byzantine attacks are posed as the strongest attack to diverge learning. It is strong because Byzantine peers can do whatever they want (i.e., it's also called: behave arbitrarily).

5. It's not clear if clipping is effective against random attacks? I understand it will be robust against gradients with big magnitudes (like the attacks in the evaluation section) but what about the other attacks?

6. It's not clear how the butterfly method works? If you only broadcast a part of the gradient, then what is aggregated in this case? Is it only the local part of a peer and a corresponding part received from another peer?

7. In Algorithm 2, a Byzantine can equivocate as follows. It can send different hashes (for the same part of the gradient) to different peers. It can then send different values for that part to different peers so that the hashes match the received gradients on each peer. Is that a problem for your algorithm?

8. The validation step is not rigorous because you might be unlucky and get the Byzantine node to validate another Byzantine node in one iteration. Clearly, Byzantines can get away with their attack (without being caught) in this iteration. What are the practical/theoretical results of such a situation?

9. The solution to Sybil attacks (in Section 3.2) is not convincing. A Byzantine node can prove its honesty only to enter the system and then it can do whatever it wants. This problem (i.e., tolerating Sybil attacks) is interesting and I encourage the authors to give it more discussion in the main paper.

10. The authors seem to rely on (Karimireddy et al., 2020) a lot. What are the main differences between this work compared to this work? Is it only PS architecture vs. decentralized architecture? If so, what are the additional challenges that you solved?

11. The federated learning (FL) example in the motivation does not fit nicely. As mentioned in the paper, one important aspect of FL is data privacy yet, the solution in the paper relies on the assumption that the dataset is public and can be accessible by anybody. I advise the authors to remove FL from their motivating examples.

12. The authors chose the clipping value (\tau) based on out-of-band experiments. Can the authors add a discussion on how to choose a clipping value practically (without initial experiments)?

13. What are the coordinate-wise trimmed median and geometric median baselines? It's clear how to use these aggregators with a central server yet, they are not well-defined in the decentralized case. If the authors are referring to some work in the literature, please add the necessary citations.

14. As the authors mentioned, they use only specific parts of MPC rather than a fully-fledged MPC protocol. I suggest the authors do not use this term and use specific terms of the specific algorithms they use instead.

15. The expression "zero trust assumption" is a bit of a stretch. For example, you need at least 50% of honest peers.

16. What is the percentage of the validators (i.e., what is the inequality between m and n)? How does this percentage affect the correctness of the algorithm?

17. The authors mentioned that m validators will validate the work of m peers. It seems from the evaluation section that there is a one-to-one mapping, in this case, i.e., each validator validates one peer. Please make this clear while describing the algorithm.

18. How can one report a Byzantine node? This again requires consensus, right?

19. It will be great if the authors can add to the paper an explanation of how CenteredClip works.

20. I suggest you better explain \tau in Equation (2). Currently, it is not clear in the text; I understood what it means only in the evaluation section.

21. In Algorithm 2, Step 7: you either mean "broadcast" instead of "send" or you mean g_i[j] instead of g_i. The same fro Step 8. I believe you mean the latter though (given Step 9 is "MERGE" rather than "AGGREGATE").

22. A few important function definitions are missing: CenteredClip, ValidatePeer, VoteForBan, and Ban. Other functions are also missing, but they are less important.

23. Footnote 4 is a bit off because the paper does not consider the heterogeneous case.

24. I do not buy the omission of "common low-magnitude attacks (Baruch et al., 2019; Xie et al., 2020; Allen-Zhu et al., 2021)". These are the SOTA attacks, and it is important to show how your algorithm behaves under these attacks.

25. What is the attack in Figure 2 (first two figures)?

26. The upper-middle plot of Figure 2 shows that the geometric median is almost as good as your algorithm. What is the benefit of your algorithm in this case?

27. Why does the coordinate-wise median diverge in the upper-left figure in Fig. 2?
summary_of_the_review: Though the paper addresses a very important and timely problem, I believe it cannot be accepted as-is as it requires to be revised in a few aspects. In summary, (1) the authors make several assumptions that seem unrealistic and unjustified. (2) The most important parts of the paper are deferred to the appendices; this makes it hard to understand the algorithm and to see its benefits. (3) As the main aim of the paper is to provide a computationally efficient algorithm, the paper should give clearly the computation complexity of all parts of the algorithm.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper seems to propose a new use-case of an existing Byzantine fault-tolerant protocol called CenteredClip in a federated learning setting. Although the authors state that their approach fits the decentralized learning setting, the protocol relies on some sort of leader selection.
 
The authors bring CenterClip's equation without explaining the problem setting to a reasonable clarity. It seems the use of multi-party random number generation for Eq.(1) is the main novelty, but its context is not clear.
 
The authors make two assumptions on the objective function on which distributed members strive to compute the gradient, but the novelty and the context are unclear.
main_review: This paper addresses a very interesting task of machine learning under a decentralized setting. As the authors mention, ensuring Byzantine fault tolerance in the learning system is very hard under a general learning setting. Some of the requirements will need to be relaxed, as is the case in recent decentralized learning works (just a few examples: I know they do not discuss Bizantine):

- Tran et al., "An efficient approach for privacy preserving decentralized deep learning models based on secure multi-party computation," Neurocomputing 422(2021) 245-262
- Ide et al., "Efficient Protocol for Collaborative Dictionary Learning in Decentralized Networks," Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 19,  August 10-16, Macao, China), pp.2585-2591
 
In this paper, the authors use leader selection schemes for "validator" and "accuse", which does not make the protocol entirely decentralized even if the selection is random. The authors need to clarify the main challenge of the existing methods and the key achievement of the paper. The first half of the paper does not look very successful in clarifying research motivation.

Questions 
p.3
"that permutation-invariant algorithms cannot converge to any predefined accuracy of the solution" sounds unreasonable because the original aggregation is permutation symmetric. Please elaborate. 
 
p.4
Is there any risk assessment of the validator selection step?
 
p.5
No definition of Split.

summary_of_the_review: - unclear description
- limited novelty
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces BTARD-SGD as a new algorithm for distributed training among untrusted Byzantine nodes. The underlying all reduce architecture makes the proposal appealing for large scale applications due to the reduction in the communication cost. The paper contains a convergence analysis for convex and non-convex loss functions and a proof for resilience against Byzantine and Sybil attacks. The authors verify the efficacy of their proposal on image classification and NLP tasks.
main_review: ### Strengths

[Significance]

All reduce is a very popular architecture for large scale distributed training with the case of Byzantine tolerance being an open problem. The results of this paper are important.

[Novelty] 

The proposal builds on multiple existing schemes that come from both the ML optimization literature (centered clip, butterfly all reduce) and distributed algorithms (e.g., DHT, MPRNG).

[Quality] 

There is sufficient technical depth for the main claims of the paper (both for theoretical guarantees and for system design choices). The authors discuss their main assumptions and clarify cases in which they don't apply. 

[Presentation / Clarity]

The paper is well written and easy to follow. Parameter choices are provided and the extensive supplementary material contain the necessary details for the proofs and complementary explanations of the method.

### Weaknesses

[Significance]

- The assumptions needed for the algorithm, prohibit an extension of the work to a setup with decentralized data (such as in federated learning). The problem of Byzantine tolerance is less motivated in the case where each node can access the entire training dataset as in this case it is often preferable to scale out in a more controlled environment (e.g., data centers) where crash failures are present but Byzantine ones are much less likely to occur. The strict IID assumptions for the paper are limiting. Convergence guarantees can still be achieved with some bound on the dissimilarity among the datasets as in practice the datasets are not arbitrarily different. Byzantine-resilient learning on decentralized data is a challenging yet open problem. For reference see the submission and discussion here: https://openreview.net/forum?id=7JSTDTZtn7-

- The reputation system for nodes that join and leave introduces another limitation for the proposal, as it requires an additional application-dependent hyperparameter (T).

[Evaluation] 

- The paper targets the large-scale setup. However, there is no evaluation of the scalability of the proposal and only experiments with up to 16 participants are shown. 

- Missing experimental results for the case of nodes joining.


summary_of_the_review: Although the paper has some significant weaknesses, I tend to recommend an acceptance given the technical depth and significance of the problem addressed.
review_title: null

Meta-review: This paper presents promising and ambitious work in the context of Byzantine-tolerant learning in the decentralized setup. The reviews raised several critical points of concern: completeness of technical derivations and details, experimental results and comparisons to other work, excluding several state of the art attacks. The reviewers provided with a generous amount of feedback, that should be incorporated in the paper before publication. Unfortunately the camera ready timeline is quite sort for such an extensive feedback to be integrated in this paper.  The authors are urged to resubmit after taking into account all the suggestions that were made during this review cycle.
Decision: Reject