View article

Gossip-based protocols have received considerable attention for broadcast applications due to their attractive scalability and reliability properties. The reliability of probabilistic gossip schemes studied so far depends on each user having knowledge of the global membership and choosing gossip targets uniformly at random. The requirement of global knowledge is undesirable in large-scale distributed systems.

In this paper, we present a novel peer-to-peer membership service which operates in a completely decentralized manner in that nobody has global knowledge of membership. However, membership information is replicated robustly enough to support gossip with high reliability. Our scheme is completely self-organizing in the sense that the size of local views naturally converges to the ‘right’ value for gossip to succeed. This ‘right’ value is a function of system size, but is achieved without any …