Guodong Shi: On finite-time convergent gossip algorithms: existence, complexity, and some applications

Gossip algorithms have been widely applied in modern distributed systems, for which we have witnessed examples ranging from sensor networks and peer-to-peer networks, to mobile vehicle networks and social networks. Tremendous research has been devoted to analyzing, or even improving, the asymptotic rate of convergence for gossip algorithms. In this work we study finite-time convergence of deterministic gossiping. We show that there exists a symmetric gossip algorithm that converges in finite time if and only if the number of network nodes is a power of two, while there always exists a globally finite-time convergent gossip algorithm despite the number of nodes in cooperation with asymmetric updates. For $n=2^m$ nodes, we prove that a fastest convergence can be reached in $mn$ node updates via symmetric gossiping. On the other hand, for $n=2^m+r$ nodes with $0\leq r<2^m$, it requires at least $mn+2r$ node updates for achieving a finite-time convergence when asymmetric gossiping is allowed. It is also shown that the existence of finite-time convergent gossiping often raises strong structure requirement to the underlying interaction graph.

Two applications of the derived results will also be briefly discussed. First for a model of opinion dynamics over signed social networks defined by randomized attraction-repulsion gossiping, we show that finite-time convergence leads to fundamental robustness in view of the Borel-Cantelli Lemma. This provides a reflection of the obtained finite-time convergence results in randomized gossiping algorithms. Second, we apply our results to recent studies on gossip algorithms in quantum networks, where the goal is to control the state of a quantum system via pairwise interactions, and show that finite-time convergence is never possible in this case.

This is a joint work with Bo Li, Academy of Mathematics and Systems Science, Chinese Academy of Sciences; Alexandre Proutiere, Mikael Johansson, Karl H. Johansson, Automatic Control, KTH; and John S. Baras, University of Maryland College Park.

Short Bio

Guodong Shi received his Ph.D. from Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China, in 2010. Since Aug. 2010 he has been a postdoctoral researcher at the ACCESS Linnaeus Centre, School of Electrical Engineering, Royal Institute of Technology, Sweden. His research interests include distributed control, computation, and optimization methods over deterministic or random graphs motivated by engineering and social networks. (see people.kth.se/~guodongs/ for more information)