Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a design of a distributed publish-subscribe system that extends the functionality of messaging middleware with "relational subscriptions", to support timely updates to state derived from published messages while preserving high throughput, scalability, and reliability.Critical to our design is our service guarantee of "eventual correctness". Eventual correctness is a weaker guarantee than the ACID properties of conventional databases, yet is useful enough to deliver state that is "just consistent enough".A key component of our design is a monotonic type system. All states delivered to clients represent facts that are permanently true, that may be refined by future updates, but will never become false. The monotonic type system is used both to formalize eventual correctness, and as a basis for our implementation, which generalizes the "Guaranteed Delivery" protocol previously implemented in the Gryphon system.We discuss: (1) our monotonic type system and relational subscription language; (2) eventual correctness; (3) the architecture of our implementation; (4) potential optimizations that form a basis for future studies.

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: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 3: An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.262, May 31-June 04, 1999
• 4: 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
• 5: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 6: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 7: Carney, D., Çetintemel, U., Cherniack, M., Convey, C., Lee, S., Seidman, G., Stonebraker, M., Tatbul, N., Zdonik, S. B.: Monitoring Streams - A New Class of Data Management Applications. VLDB 2002.
• 8: Chandrasekaran, S., and Franklin, M., Streaming Queries over Streaming Data, In Proc. of the 28th VLDB Conference, Hong Kong, China, 2002.
• 9: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 10: Cherniack, M., Balakrishnan, H., Balazinska, M., Carney, D., Cetintemel, U., Xing, Y., and Zdonik, S. Scalable Distributed Stream Processing. In Proc. of the 1st Biennial Conference on Inovative Data Systems Research (CIDR 2003), Jan 2003, Asilomar, CA.
• 11: C. J. Date , Hugh Darwen, Foundation for object/relational databases: the third manifesto, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 12: 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
• 13: H. V. Jagadish , Inderpal Singh Mumick , Abraham Silberschatz, View maintenance issues for the chronicle data model (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.113-124, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220201]
• 14: Ling Liu , Calton Pu , Wei Tang, Continual Queries for Internet Scale Event-Driven Information Delivery, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.610-628, July 1999 [doi>10.1109/69.790816]
• 15: Motwani, R., Widom, J., Arasu, A., Babcock, B., Babu, S., Datar, M., Manku, G., Olston, C., Rosenstein, J., and Varma, R.: Query Processing, Approximation, and Resource Management in a Data Stream Management System. In Proc. of the 1st Biennial Conference on Innovative Data Systems Research (CIDR 2003), Jan 2003, Asilomar, CA.
• 16: Madden, S., and Franklin, M. Fjording the stream: An architecture for queries over streaming sensor data. ICDE. San Jose, CA, February 2002.
• 17: Samuel Madden , Robert Szewczyk , Michael J. Franklin , David Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.49, June 20-21, 2002
• 18: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 19: Strom R., Extending a Content-Based Publish-Subscribe System with Relational Subscriptions, IBM Technical Report. At <u>http://www.research.ibm.com/gryphon</u>
• 20: Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States
• 21: Yao, Y., and Gehrke, J. Query Processing in Sensor Networks. In Proc. of the 1st Biennial Conference on Innovative Data Systems Research (CIDR 2003), Jan 2003, Asilomar, CA.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Design, Languages, Reliability

Keywords:
continuous queries, event distribution systems, monotonicity, relational subscriptions