Deterministic gossiping with a periodic protocol
Shaoshuai Mou, Changbin Brad Yu, Brian D. O. Anderson, A. Stephen Morse · 2010
A sequence of allowable gossips between pairs of agents in a group is complete if the gossip graph which the sequence generates is a connected spanning subgraph of the graph of all allowable gossip pairs; such a sequence is minimally complete if there is no shorter sequence which is complete. An infinite sequence of gossips is repetitively complete with period T if each successive subsequence of length T within the gossip sequence is complete. Any such sequence converges exponentially fast. A repetitively complete gossip sequence is periodic with period T if each gossip in the sequence is repeated once every T time steps. The rate of convergence of a periodic gossiping process is determined by the Tth root of the second largest eigenvalue in magnitude of the stochastic matrix of the complete gossip subsequence. In the case when the graph of allowable gossips is a tree and the complete gossip subsequence is minimally complete, this eigenvalue is independent of the order in which the gossips occur within the complete gossip subsequences.