An upper bound on the convergence time for quantized consensus
An upper bound on the convergence time for quantized consensus
复制标题
量化共识收敛时间的上限
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
S. Kulkarni
中科院分区：
文献类型：
--
作者：
Shang Shang;P. Cuff;Pan Hui;S. Kulkarni
本文分析了一类适用于任意网络的分布式量化一致性算法。在初始设置中，网络中的每个节点都具有整数值。节点在网络中交换它们当前的平均值估计，然后通过在异步时钟设置中的有限容量信道中与它们的邻居通信来更新它们的估计。最终，所有节点以量化的精度达成共识。我们从一个特殊的分布式二进制投票算法开始分析，然后继续Kashyap等人提出的一般量化共识算法的预期收敛时间。我们使用电网络，随机游动和马尔可夫链耦合的理论来推导一个O（N3 log N）任意大小为N的图上的预期收敛时间的上界，改进了二进制一致性算法的O（N4 log N）和量化一致性算法的O（N5）的现有技术界限。我们的结果是不依赖于图的拓扑结构。仿真进行验证的分析。
We analyze a class of distributed quantized consensus algorithms for arbitrary networks. In the initial setting, each node in the network has an integer value. Nodes exchange their current estimate of the mean value in the network, and then update their estimate by communicating with their neighbors in a limited capacity channel in an asynchronous clock setting. Eventually, all nodes reach consensus with quantized precision. We start the analysis with a special case of a distributed binary voting algorithm, then proceed to the expected convergence time for the general quantized consensus algorithm proposed by Kashyap et al. We use the theory of electric networks, random walks, and couplings of Markov chains to derive an O(N3 log N) upper bound for the expected convergence time on an arbitrary graph of size N, improving on the state of art bound of O(N4 log N) for binary consensus and O(N5) for quantized consensus algorithms. Our result is not dependent on the graph topology. Simulations are performed to validate the analysis.