1. 研究目的与意义（文献综述）

gossip算法如其名，灵感来自办公室八卦，只要一个人八卦一下，在有限的时间内所有的人都会知道该八卦的信息，这种方式也与病毒传播类似，因此gossip有众多的别名“闲话算法”、“疫情传播算法”、“病毒感染算法”、“谣言传播算法”。但gossip并不是一个新东西，泛洪查找、路由算法都归属于这个范畴，不同的是gossip给这类算法提供了明确的语义、具体实施方法及收敛性证明。

gossip算法又被称为反熵（anti-entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了gossip的特点：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终他们的状态都是一致的，当然这也是疫情传播的特点。要注意到的一点是，即使有的节点因宕机而重启，有新节点加入，但经过一段时间后，这些节点的状态也会与其他节点达成一致，也就是说，gossip天然具有分布式容错的优点。

去中心化是网络技术发展的必然趋势。近些年p2p、无线ad-hoc等新型网络技术飞速发展,这些网络具有无中心、可扩展性好、节点高度自治等特点。但是无中心使得网络中的节点只有局部知识,无法进行全局控制;可扩展性使得网络规模8益庞大;节点自治使得网络高度动态,很难保证稳定性和鲁棒性;节点能力上的异构性,导致整个网络或者局部资源(计算、存储、通信)受限。gossip 算法简单高效,同时具有很好的可扩展性和鲁棒性,很好地适应了具有上述特点的网络环境。近些年在计算机领域,尤其是分布计算领域中涌现出了大量gossip相关的研究和应用。

2. 研究的基本内容与方案

设计的主要内容为用c/c 语言实现广播gossip算法的求和、求平均、求最大和最小等功能，分析其收敛性以及计算精确度，并与单播gossip进行比较。

在设计前期，了解gossip算法及其广播算法，学习分析此类算法的收敛性和收敛速度的方法，然后利用自己学习到的知识，完成一些求和、求平均、求最大和最小等功能小功能，分析gossip算法的收敛性并计算其精确度，最后与单播gossip算法进行比较，得出各自算法的优缺点，以及gossip算法还亟待研究的地方。

实现算法三个主要功能：1.在线节点不断广播“alive”消息来指示它们的可用性；2.在数据和其他节点不一致时，同步其他节点数据；3.在有新数据进入网络时，节点间通过不断的对随机相邻节点广播，最终达到数据一致性。

3. 研究计划与安排

2019/3/1-2019/3/10: 了解 gossip算法相关知识，阅读文献和相关书籍

2019/3/11-2019/3/31: 思考编程步骤，为实现gossip算法搭好框架

2019/4/1-2019/4/15: 编码，实现gossip算法

4. 参考文献（12篇以上）

[1] d. kempe, a. dobra, and j. gehrke. gossip-based computation of aggregate information, in proc. of the 44th annual ieee symposium on foundations of computer science (focs’03), 2003

[2] m. bawa, h. garcia-molina, a. gionis, and r. motwani. estimating aggregates ona peer-to-peer network. technical report, stanford university, 2003.

[3]基于gossip算法的分布式盲区检测[d].潘斯琦.哈尔滨工业大学 2016