Correctness of Gossip-Based Membership under Message Loss

Authors:
  • MGMaxim Gurevich
    Maxim Gurevich
  • IKIdit Keidar
    Idit Keidar
Publisher website
Google Scholar
Abstract
Due to their simplicity and effectiveness, gossip-based membership protocols have become the method of choice for maintaining partial membership in large peer-to-peer systems. A variety of gossip-based membership protocols were proposed. Some were shown to be effective empirically, lacking analytic understanding of their properties. Others were analyzed under simplifying assumptions, such as lossless and delayless network. It is not clear whether the analysis results hold in dynamic networks, where both nodes and network links can fail. In this paper we try to bridge this gap. We first enumerate the desirable properties of a gossip-based membership protocol, such as view uniformity, independence, and load balance. We then propose a simple send & forget protocol, and show that even in the presence of message loss, it achieves the desirable properties.

This publication has 29 references indexed in Scilit: