Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents a new collective algorithm and associated implementation of SGD training that is optimized for distributed systems where some ranks will not participate in each training step.  The observation is that parameter servers are not scalable, and that most collective based (all-reduce) distributed algorithms are either not fault tolerant, or have significant performance impacts when there is load imbalance or system noise.  The proposed Moshpit all-reduce and SGD strive to overcome these challenges by breaking down the collective communication domains into many more "sub-domains" that can tolerate delays or absences of its participants.  However, it does so in a structured manner that is more communication efficient than a standard gossip, random, algorithm.  They show that despite stale gradients for each participant, the algorithm still converges and does so faster than SOTA algorithms.
main_review: Overall, the paper presents a clear and compelling description of the proposed algorithm.  Both the pseudo-code and block diagrams did a good job of conveying the algorithms details.  Evaluations were performed on both a standard visual network as well as a transformer based language model.  The paper also provides a detailed description of the convergence properties of the algorithm, which are empirically supported by the results shown in Figure 4.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces Moshpit All-Reduce, a fully decentralized iterative averaging protocol for large-scale training under unstable communication conditions and/or with unreliable workers. The proposed protocol allows an exponential convergence to the global average. It is shown that Moshpit SGD, built on top of Moshpit All-Reduce, is equivalent to the centralized SGD in terms of iteration complexity.
main_review: * Originality and Significance: This paper considers distributed learning over unreliable worker and communication channel. The topic is of significance in that the proposed method resolves the issues in the existing gossip based algorithms lifting the fundamental restriction and tradeoff between the communication required and convergence rate. 

* Technical quality: The technical contribution/quality of this paper overall looks good to me (didn't fully check the proof though). My only concern is that some part in the experiment section is not very clear to me. Please refer to the questions at the end of the comment (Miscellaneous). 

* Clarity in organization/writing: 

-- The organization and writing are mostly clear to me. I especially like the organization of the introduction and related work sections. I believe that It would be helpful for readers who just jumped into this area as it is easy to read and contains a fairly good list of references.

-- Miscellaneous
1) line 49: Can we quantitatively measure the additional burden for dynamically organizing workers? Do we need intervention of a moderator or any kind of centralized operation to do this? 
2) line 253: It is not clear what "all information is replicated" means. Please elaborate more.
3) line 264: It seems that the authors use the gaussian noise to model errors added to the values of the original vectors. Please consider modifying this sentence to contain the full detail.
4) Figure 3: Can we think of any tradeoffs from this figure? It was surprising that there is a fairly large gap in the behavior between the red and brown lines given the same p and a small difference in N. It would be better if the readers could get some more intuition behind the results shown in this figure.

limitations_and_societal_impact: They addressed the limitations in Appendix. I agree with the authors that it is hard to assess potential negative societal impact of this work/application.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Data parallel distributed NN training often depends on homogenous, well-provisioned networks and reliable end hosts.  This paper presents a scheme, Moshpit All-Reduce, that leverages a hybrid approach to communicating parameters (gradients) that combines elements of gossip with all-reduce to better withstand heterogeneous network environments and node failures.  The authors present their technique, and integrate it into a distributed SGD scheme (Moshpit SGD).  Microbenchmarks validate the extensive theoretical exploration of MAR, and the authors compare/contrast the system's effectiveness on both well-connected and distributed/heterogenous infrastructure.  They find that the scheme can tolerate varying network latencies and often more quickly converges by shortening training during individual epochs.   
main_review: ++ Robust training on cheap(er) nodes/networks is an important challenge. 

++ Paper provides a novel communication algorithm for efficiently performing an all-reduce average.  Extensive analysis provides support for its convergence and robustness properties.

++ Experiments on homogenous and heterogenous networks with varying network latencies illustrate its ability to quickly approximate the true average and support distributed SGD. 

++ The writing was clear and the notation consistent. 

-- Given the complexity of the theoretical analysis, the empirical validation of Moshpit All-Reduce was notably weak.  

-- There was a lack of description of the competing techniques (related work) beyond all-reduce.  (S4.2).

-- While the end-to-end training experiments are compelling, the experiment construction makes comparisons (and lessons learned) difficult.  

Overall this appears to be an important problem and the novel communication protocol is well motivated.  Most of my concerns about the work lie within the empirical evaluation.   A key contribution here is MAR, but the simplistic, limited evaluation does the work a disservice.  While theoretical results (assuming the proofs are correct) are necessary, they may not always account for reality.   A key question (and contribution) then, would be to determine under what network conditions (latency, disconnections) and failure rates will Moshpit AR (and by association MSGD) succeed or fail?  Ultimately this feels like solid, important work, but it isn't sufficiently evaluated in the current work. 

