Deterministic Gossiping

Abstract

For the purposes of this paper, gossiping is a distributed process whose purpose is to enable the members of a group of autonomous agents to asymptotically determine, in a decentralized manner, the average of the initial values of their scalar gossip variables. This paper discusses several different deterministic protocols for gossiping which avoid deadlocks and achieve consensus under different assumptions. First considered is $T$- periodic gossiping which is a gossiping protocol which stipulates that each agent must gossip with the same neighbor exactly once every $T$ time units. Among the results discussed is the fact that if the underlying graph characterizing neighbor relations is a tree, convergence is exponential at a worst case rate which is the same for all possible $T$-periodic gossip sequences associated with the graph. Many gossiping protocols are request based which means simply that a gossip between two agents will occur whenever one of the two agents accepts a request to gossip placed by the other. Three deterministic request-based protocols are discussed. Each is guaranteed to not deadlock and to always generate sequences of gossip vectors which converge exponentially fast. It is shown that worst case convergence rates can be characterized in terms of the second largest singular values of suitably defined doubly stochastic matrices.