Lightweight probabilistic broadcast

ABSTRACT

Gossip-based broadcast algorithms, a family of probabilistic broadcast algorithms, trade reliability guarantees against "scalability" properties. Scalability in this context has usually been expressed in terms of message throughput and delivery latency, but there has been little work on how to reduce the memory consumption for membership management and message buffering at large scale.This paper presents lightweight probabilistic broadcast (lpbcast), a novel gossip-based broadcast algorithm, which complements the inherent throughput scalability of traditional probabilistic broadcast algorithms with a scalable memory management technique. Our algorithm is completely decentralized and based only on local information: in particular, every process only knows a fixed subset of processes in the system and only buffers fixed "most suitable" subsets of messages. We analyze our broadcast algorithm stochastically and compare the analytical results both with simulations and concrete implementation measurements.

REFERENCES

• 1: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 2: Bailey, N. 1975. The Mathematical Theory of Infectious Diseases and its Applications (second edition). Hafner Press.
• 3: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 4: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Achieving scalability and expressiveness in an Internet-scale event notification service, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.219-227, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343622]
• 5: Deering, S. 1994. Internet multicasting. In ARPA HPCC 94 Symposium. Advanced Research Projects Agency Computing Systems Technology Office.
• 6: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 7: Eugster, P. T., Felber, P., Guerraoui, R., and Kermarrec, A.-M. 2001a. The many faces of publish/subscribe. Tech. Rep. DSC/2001/004, Swiss Federal Institute of Technology, Lausanne, http://dscwww.epfl.ch/EN/publications/.
• 8: Patrick Th. Eugster , Rachid Guerraoui , Joe Sventek, Distributed Asynchronous Collections: Abstractions for Publish/Subscribe Interaction, Proceedings of the 14th European Conference on Object-Oriented Programming, p.252-276, June 12-16, 2000
• 9: Patrick Th. Eugster , Rachid Guerraoui , S. B. Handurukande , Petr Kouznetsov , Anne-Marie Kermarrec, Lightweight Probabilistic Broadcast, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.443-452, July 01-04, 2001
• 10: Eugster, P. T., Guerraoui, R., Kermarrec, A.-M., and Massoulie, L. 2003. From epidemics to distributed computing. IEEE Comput.
• 11: Golding, R. 1992. Weak consistency group communication for wide-area systems. In Proceedings of the Second Workshop on the Management of Replicated Data.
• 12: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 13: Anne-Marie Kermarrec , Laurent Massoulié , Ayalvadi J. Ganesh, Probabilistic Reliable Dissemination in Large-Scale Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.248-258, March 2003 [doi>10.1109/TPDS.2003.1189583]
• 14: Kouznetsov, P., Guerraoui, R., Handurukande, S. B., and Kermarrec, A.-M. 2001. Reducing noise in gossip-based reliable broadcast. In Proceedings of the IEEE Symposium on Reliable Distributed Systems (SRDS 2001).
• 15: Meng-Jang Lin , Keith Marzullo, Directional Gossip: Gossip in a Wide Area Network, Proceedings of the Third European Dependable Computing Conference on Dependable Computing, p.364-379, September 15-17, 1999
• 16: Meng-Jang Lin , Keith Marzullo , Stefano Masini, Gossip versus Deterministically Constrained Flooding on Small Networks, Proceedings of the 14th International Conference on Distributed Computing, p.253-267, October 04-06, 2000
• 17: José Pereira , Rui Oliveira , Luís Rodrigues, Semantically Reliable Multicast Protocols, Proceedings of the 19th IEEE Symposium on Reliable Distributed Systems (SRDS'00), p.60, October 16-18, 2000
• 18: Paul, S., Sabnani, K., Lin, J., and Bhattacharyya, S. 1997. Reliable multicast transport protocol (RMTP). IEEE J. Selected Areas Comm. 15, 3 (Apr.), 407--421.
• 19: Rico Piantoni , Constantin Stancescu, Implementing the Swiss Exchange Trading System, Proceedings of the 27th International Symposium on Fault-Tolerant Computing (FTCS '97), p.309, June 25-27, 1997
• 20: Rodrigues, L., Handurukande, S., Pereira, J., Guerraoui, R., and Kermarrec, A.-M. 2003. Adaptive gossip-based broadcast. In Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN 2003).
• 21: Qixiang Sun , Daniel C. Sturman, A Gossip-Based Reliable Multicast for Large-Scale High-Throughput Applications, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.347, June 25-28, 2000
• 22: TIBCO. 1999. TIB/Rendezvous White Paper. http://www.rv.tibco.com/.
• 23: Robbert Van Renesse, Scalable and Secure Resource Location, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 4, p.4012, January 04-07, 2000
• 24: Xiao, Z. and Birman, K. 2001. Randomized error recovery algorithm for reliable multicast. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM).
• 25: Zhen Xiao , Kenneth P. Birman , Robbert van Renesse, Optimizing Buffer Management for Reliable Multicast, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.187-198, June 23-26, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Design, Measurement, Performance, Reliability

Keywords:
Broadcast, buffering, garbage collection, gossip, noise, randomization, reliability, scalability