Probabilistic Reliable Dissemination in Large-Scale Systems
Probabilistic Reliable Dissemination in Large-Scale Systems
复制标题
DOI：
10.1109/tpds.2003.1189583
复制
发表时间：
2003-03
期刊：
影响因子：
--
通讯作者：
Anne-Marie Kermarrec;L. Massoulié;A. Ganesh
中科院分区：
文献类型：
--
作者：
Anne-Marie Kermarrec;L. Massoulié;A. Ganesh
Internet的发展为分布式系统和应用程序的设计提出了新的挑战。在组通信协议的上下文中，基于八卦的方案吸引了人们的兴趣，因为它们具有可伸缩性、易于部署以及对网络和流程故障具有弹性。然而，传统的基于八卦的协议有两个主要缺点：1)它们依赖于每个节点都知道全球成员；2)与网络拓扑无关，当应用于广域设置时，它们可以对网络链路施加高负载。在本文中，我们对基于八卦的协议进行了理论分析，将其可靠性与关键系统参数（系统大小，故障率和八卦目标数量）联系起来。研究结果为实际方案的设计提供了指导。特别是，它们展示了如何在保持可靠性的同时通过以下方式减轻缺点：1)仅向每个对等体提供全部成员信息和缺点的一小部分；2)根据与网络相关的度量标准，将成员组织成反映其接近程度的层次结构。我们通过模拟验证了分析结果，并验证了与原始的非分层协议相比，分层八卦协议大大减少了网络上的负载。
The growth of the Internet raises new challenges for the design of distributed systems and applications. In the context of group communication protocols, gossip-based schemes have attracted interest as they are scalable, easy to deploy, and resilient to network and process failures. However, traditional gossip-based protocols have two major drawbacks: 1) they rely on each peer having knowledge of the global membership; and 2) being oblivious to the network topology, they can impose a high load on network links when applied to wide-area settings. In this paper, we provide a theoretical analysis of gossip-based protocols which relates their reliability to key system parameters (the system size, failure rates, and number of gossip targets). The results provide guidelines for the design of practical protocols. In particular, they show how reliability can be maintained while alleviating drawback by: 1) providing each peer with only a small subset of the total membership information and drawback; and 2) organizing members into a hierarchical structure that reflects their proximity according to some network-related metric. We validate the analytical results by simulations and verify that the hierarchical gossip protocol considerably reduces the load on the network compared to the original, non-hierarchical protocol.