Convergence Time of Quantized Metropolis Consensus Over Time-Varying Networks

2015/04/06 by Basar, Tamer, Etesami, Seyed Rasoul, Olshevsky, Alex
#Distributed #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Parallel #Probability (math.PR) #Systems and Control (eess.SY) #and Cluster Computing (cs.DC) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.1504.01438

Abstract

We consider the quantized consensus problem on undirected time-varying connected graphs with n nodes, and devise a protocol with fast convergence time to the set of consensus points. Specifically, we show that when the edges of each network in a sequence of connected time-varying networks are activated based on Poisson processes with Metropolis rates, the expected convergence time to the set of consensus points is at most O(n² log² n), where each node performs a constant number of updates per unit time.

Related

• An Upper Bound on the Convergence Time for Quantized Consensus
• An Upper Bound on the Convergence Time for Distributed Binary Consensus
• Convergence Time Analysis of Quantized Gossip Consensus on Digraphs
• Continuous-time quantized consensus: convergence of Krasowskii solutions
• Degree Fluctuations and the Convergence Time of Consensus Algorithms