Gossip over holonomic graphs

DOI10.1016/J.AUTOMATICA.2021.110088MaRDI QIDQ2063863zbMATH OpenOpenAlexFDO

Authors Xudong Chen, Mohamed-Ali Belabbas, Ji Liu

Publication date 3 January 2022

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.08853

zbMATH Keywords

consensusconvergence of matrix productsgossipingholonomyMarkov processes

Mathematics Subject Classification ID

Stochastic matrices (15B51) Multi-agent systems (93A16) Consensus (93D50) Stochastic systems in control theory (general) (93E03)

Abstract: 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.

Recommendations

• Convergence of periodic gossiping algorithms
• Analysis of accelerated gossip algorithms
• The contraction coefficient of a complete gossip sequence
• Nonlinear gossip
• Convergence rate on periodic gossiping

Cites work

• Cluster consensus with point group symmetries
• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
• Consensus seeking in multiagent systems under dynamically changing interaction topologies
• Coordination of groups of mobile autonomous agents using nearest neighbor rules
• Distributed Averaging Using Periodic Gossiping
• Distributed averaging with linear objective maps
• How to decide consensus? A combinatorial necessary and sufficient condition and a proof that consensus is decidable but NP-hard
• scientific article; zbMATH DE number 3135399 (Why is no real title available?)
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• Matrix Analysis
• Non-negative matrices and Markov chains.
• On Convergence Rate of Weighted-Averaging Dynamics for Consensus Problems
• Product of Random Stochastic Matrices
• Products of Indecomposable, Aperiodic, Stochastic Matrices
• Reaching a Consensus
• Reaching a Consensus in a Dynamically Changing Environment: A Graphical Approach
• Reaching a Consensus in a Dynamically Changing Environment: Convergence Rates, Measurement Delays, and Asynchronous Events
• Stability of multiagent systems with time-dependent communication links
• Towards consensus: some convergence theorems on repeated averaging
• Triangulated Laman graphs, local stochastic matrices, and limits of their products

Cited in

(5)

• Triangulated Laman graphs, local stochastic matrices, and limits of their products
• Nonlinear gossip
• The contraction coefficient of a complete gossip sequence
• scientific article; zbMATH DE number 1538541 (Why is no real title available?)
• Co-design of networked gossip protocol and distributed control for interconnected large-scale systems

This page was built for publication: Gossip over holonomic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2063863)