A Lower Bound on Convergence of a Distributed Network Consensus Algorithm
A Lower Bound on Convergence of a Distributed Network Consensus Algorithm
复制标题
DOI：
10.1109/cdc.2005.1582514
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
Ming Cao;D. Spielman;A. Morse
中科院分区：
文献类型：
--
作者：
Ming Cao;D. Spielman;A. Morse
本文给出了一类网络一致性算法收敛速度的一个下界。介绍了两种不同的方法，使用有向图作为主要工具：一个是计算与“邻居共享图”相关的随机矩阵的“置乱常数”，另一个是分析图序列上的随机游动。这两种方法都证明了在动态网络中达成共识的时间在相对误差上是对数的，在最坏情况下在网络大小上是指数的。
This paper gives a lower bound on the convergence rate of a class of network consensus algorithms. Two different approaches using directed graphs as a main tool are introduced: one is to compute the "scrambling constants" of stochastic matrices associated with "neighbor shared graphs" and the other is to analyze random walks on a sequence of graphs. Both approaches prove that the time to reach consensus within a dynamic network is logarithmic in the relative error and is in worst case exponential in the size of the network.