Convergence Speed of Asymptotic Consensus Algorithms

Speaker : Thomas Nowak (DYOGENE)
Date: 10/12/2013
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40


Asymptotic consensus is a phenomenon observed in bird flocking, firefly synchronization, opinion spreading, or synchronization of coupled oscillators. Algorithms that achieve asymptotic consensus are used in systems like sensor networks, dynamic load balancing protocols, robot formation protocols, or rendezvous in space.

These algorithms have a simple form: At every step of the algorithm, each agent forms an average of values observed from neighboring agents. These algorithms guarantee asymptotic consensus among agents even under very light conditions on the (dynamic) communication topology and the weights used in the calculation of the averages.

Equivalently, asymptotic consensus can be seen as convergence of not necessarily reversible and not necessarily time-homogeneous Markov chains to their limiting distributions.

This talk introduces asymptotic consensus and presents new upper bounds on its convergence speed, generalizing recent results by Cao et al., Oshevsky and Tsitsiklis, and Chazelle.