Subject space: a state-persistent model for publish/subscribe systems

ABSTRACT

Many conventional models of publish/subscribe systems have limitations. Some models lack the flexibility for expressive subscription semantics, and others exhibit undesirable behaviors under certain situations. This paper introduces the subject space model, a new model for publish/subscribe systems. The major difference between this model and existing ones is that it persists the states of both publications and subscriptions in the system and notifies subscribers only when the states of their subscriptions change from false to true. A novel indexing technique is described for indexing the positions of objects and subscriptions in subject spaces, so that their state information can be retrieved and evaluated very quickly. The performance of the indexing technique is demonstrated in a prototype of a subject space publish/subscribe kernel.

REFERENCES

• 1: {1} A. Carzaniga. Architectures for an Event Notification Service Scalable to Wide-area net-works, PhD thesis, Politecnico di Milano, Milano, Italy, December, 1998.
• 2: {2} D. B. Skillicorn. Structured Parallel Computation in Structured Documents, Journal of Universal Computer Science, Vol.3, No.1, January 1997.
• 3: David Powell, Group communication, Communications of the ACM, v.39 n.4, p.50-53, April 1996 [doi>10.1145/227210.227225]
• 4: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 5: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 6: 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]
• 7: 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
• 8: {8} Patrick Th. Eugster, Rachid Guerraoui and Joe Sventek. Type-Based Publish/Subscribe, June 2000.
• 9: Prosenjit Gupta , Ravi Janardan , Michiel Smid, Further results on generalized intersection searching problems: counting, reporting, and dynamization, Journal of Algorithms, v.19 n.2, p.282-317, Sept. 1995 [doi>10.1006/jagm.1995.1038]
• 10: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 11: {11} TIBCO Inc. TIB/Rendezvous White Paper, http://www.rv.tibco.com/whitepaper.html
• 12: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services; Commercial services

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory