Asynchrony and Acceleration in Gossip Algorithms

Mathieu Even (1) , Hadrien Hendrikx (1) , Laurent Massoulié (1)

1 DYOGENE - Dynamics of Geometric Networks

This paper considers the minimization of a sum of smooth and strongly convex functions dispatched over the nodes of a communication network. Previous works on the subject either focus on synchronous algorithms, which can be heavily slowed down by a few slow nodes (the straggler problem), or consider a historical asynchronous setting (Boyd et al., 2006), which relies on a communication model that cannot be readily implemented in practice, as it does not capture important aspects of asynchronous communications such as non-instantaneous computations and communications. We have two main contributions. 1) We introduce a new communication scheme, based on Loss-Networks, that is programmable in a fully asynchronous and decentralized fashion. We establish empirically and theoretically that it improves over existing synchronous algorithms by depending on local communication delays in the analysis instead of global worst-ones. 2) We provide an acceleration of the standard gossip algorithm in the historical asynchronous model without requiring any additional synchronization.

Domaines: Optimisation et contrôle [math.OC]; Probabilités [math.PR]; Machine Learning [stat.ML]; Calcul parallèle, distribué et partagé [cs.DC]; Système multi-agents [cs.MA]

Mathieu Even, Hadrien Hendrikx, Laurent Massoulié. Asynchrony and Acceleration in Gossip Algorithms. 2020. ⟨hal-02989459v1⟩