Francesco Pasquale: Self-Stabilizing Dynamics for Distributed Consensus
The "consensus problem" in distributed computing can be described as follows: A collection of agents, each holding an "opinion", interact with the goal of agreeing on one of the opinions initially held by at least one agent, possibly in the presence of an "adversary" that is trying to disrupt the process.
Recently, there has been considerable interest in the design of consensus algorithms in models that severely restrict communication and computational capabilities of the agents, both for efficiency consideration and because such models capture aspects of the way consensus is reached in biological systems, social networks, and other domains of interest in network science.
In this talk I will give an overview of our recent work on the performance analysis of simple consensus "dynamics", i.e., distributed "memoryless" algorithms in which at each round each agent updates its opinion based only on a few bits of information from a few of its neighbors. I will present our results on the convergence time to consensus of such dynamics and on their "self-stabilizing" properties.
Finally, I will briefly outline ongoing work on generalized forms of consensus, such as community detection, that employ spectral graph techniques in a distributed setting.
This is joint work with Luca Becchetti, Andrea Clementi, Emanuele Natale, Gustavo Posta, Riccardo Silvestri, and Luca Trevisan.