Convergence time analysis of quantized gossip consensus on digraphs
Convergence time analysis of quantized gossip consensus on digraphs
复制标题
DOI：
10.1016/j.automatica.2012.06.048
复制
发表时间：
2011-05
期刊：
影响因子：
--
通讯作者：
Kai Cai;H. Ishii
中科院分区：
文献类型：
--
作者：
Kai Cai;H. Ishii
我们最近提出了量化八卦算法，该算法以最少的连通性要求来解决有向图上的一致性和平均问题。本文研究了这些算法的收敛时间。为此，我们研究了共识算法中包含所有状态的最小区间的收缩时间，以及平均算法中合适的Lyapunov函数的衰减时间。通过研究，我们可以用特定马尔可夫链上的命中时间来表征收敛时间。考虑了完全图中每条边都可以被等概率激活的特殊情况，简化了状态转移的结构，并导出了收敛时间的多项式上界。
We have recently proposed quantized gossip algorithms which solve the consensus and averaging problems on directed graphs with the least restrictive connectivity requirements. In this paper we study the convergence time of these algorithms. To this end, we investigate the shrinking time of the smallest interval that contains all states for the consensus algorithm, and the decay time of a suitable Lyapunov function for the averaging algorithm. The investigation leads us to characterize the convergence time by the hitting time in certain special Markov chains. We simplify the structures of state transition by considering the special case of complete graphs, where every edge can be activated with an equal probability, and derive polynomial upper bounds on convergence time.