Convergence Speed in Distributed Consensus and Averaging
Convergence Speed in Distributed Consensus and Averaging
复制标题
DOI：
10.1137/110837462
复制
发表时间：
2011-01-01
期刊：
影响因子：
10.2
通讯作者：
Tsitsiklis, John N.
中科院分区：
文献类型：
--
作者：
Olshevsky, Alex;Tsitsiklis, John N.
我们研究了共识和平均问题的分布式迭代算法的收敛速度，重点是后者。我们首先考虑固定通信拓扑的情况。我们表明，对共识算法的简单改编会导致平均算法。我们证明了各种线性，时间不变，分布式共识方法的最差案例收敛时间的下限，并提供了一种与这些下限匹配的算法。然后，我们考虑时间变化的拓扑结构，并提供多项式平均算法。
We study the convergence speed of distributed iterative algorithms for the consensus and averaging problems, with emphasis on the latter. We first consider the case of a fixed communication topology. We show that a simple adaptation of a consensus algorithm leads to an averaging algorithm. We prove lower bounds on the worst-case convergence time for various classes of linear, time-invariant, distributed consensus methods, and provide an algorithm that essentially matches those lower bounds. We then consider the case of a time-varying topology, and provide a polynomial-time averaging algorithm.