From Gossip to Distributed Optimization (and back again)

Consensus in a network is a fundamental, thoroughly, studied problem. It is well known that the main obstacles to it are unreliability and asynchronism as stated by the celebrated “FLP impossibility result”. However under smoother assumptions, several works in the past decade have shown that consensus can be reached using very simple algorithms known as Gossip. Interestingly enough, these gossip algorithms turned out essential in the more complex setting of distributed optimization wherethe sought consensus has to solve an optimization problem.

The first part of this talk will introduce the main concepts and tools: distributed algorithms, gossip, distributed optimization. In a second part of the talk, I will discuss how to rely on distributed optimization to build more robust gossip schemes.