Asynchrony and Acceleration in Gossip Algorithms

Hadrien Hendrikx (1) , Laurent Massoulié (1) , Mathieu Even (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.

Mots clés: gossip algorithms; loss networks; distributed optimization; asynchrony; acceleration

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]

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