Probabilistic Semantically Reliable Multicast

J. Pereira, L. Rodrigues, R. Oliveira, A.-M. Kermarrec

An extended abstract of this report was published as a short paper in the Proceedings of the IEEE International Symposium on Network Computing and Applications, October, 8-10, 2001 Royal Sonesta Hotel Cambridge, MA, USA.


Traditional broadcast protocols fail to scale to large settings. Several recent attempts have proven efficient to ensure reliable information dissemination in groups composed of a large number of participants. This paper proposes a reliable multicast protocol that integrates two complementary approaches to deal with the large-scale dimension in group communication protocols: gossip-based probabilistic and semantic-based protocols.

Although it seems intuitive that the combination of probabilistic and semantic reliable protocols should provide good results, we show that a naive composition of both protocols offers disapointing results. We then propose a specialized probabilistic semantically reliable layer, evaluate different implementation policies and study the impact of relevant system parameters in the performance of the protocol.

Our approach allows us to identify which protocol configuration provides the best results, combining the advantages of both models in a single primitive that: i) is scalable to large number of participants and highly resilient to network and process failures and; (ii) delivers a high quality data flow even when the load exceeds the available bandwidth.

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

Luís Rodrigues