在过去的十年中，我们看到计算机之间的连通性发生了革命，并导致了从集中式计算到高度分布式系统的转变。例如，具有数百万台服务器的大规模对等（P2P）网络正在被用于或被设计用于分布式信息存储和检索，并且硬件的进步正在导致我们的物理环境中传感器网络的规模增加到由数十万个小型传感器节点组成。这种大规模分布式系统的应用程序具有两个个突出的特性，可以将它们与传统的集中式或小型分布式系统区分开来。

首先，大规模分布式系统的动态往往明显不同。例如，在P2P网络中，大量机器通常处于可随时加入或离开网络的状态中（如用户电脑关机）。传感器网络通常也会涉及部署在不稳定的环境中（例如战场），容易使得传感器故障。因此，整个系统必须具有高度容错性，因为节点和链路故障或临时通信中断是常态而非例外。

第二，由于系统规模庞大，整个网络（或其中很大一部分的节点）的数据集合函数的值通常比单个节点上的数据更重要。例如，在具有温度传感器的传感器网络中，我们通常对一个区域中的所有传感器测量的平均或中值温度更感兴趣，而不是单个传感器上的单个测量；在P2P系统中，我们可能对文件的总数，存储的文件的平均大小，或有关机器磁盘上可用空间量的分位数感兴趣。同时，通信带宽通常是限制节点间数据交流的重要障碍，因此计算聚合应该只涉及小型信息的交换。特别是，在一个给定节点上收集所有节点数据的任何协议都会在该节点上产生通信瓶颈或消息爆炸。

基于这两个特性，在大规模分布式网络中，我们需要研究一款能够在容错率可以接受范围内，并且能够在适度的开销中，以指数级快速收敛完成预期函数计算的算法，即Gossip算法。在基于Gossip的协议中，每个节点在每一轮联系一个或几个节点（通常随机选择），并与这些节点交换信息。信息传播的动态与传染病的传播相似，并导致高度的容错和“自我稳定”。基于流言的协议通常不需要错误恢复机制，因此在简单性方面享有很大的优势，而与最佳确定性协议（如数据传播树的构建）相比，通常只会产生适度的开销。从流言中获得的保证通常是概率性的，相比之下，传统技术具有绝对的保证，但即使在适度的破坏时也不稳定或无法取得进展。

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

① 1 基本内容：

利用Gossip算法计算类P2P网络上全部或部分节点的可共享文件数量的总和、平均、最大和最小数目,分析算法的收敛性和收敛速度。

② 2 预期目标：

在误差允许范围内，在指数级收敛中，完成对类P2P网络上预设节点上的的可共享文件数量的总和、平均、最大和最小的计算,并在NS网络仿真软件中模拟计算过程。

③ 3 拟采用的技术方案及措施：

首先研究Gossip算法，Gossip是一个带冗余的容错算法，更进一步，Gossip是一个最终一致性算法。虽然无法保证在某个时刻所有节点状态一致，但可以保证在“最终”所有节点一致，“最终”是一个现实中存在，但理论上无法证明的时间点。在本次研究内容中，我们利用NS网络仿真软件预设一个类P2P网络，在每个节点设置一个数值来表示此节点可共享的文件数量，然后在一个节点发出计算命令，利用pull/push方式和异步单播的原理唤醒邻居节点，假设每个节点通信周期都能选择（感染）一个新节点，则Gossip算法退化为一个二分查找过程，每个周期构成一个平衡二叉树，收敛速度为O(n² )，对应的时间开销则为O(logshy;_n )。这也是Gossip理论上最优的收敛速度。