网络Gossip算法的研究

发布时间:2017-10-10  |  来源:数学机械化重点实验室

Gossip算法是分布式网络系统中的重要算法,在分布式计算网络、传感器网络、P2P服务网络和社会网络等领域都有着重要的理论与应用价值。基于gossip原理的协议已经成为现代分布式系统的一类标准解决方式;Gossip算法也是社会网络信息传递和观点演化的一个基本模型。该算法的渐进收敛性以及收敛效率一直是这方面的研究热点。该算法理论模型由图灵奖得主Karp 与其合作者在2000年提出,并给出渐近收敛性证明。众多研究者,包括麻省理工学院Shah教授,加州理工学院Murray院士,斯坦福大学Boyd 教授,都继续深入研究了gossip算法的渐近收敛性。

对于计算机网络和网络控制中的gossip算法,现在已经有了深刻的理论认识。但是渐近算法在有限时间内只能给出近似结果,只有有限时间收敛算法才可以给出精确结果。那么一个重要的问题是,确定性有限时间收敛的对称gossip算法是否存在?如果存在,该算法的计算复杂度是多少?

最近,李博与澳大利亚国立大学的石国栋博士,瑞典KTH的Mikael Johansson教授,Karl Henrik Johansson教授(IEEE Fellow)合作构造性的给出了确定性gossip有限时间收敛算法。他们证明了一个由n个结点组成的网络上可能存在精确有限时间收敛gossip算法的充分必要条件是n是 2 的幂次。如果n不是2的幂次,则对于几乎所有的初值,都不存在有限收敛的gossip算法。根据Borel-Cantelli引理,在满足有限时间收敛的条件下,随机gossip算法以概率1有限时间收敛。该结果刻画了基于gossip协议的计算机网络应用的性能极限。利用算法复杂性理论,他们进一步证明了该算法是理论上可能存在的最快的算法。

早在2013年意大利学者Mazzarella 等人提出了量子gossip算法并证明了在相当广泛的条件下,该算法渐进收敛。李博与合作者发现,这一n量子比特的gossip算法等价于一个总共有 22n个结点的分区块的并行计算的经典对称gossip网络。这些连通的网络区域中,必然有结点个数不是 2的幂次的区域。由此,利用上面给出的经典对称gossip算法存在的充分必要条件,他们建立了量子gossip算法不可能性定理:对由任意n个量子比特组成的量子网络,有限时间收敛的gossip算法都不可能存在。下图给出了一个 3 量子比特的gossip算法等价的 64结点的分区块的经典对称gossip网络。

与本成果相关的论文: 

[1] Shi, G., Li, B., Johansson, M., & Johansson, K. H. (2016). Finite-time convergent gossiping. IEEE/ACM Transactions on Networking, 24(5), 2782-2794.