Convergence Time for Unbiased Quantized Consensus Over Static and Dynamic Networks

DOI10.1109/TAC.2015.2440568MaRDI QIDQ2980670zbMATH OpenOpenAlexFDO

Authors Seyed Rasoul Etesami, Tamer Başar

Publication date 3 May 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random walks on graphs (05C81) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Abstract: In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides a tight upper bound for the expected convergence time to consensus based on the parameters of the network. Moreover, the paper identifies a precise order of the maximum expected convergence time for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives a tight upper bound for expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier results for the quantized consensus problem over time-varying graphs.

Recommendations

• Convergence Time of Quantized Metropolis Consensus Over Time-Varying Networks
• An Upper Bound on the Convergence Time for Quantized Consensus of Arbitrary Static Graphs
• Convergence time analysis of quantized gossip consensus on digraphs
• Average consensus on networks with quantized communication
• Convergence speed in distributed consensus over dynamically switching random networks
• On quantized consensus for multi-agent networks under communication delays
• On the Convergence Time of Asynchronous Distributed Quantized Averaging Algorithms
• Fast convergence for consensus in dynamic networks
• Fast convergence for consensus in dynamic networks
• Quantized consensus over directed networks with switching topologies

Cited in

(10)

• Synchronization of coupled harmonic oscillators using quantized sampled position data
• Non-oscillating quantized average consensus over dynamic directed topologies
• Distributed averaging with linear objective maps
• An Upper Bound on the Convergence Time for Quantized Consensus of Arbitrary Static Graphs
• Continuous-time quantized consensus: convergence of Krasovskii solutions
• Maximizing convergence time in network averaging dynamics subject to edge removal
• Duality and Stability in Complex Multiagent State-Dependent Network Dynamics
• Convergence Speed of Unsteady Distributed Consensus: Decay Estimate Along the Settling Spanning-Trees
• On the Structural Perspective of Computational Effectiveness for Quantized Consensus in Layered UAV Networks
• A simple framework for stability analysis of state-dependent networks of heterogeneous agents

This page was built for publication: Convergence Time for Unbiased Quantized Consensus Over Static and Dynamic Networks

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