Convergence rate of optimal periodic gossiping on ring graphs
Shaoshuai Mou, A. Stephen Morse, Brian D. O. Anderson · 2015
In an n-node connected graph A, each node i is with a real-valued state xi(t), i = 1, 2, ..., n, and is able to communicate with certain other nodes. A periodic gossip sequence is able to drive all xi(t) to converge to 1/n Σ1=1nxi(0) equation exponentially fast. Different sequences are usually associated with different convergence rates for graphs with cycles. This paper mainly focuses on a type of optimal periodic gossip sequences for ring graphs. Explicit formulas to compute their convergence rates are given, which are determined by the adjacency matrix of the n over n/2-node ring graph when n is even and Chebychev polynomials of the second kind when n is odd.