Peer-to-peer membership management for gossip-based protocols

被引:194
作者
Ganesh, AJ [1 ]
Kermarrec, AM [1 ]
Massoulié, L [1 ]
机构
[1] Microsoft Res, Cambridge CB3 0FB, England
关键词
scalability; reliability; peer-to-peer; gossip-based probabilistic multicast; membership; group communication; random graphs;
D O I
10.1109/TC.2003.1176982
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Gossip-based protocols for group communication have attractive scalability and reliability properties. The probabilistic gossip schemes studied so far typically assume that each group member has full knowledge of the global membership and chooses gossip targets uniformly at random. The requirement of global knowledge impairs their applicability to very large-scale groups. In this paper, we present SCAMP (Scalable Membership protocol), a novel peer-to-peer membership protocol which operates in a fully decentralized manner and provides each member with a partial view of the group membership. Our protocol is self-organizing in the sense that the size of partial views naturally converges to the value required to support a gossip algorithm reliably. This value is a function of the group size, but is achieved without any node knowing the group size. We propose additional mechanisms to achieve balanced view sizes even with highly unbalanced subscription patterns. We present the design, theoretical analysis, and a detailed evaluation of the basic protocol and its refinements. Simulation results show that the reliability guarantees provided by SCAMP are comparable to previous schemes based on global knowledge. The scale of the experiments attests to the scalability of the protocol.
引用
收藏
页码:139 / 149
页数:11
相关论文
共 27 条
  • [1] ANKER T, 1998, NETWORKS DISTRIBUTIN, P23
  • [2] [Anonymous], P IEEE INT C DEP SYS
  • [3] POISSON APPROXIMATION FOR SOME EPIDEMIC MODELS
    BALL, F
    BARBOUR, AD
    [J]. JOURNAL OF APPLIED PROBABILITY, 1990, 27 (03) : 479 - 490
  • [4] THE PROCESS GROUP-APPROACH TO RELIABLE DISTRIBUTED COMPUTING
    BIRMAN, KP
    [J]. COMMUNICATIONS OF THE ACM, 1993, 36 (12) : 37 - &
  • [5] Bimodal multicast
    Birman, KP
    Hayden, M
    Ozkasap, O
    Xiao, Z
    Budiu, M
    Minsky, Y
    [J]. ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1999, 17 (02): : 41 - 88
  • [6] CABRERA LF, 2001, P HOTOS MAY, V8
  • [7] CASTRO M, 2002, IN PRESS IEEE J SELE
  • [8] CSISZAR I, 1997, INFORMATION THEORETI
  • [9] DEERING S, 1996, IEEE ACM T NETWORKIN, V4
  • [10] Deering S. E., 1990, ACM T COMPUTER SYSTE, V8