
handle: 1885/63163
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.
nonhomogeneous Markov chains, Distributed process, Underlying graphs, Convergence rates, Distributed averaging, stochastic matrices, Gossiping protocols, 510, Deterministic protocols, Initial values, W Consensus, Keywords: Consensus, Singular values, Doubly stochastic, Time units
nonhomogeneous Markov chains, Distributed process, Underlying graphs, Convergence rates, Distributed averaging, stochastic matrices, Gossiping protocols, 510, Deterministic protocols, Initial values, W Consensus, Keywords: Consensus, Singular values, Doubly stochastic, Time units
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 84 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
