文 献 综 述

随着互联网的飞速发展，分布式计算的运用越来越多，面向商业运营的分布式系统也快速的走进人们的视野，随着用户的增长，分布式系统的体积越来越大，其复杂度和规模都呈指数级增长，但对于用户来说，高可靠性显得越来越重要，所以分布式系统的故障维护越来越难，在一些重要领域如银行，医疗等，对服务节点的可用性以及性能的要求更高，这就导致对故障节点监测服务的诞生。

1972年Hajnal等人首次给出了Gossip问题(电话问题)的描述：有”个妇女，每个人都知道一条特有的流言，她们通过电话互相联系；任意两个妇女联系上以后，互相交流当前 自己知道的所有流言；最少需要多少次联系．使得玎个妇女每 个人都知道所有流言?这使得对流言问题的研究正式登上历史舞台。

从上个世纪50年代到70年代，针对Gossip的研究层出 不穷，人们的研究主要集中在寻找一种合适的模型来很好地描述其运行机理，并对其进行分析；接下来的10年里，针对Gossip的研究热度有所减低；新型网络技术的飞速发展、复 杂网络相关研究的深入，则进一步推动了Gossip研究的发 展．近10年涌现出了大量关于Gossip的研究成果，并在分布 计算的众多子领域得到广泛应用，如数据库复制、故障探测、 P2P的拓扑构造及维护、分布环境下的聚合计算等。

我们用图对真实网络的结构进行抽象。这里的网络可以是计算机网络、传感器网络，也可以是由人通过不同联系方式组成的社会网络。一个网络可以表示为G=(V，E)，其中V 表示节点(网络成员)的结合；E为边，即节点之间的连接关系的集合。N#8212;|V|，指网络中节点的数目；A=a(ij)为G的邻接矩阵，假设是(0，1)矩阵。如果从节点到疗j存在边，且i≠j，有a(ij)=1，否则为0。如果G为无向图，则有a(ij)=a(jl) =1。如果a(ij)=l，我们称节点nj为ni的邻居节点。

时间模型是根据系统对时间的约束假设建立的模型，它 是Gossip算法的基础。不同的时间模型对Gossip算法的设 计和分析有着很大的影响。约束苛刻的时间模型，甚至使得 Gossip算法在分布环境下无法实施。目前主要有两类时间模 型：同步时间模型、异步时间模型。

同步时间模型将时间分为时隙，每个节点严格地在每个时隙与 自己的邻居节点进行信息交换。邻居节点的选择过程是随机 且独立的。该模型要求所有节点的信息交换过程在同一时刻发生，整个网络需要一个全局时钟来同步网络中所有节点的 时间。早期人们的研究都以同步模型为基础。

异步时问模型：每个节点都有自 己的时钟，并根据自己的时钟嘀嗒每隔△T发起信息交换，其 信息交换时刻是速率为1的泊松过程。所有节点信息交换的 时刻独立同分布。将网络中N个节点信息交换的时刻合成， 得到一个速率为N的泊松过程。。假设Gossip过程的开始时 刻为Zo，且Z(k 1)-Z(k)=△T，走k≥1，那么在[Z(k 1)-Z(k))时间段内,平均有n个信息交换的事件发生，称[Z(k 1)-Z(k))为该Gossip 过程的第k个周期.异步时间模型放松了对全局时钟同步的 要求，使得Gossip算法在分布式环境中的实现更加简单。

Gossip机制还在分布环境下的其它许多研究领域得到 广泛应用，如故障检测、网络监控、无线网络中的路由技术。 在众多的研究领域中，Gossip算法能够得到广泛的应用 是由于其高可扩展性、鲁棒性，以及简单的实现，而各种应用 之间的区别在于利用Gossip消息的内容不同、信息交换的目 的不同。总之，在大规模、动态、异构、通信受限的网络环境 中，基于Gossip算法解决相应的问题是一个很好的选择。