Gossip over holonomic graphs

Xudong Chen, Mohamed Ali Belabbas, Ji Liu

Research output: Contribution to journalArticlepeer-review


A gossip process is an iterative process in a multi-agent system where only two neighboring agents communicate at each iteration and update their states. The neighboring condition is by convention described by an undirected graph. In this paper, we consider a general update rule whereby each agent takes an arbitrary weighted average of its and its neighbor's current states. In general, the limit of the gossip process (if it converges) depends on the order of iterations of the gossiping pairs. The main contribution of the paper is to provide a necessary and sufficient condition for convergence of the gossip process that is independent of the order of iterations. This result relies on the introduction of the novel notion of holonomy of local stochastic matrices for the communication graph. We also provide complete characterizations of the limit and the space of holonomic stochastic matrices over the graph.

Original languageEnglish (US)
Article number110088
StatePublished - Feb 2022


  • Consensus
  • Convergence of matrix products
  • Gossiping
  • Holonomy
  • Markov processes

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Gossip over holonomic graphs'. Together they form a unique fingerprint.

Cite this