Before enumerating the kinds of experiments, there were a few places where the technical details were not clear. 
* In Algorithm 1, it would be useful to characterize the asynchrony.   For example, there is a wait for peers to assemble.  Essentially, this is view maintenance/consensus.   If a node "joins late" what occurs?   They must be kicked out of the all-reduce.   If a there is agreement on the peer set, and then peers experience failure, what is the impact on the latency of the round (internal all-reduce timeouts), what is the impact of that timeout on convergence?  Is it possible for certain network or failure conditions to allow butterfly all-reduce to end in an inconsistent state?
* It would then seem to make sense to report the number of nodes that fail to participate in a round, as well as the distribution of round length (and variance of the aggregate). Theorem 3.2 maintains that the sum of all the groups is still N.  While the theorem explores an important relaxation of the initial assumptions, node failure/disconnections imply that rounds may proceed that violate that assumption. 

To establish these properties the microbenchmarks should a.) plot the theoretical and competing systems (S4.2) results with the empirical results, b.) should change one aspect at a time (as opposed to changing N and p simultaneously), and c.) report performance statistics as a function of increasing node failure and (separately) connection latency.   Again, the point is to establish the claimed properties of MAR: faster (fewer rounds) and more efficient (less communication) convergence during failures and network performance.   

Section 4.1 doesn't clearly state M or d (leaving the reader to parse "32x32" 'grid').   I'm assuming "18 steps" is T=18.  When failed peers return, do they return with the last returned parameters?   More importantly, failing for individual rounds seems contrived.   What about failing for some unspecified period of time (modeled with some distribution)?  In reality, peers aren't going to fail on nicely behaved round boundaries.  Also, I don't understand line 268.  Why does this experiment converge in two steps with failures?  Two steps are the minimum to achieve an exact answer without failure.   Were there no failures?    On that same graph, why would N=900 with no failures take so many steps (9) to converge to the true answer?   Clearly, even without failures, the true size of the groups must be << than 32.     

A good section of the paper is taken up by showing that Moshpit AR can be used for distributed training (Moshpit SGD).   It isn't clear how many rejected distributed communications protocols have been the cause of SGD failures -- even the establishing of such theoretical bounds doesn't prevent MSGD from failing to converge during training in some situations (Section 4.3).   

- Moshpit All-Reduce also takes into consideration network bandwidth.   Was this used in all experiments?  How was the bandwidth measured?   How often / was it stable?  How big an improvement did this provide and would it apply to other systems as well? 
- S4.2 says that additional latency is added per communication round.  Is this added per host link or is it added per communicating pair (emulating latency at the end host or in the middle of the network)?  Is this delay left on for the duration of the communication round?  
- S4.2: The paper says AR-SGD is "unsuitable for heterogenous hardware."  It would be better to provide data to support this statement, i.e., how bad is it? 
- S4.2:  The paper compares against a gossip approach that communicates with 2 neighbors.  This setting appears unmotivated and rather small.   What happens if it is set in a similar fashion to the different group sizes for MSGD (4 and 8 groups)?
- S4.2 mentions "efficiency" but it's unclear what this represents.  Latency of each communication round? Number of messages? Number of bytes on the network? 
- While Figure 4 is interesting (though very small), it would also be enlightening to plot summary statistics for accuracy and latency of averaging per epoch, per mechanism.  In some ways, these are the metrics the paper discusses, but we are forced to deduce them from these end products (though the results should be directly available).     
* In S4.2, you say Moshpit SGD has "1 round of Moshpit averaging."  How does this relate to Algorithm 2?  

* The heterogenous network is unspecified.  How many nodes were at each site?  
* During actual model training it wasn't clear if there were node failures.
* What is the distribution of M_k in these heterogenous situations?  How often are there incomplete groups? 

Like adjusting partition size based on bandwidth, one could also explore building the groups based on network coordinates (rack, container, data center, etc., locality). 

