Correctness of a gossip based membership protocol
Correctness of a gossip based membership protocol
复制标题
基于八卦的成员协议的正确性
DOI：
10.1145/1073814.1073871
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
J. Hopcroft
中科院分区：
文献类型：
--
作者：
A. Allavena;A. Demers;J. Hopcroft
可扩展性和容错性在现代分布式系统中的重要性，导致了大量的研究，在组播协议使用的流言。在流言协议中，每个节点将消息转发给从整个组成员中随机选择的一小组“流言伙伴”。通过放弃传统协议的强可靠性保证，支持概率保证，gossip协议可以提供更大的可扩展性和容错性。在早期的gossip算法中，合作伙伴是从整个成员中随机选择的，由于在每个节点上存储和维护完整的成员关系视图所需的资源，限制了可扩展性。后来的协议通过在每个节点上存储更小的随机成员子集来避免这个问题，并且只从这些本地视图中选择流言伙伴。这样的协议是微妙的：至少一些本地视图必须响应组成员身份的更改而更改，以便保留连接性和性能保证。虽然这些协议一直是大量模拟和分析的主题，但关键属性的正式证明-特别是分区的概率-仍然难以捉摸。在本文中，我们给出了一个新的可扩展的基于流言的局部视图维护算法，连同证明，直到网络分区的预期时间至少是指数的平方视图大小。我们还开发了概率界限的程度（因此负载）的个别节点，并认为，协议缺乏我们的加固组件最终收敛到星形网络，其连接依赖于一个小的超载节点。我们还认为，无向连接图是一个扩展器，应用程序级的八卦组播协议将迅速收敛。我们的理论结果支持模拟。
The importance of scalability and fault-tolerance in modern distributed systems has led to considerable research in multicast protocols using gossip. In a gossip protocol, each node forwards messages to a small set of “gossip partners” chosen at random from the entire group membership. By discarding the strong reliability guarantees of traditional protocols in favour of probabilistic guarantees, gossip protocols can deliver greater scalability and fault tolerance. In early gossip algorithms, partners were chosen uniformly at random from the entire membership, limiting scalability because of the resources required to store and maintain complete membership views at each node. Later protocols avoided this issue by storing much smaller random subsets of the membership at each node, and choosing gossip partners only from these local views. Such protocols are subtle: at least some local views must change in response to group membership changes in order to preserve connectivity and performance guarantees. While these protocols have been the subject of much simulation and analysis, formal proofs of key properties – in particular the probability of partitioning – have remained elusive. In this paper we give a new scalable gossip-based algorithm for local view maintenance, together with a proof that the expected time until a network partition is at least exponential in the square of the view size. We also develop probabilistic bounds on the in-degree (hence the load) of individual nodes, and argue that protocols lacking our reinforcement component eventually converge to star-like networks, whose connectivity depends on a small set of overloaded nodes. We also argue that the undirected connectivity graph is an expander, for which application-level gossip multi-cast protocols will converge rapidly. Our theoretical results are supported by simulations.