Introducing reliability in content-based publish-subscribe through epidemic algorithms

ABSTRACT

Distributed content-based publish-subscribe middleware provides the necessary decoupling, flexibility, expressiveness, and scalability required by modern distributed applications. Unfortunately, this middleware usually does not provide reliability, especially in the presence of highly reconfigurable scenarios. Indeed, this problem has been thus far largely disregarded by the research community and solutions developed in other contexts are not immediately applicable.In this paper, we tackle the problem of introducing reliability in content-based publish-subscribe in dynamic environments by exploiting epidemic algorithms, whose characteristics in terms of decentralization, scalability, and resilience to topological changes resonate with our problem.

REFERENCES

• 1: Sumeer Bhola , Robert E. Strom , Saurabh Bagchi , Yuanyuan Zhao , Joshua S. Auerbach, Exactly-once Delivery in a Content-based Publish-Subscribe System, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.7-16, June 23-26, 2002
• 2: 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]
• 3: Luis Felipe Cabrera , Michael B. Jones , Marvin Theimer, Herald: Achieving a Global Event Notification Service, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.87, May 20-22, 2001
• 4: Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 5: M. Castro, P. Druschel, A. Kermarrec, and A. Rowstron. Scribe: A large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in Communications, 20(8), 2002.
• 6: Anonymous Gossip: Improving Multicast Reliability in Mobile Ad-Hoc Networks, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.275, April 16-19, 2001
• 7: Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001 [doi>10.1145/503112.503113]
• 8: P. Costa, M. Migliavacca, G. P. Picco, and G. Cugola. Epidemic Algorithms for Reliable Content-Based Publish-Subscribe. Technical report, Politecnico di Milano, March 2003. Available at www.elet.polimi.it/~picco.
• 9: F. M. Cuenca-Acuna, C. Peery, R. P. Martin, and T. D. Nguyen. PlanetP: Infrastructure support for P2P information sharing. Technical Report DCS-TR-465, Rutgers University, November 2001.
• 10: Gianpaolo Cugola , Elisabetta Di Nitto , Alfonso Fuggetta, The JEDI Event-Based Infrastructure and Its Application to the Development of the OPSS WFMS, IEEE Transactions on Software Engineering, v.27 n.9, p.827-850, September 2001 [doi>10.1109/32.950318]
• 11: G. Cugola, G. P. Picco, and A. L. Murphy. Towards distributed publish-subscribe middleware for mobile systems. In Proc. of the 3rd Int. Workshop on Software Engineering and Middleware, LNCS 2596. Springer, May 2002.
• 12: Alan Demers , Dan Greene , Carl Houser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, ACM SIGOPS Operating Systems Review, v.22 n.1, p.8-32, Jan., 1988 [doi>10.1145/43921.43922]
• 13: C. Diot, W. Dabbous, and J. Crowcroft. Group communication. IEEE Journal on Selected Areas in Communication, May 1997.
• 14: 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
• 15: P. Eugster and R. Guerraoui. Hierarchical probabilistic multicast. Technical report, EPFL, Lausanne (Switzerland), 2001. Available at icwww.epfl.ch/publications.
• 16: Brian Neil Levine , J. J. Garcia-Luna-Aceves, A Comparison of Known Classes of Reliable Multicast Protocols, Proceedings of the 1996 International Conference on Network Protocols (ICNP '96), p.112, October 29-November 01, 1996
• 17: 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
• 18: J. Luo, P. Eugster, and J.-P. Hubaux. Route Driven Gossip: Probabilistic Reliable Multicast in Ad Hoc Networking. Technical report, EPFL, Lausanne (Switzerland), 2002. Available at icwww.epfl.ch/publications.
• 19: K. Obraczka. Multicast transport protocols: a survey and taxonomy. IEEE Communications, 36(1):94--102, January 1998.
• 20: Gian Pietro Picco , Gianpaolo Cugola , Amy L. Murphy, Efficient Content-Based Event Dispatching in the Presence of Topological Reconfiguration, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.234, May 19-22, 2003
• 21: Peter R. Pietzuch , Jean Bacon, Hermes: A Distributed Event-Based Middleware Architecture, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.611-618, July 02-05, 2002
• 22: Peter R. Pietzuch , Jean Bacon, Hermes: A Distributed Event-Based Middleware Architecture, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.611-618, July 02-05, 2002
• 23: Real-Time Innovations, Inc. NDDS: Network Middleware for Distributed Real Time Applications. www.rti.com.
• 24: V. Roca, L. Costa, R. Vida, A. Dracinschi, and S. Fdida. A survey of multicast technologies. Technical report, Laboratoire d'Informatique de Paris 6 (LIP6), September 2000. www-rp.lip6.fr.
• 25: David S. Rosenblum , Alexander L. Wolf, A design framework for Internet-scale event observation and notification, Proceedings of the 6th European conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, p.344-360, September 22-25, 1997, Zurich, Switzerland
• 26: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 27: R. Strom, G. Banavar, T. Chandra, M. Kaplan, K. Miller, B. Mukherjee, D. Sturman, and M. Ward. Gryphon: An information flow based approach to message brokering. In Int. Symp. on Software Reliability Engineering, 1998.
• 28: Sun Microsystems, Inc. Java Message Service Specification Version 1.1, April 2002.
• 29: Peter Sutton , Rhys Arkins , Bill Segall, Supporting Disconnectedness-Transparent Information Delivery for Mobile and Invisible Computing, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.277, May 15-18, 2001
• 30: TIBCO Inc. TIBCO Rendezvous. www.rv.tibco.com.
• 31: Shelley Q. Zhuang , Ben Y. Zhao , Anthony D. Joseph , Randy H. Katz , John D. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.11-20, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378347]