Convergence Speed of Unsteady Distributed Consensus: Decay Estimate Along the Settling Spanning-Trees

By David Angeli, Pierre-Alexandre Bliman. 2006

74 citations recorded by the source corpus.

Results for estimating the convergence rate of nonstationary distributed consensus algorithms are provided, on the basis of qualitative (mainly topological) as well as basic quantitative information (lower-bounds on the matrix entries). The results appear to be tight in a number of instances and are illustrated through simple as well as more sophisticated examples. The main idea is to follow propagation of information along certain spanning-trees which arise in the communication graph.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Mechanical Engineering

Citations in the corpus

Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control (2014, unknown): “A number of papers studied the convergence speed of discrete-time (not necessarily average) consensus for a wide class of updates over time-varying directed graphs; see [82, 40, 10, 9, 5, 13, 12, 30].”
Convergence Speed in Distributed Consensus and Averaging (2009, unknown): “Recently, the problem has attracted signiﬁcant attention [18, 22, 2, 11, 24, 7, 14, 25, 26, 13, 8, 5, 1], motivated by new contexts and open problems in communications, sensor networks, and networked control theory.”
Distributed consensus over network with noisy links (2009, unknown): “(5) From relations (3) and (4), we have xi(k + 1) = xi(k)− αk X j 6=i wij(k)xi(k) + αk X j 6=i wij(k)xj(k) + αkξi(k) = xi(k)− αk(1− wii(k))xi(k) + αk X j 6=i wij(k)xj(k) + αkξi(k) = (1− αk) xi(k) + αk mX j=1 wij(k)xj(k) + αkξi(k).”