__Edit [comments on author's response] :__  First, thank you for taking the time to help explain your work to the reviewers and provide additional supporting evidence for the work.  If the author's revise their work by adding the missing clarity noted by the reviewers (e.g., implications of group/grid size, how to choose group size), and incorporate the new analysis (as they suggest they will do), it will significantly enhance the paper.   I would also love to see an improved discussion of the impact of incomplete groups and failures based on the additional detail you provided.   In light of the author's commitment to improving clarity in the technical and experimental parts of the work, I will improve my score.     



limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces a decentralized averaging scheme and uses it for distributed learning.
The averaging scheme falls somewhere in between typical gossip averaging and uniform all-reduce averaging.
It inherits some of the robustness to node failures from typical gossip averaging and some of the communication efficiency from all-reduce collectives.

For each communication step, nodes are divided into groups using a decentralized hash table, and perform all-reduce averaging within their group. If a node in one group fails or takes too long to respond, other communication groups can still complete their averaging reliably. 
In the light of prior work, this method could be classified as a linear time-varying averaging scheme, with block-uniform averaging matrices.

What I personally consider the most interesting contribution of the paper, is the match-making mechanism used to group the workers. By numbering the nodes in each group at timestep $t$, and using those numbers to group the nodes in the next round, workers are never grouped with the same peers in two consecutive communication rounds. I believe this is what gives the algorithm its name 'MoshPit' (although an explanation of this is missing from the paper).

The paper contains convergence rates for the algorithm with random grouping (not with moshpit match-making), and experiments show that the algorithm can reduce training time and cost, mainly in heterogeneous environments (bandwidth or compute capabilities).
main_review: I have enjoyed reading this paper, and I particularly found the moshpit match-making scheme clever and interesting.
The quality of the writing is good and the exposition is clear. 
While I have some hesitations regarding the experiments and focus of the paper (see below), I believe efficient decentralized averaging schemes can have great significance for peer-to-peer and large-scale training.

While I think the match-making scheme described at the start of Section 3.1 is the most interesting contribution of this work (and gives the name to the proposed algorithm), I feel that this particular contribution does not receive the attention it deserves. The theory does not consider moshpit (repelling) grouping, and in the experiments, a many questions are unanswered:

- (1) How much does moshpit matchmaking help over random grouping?
- (2) Reliability to workers leaving and joining is presented as a benefit of this method. Will the group sizes remain balanced across iterations and groups if this happens? Is there a mechanism to achieve this?
- (3) The comment "wait for peers to assemble" in Algorithm 1 hides some non-trivial details. How do the workers synchronize and know their group is 'complete'? Do they use time-outs? How are those time-outs set and what is their impact on the performance of this method?

I also have some hesitations regarding the experimental setup:
- (4) While the experiments convincingly show that there are settings in which this method works well, the setup seems a little artificial (with additional randomized latency). This is fine, but I believe experiments that test individual aspects of the model could be more valuable (suggestions below)
- (5) For a group size of 2, the proposed method recovers something very much like the time-varying (torus) topology in Stochastic Gradient Push [15, 54]. For a group size of n, the method becomes all-reduce. I would like to see the impact of the choice of group size on the resilience to failures and communication efficiency. How should this be set in practice? Is there ever a benefit of using groups of size > 2 or smaller than $n$?
- (6) The benefits in the heterogeneous case seem to come mainly from the load balancing details in Appendix E. Other baselines such as all-reduce would benefit from the same mechanism. I believe it would be better if the authors could separate this contribution from their proposed averaging scheme.

While the theory in this paper is correct and relevant, it does considers a simplified algorithm (with random grouping) that does not include the match-making scheme I find most interesting about this paper.
It also seems that rates for this algorithm follow quite readily from prior work (e.g. Koloskova et al. [63]), by considering this method as time-varying linear gossip averaging with block-uniform matrices. Lines 248 and 249 compare the obtained rate to this paper. Could you please clarify the differences in the analysis?

I would consider increasing my score if the authors can address most of the questions (1 - 6). Below, I include a few minor questions and comments.

- The paper often claims that the method "does not depend on the spectral properties of the graph". I think this is misleading because the method requires a fully connected topology, and competing methods don't have such a dependence either in this case.
- Theorem 3.1 shows that a simplification of Moshpit Averaging (with random groups) converges linearly, even with communication failures. The same seems true for retrying all-reduce. Would it be possible to characterize the gains in reliability?
- For the claim about linear convergence in 131, I think you should list the key assumptions.
- I am missing some training details such as learning rates, schedules, warmup, and whether typical optimizations are used, such as overlapping computation and communication in the backward pass (see PyTorch's DistributedDataParallel).
- The paper mentions that all-to-all implementations of all-reduce are not always practical. While I can imagine this is because many messages are sent, I do not quite understand why this is problematic? Could you please elaborate a bit on this?
- Section 2.4 has some incorrect use of articles. Check [a] PS and "the changes".

__Edit:__ I have read the other reviews and the author's response. The authors have included significant new analysis. If the authors include this analysis in the paper, and commit to giving the proposed matchmaking procedure more attention in the mansucript, I would be fine with acceptance. I'll change my score from 5 to 6.
limitations_and_societal_impact: I do not see any societal impact or limitations that warrant discussion.
review_title: null

Meta-review: This paper proposes a novel approach to distributed data-parallel training, MoshpitSGD. The approach targets systems where fault tolerance and robustness important, e.g., when some worker nodes may fail, there is load imbalance, or other sources of heterogeneity in the system. This is a setting relevant to practitioners applying distributed training.

The reviewers agreed that the contribution is interesting and worthy of acceptance. While there were some questions and concerns raised in the initial reviews, the authors’s responses largely addressed these. In particular, the new empirical results nicely illustrate the tradeoff between messaging rounds and resilience to node failures. It is important that the camera-ready revision should include the points mentioned during the rebuttal to address questions raised by the reviewers to improve the clarity of the paper, especially around experimental setup and findings. We also strongly encourage the authors to include the additional experiments in the paper and make the experiments more focused on specific contributions (e.g., the proposed match-making scheme) in addition to highlighting performance of the method as a whole. This will likely involving moving/adding material to the supplementary material.

Decision: Accept (Poster)