Periodic Gossiping

Gossiping is a well-studied distributed algorithm whose purpose is to enable the members of a group of autonomous agents to asymptotically determine in a decentralized manner, the average of their initial scalar-valued gossip variables. T-periodic gossiping is a gossiping protocol which stipulates that each agent must gossip with each of its neighbors exactly once every Ttime unit. Under suitable connectivity assumptions of a graph characterizing all allowable gossip pairs, a T-periodic gossip sequence will converge at a rate determined by the magnitude of the second largest eigenvalue of the stochastic matrix determined by the sequence of gossips which occurs over a period. It has been shown in the prior work that if the underlying graph of allowable gossips is a tree, this eigenvalue is the same for all possible T-periodic gossip sequences. The aim of this paper is to develop several properties for stochastic matrices induced by the sequence of gossips occurring over a Tperiod and reprove the result using these properties in a different and simpler argument.