Adaptive Gossip-Based Broadcast.

L. Rodrigues, S. Handurukande, J. Pereira, R. Guerraoui, A.-M. Kermarrec.

Selected sections of this report were published in the Proceedings of the International Conference on Dependable Systems and Networks (DSN), pp. 47-56, San Francisco, California, USA, June, 2003.

Abstract

Gossip-based broadcast algorithms, also called ``probabilistic'' or ``epidemic'' broadcast algorithms, do have inherent scalability properties and are hence extremely appealing in a large scale setting. Information is disseminated reliably provided that every node has enough buffering resources to store and forward messages for sufficiently long. Very little research has been devoted to gossip-based broadcast with a limited amount of resources at every node.

This paper presents a novel adaptation mechanism that allows every node of a gossip-based broadcast algorithm to adjust the rate of message transmission and forwarding to the amount of resources available to the nodes within the same broadcast group. The mechanism scales very well since the dissemination of the feedback control information that enables adaptation is embedded in the gossip-based data flow. It permits gossip-based broadcast algorithms to be applied to situations where nodes have limited resources whose quantity changes dynamically with time without decreasing the reliability.

This feature is motivated in a practical situation where a large number of nodes are involved in a publish-subscribe interaction with a realistic heterogeneity of subscription interest.

Also available extended report(gzip postscript), (pdf)


Luís Rodrigues