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

ABSTRACT

A crucial consideration in environments where data is broadcast to clients is the low bandwidth available for clients to communicate with servers. Advanced applications in such environments do need to read data that is mutually consistent as well as current. However, given the asymmetric communication capabilities and the needs of clients in mobile environments, traditional serializability-based approaches are too restrictive, unnecessary, and impractical. We thus propose the use of a weaker correctness criterion called update consistency and outline mechanisms based on this criterion that ensure (1) the mutual consistency of data maintained by the server and read by clients, and (2) the currency of data read by clients. Using these mechanisms, clients can obtain data that is current and mutually consistent “off the air”, i.e., without contacting the server to, say, obtain locks. Experimental results show a substantial reduction in response times as compared to existing (serializability-based) approaches. A further attractive feature of the approach is that if caching is possible at a client, weaker forms of currency can be obtained while still satisfying the mutual consistency of data.

REFERENCES

• Ach95: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• Ach96: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Disseminating Updates on Broadcast Disks, Proceedings of the 22th International Conference on Very Large Data Bases, p.354-365, September 03-06, 1996
• Alo90: Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990 [doi>10.1145/88636.87848]
• Ber87: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• Bob92: Paul M. Bober , Michael J. Carey, Multiversion Query Locking, Proceedings of the 18th International Conference on Very Large Data Bases, p.497-510, August 23-27, 1992
• Bob93: P.M. Bober and M.J. Carey. Multiversion Query Locking. Computer Science Technical Report TR 1160, University of Wisconsin-Madison, 1993.
• Car91: Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States
• Fra93: Michael Jay Franklin, Caching and memory management in client-server database systems, University of Wisconsin at Madison, Madison, WI, 1993
• Guk96: Sreenivas Gukal , Edward Omiecinski, Transient versioning for consistency and concurrency in client-server systems, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.274-287, December 18-20, 1996, Miami Beach, Florida, United States
• Her87: Gary Herman , K. C. Lee , Abel Weinrib, The datacycle architecture for very high throughput database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.97-103, May 27-29, 1987, San Francisco, California, United States
• Imi94: Tomasz Imielinski , B. R. Badrinath, Mobile wireless computing: challenges in data management, Communications of the ACM, v.37 n.10, p.18-28, Oct. 1994 [doi>10.1145/194313.194317]
• Kum97: Suresh Kumar , Eng-Kee Kwang , Divyakant Agrawal, Caprera: An Activity Framework for Transaction Processing on Wide-Area Networks, Proceedings of the 23rd International Conference on Very Large Data Bases, p.585-589, August 25-29, 1997
• Mol82: Hector Garcia-Molina , Gio Wiederhold, Read-only transactions in a distributed database, ACM Transactions on Database Systems (TODS), v.7 n.2, p.209-234, June 1982 [doi>10.1145/319702.319704]
• Oki93: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• Pap88: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• Pit99: Scalable Processing of Read-Only Transactions in Broadcast Push, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.432, May 31-June 04, 1999
• Ram96: Krithi Ramamritham , Panos K. Chrysanthis, A taxonomy of correctness criteria in database applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.085-097, January 1996 [doi>10.1007/s007780050017]
• Sha99: J. Shanmugasundaram, et. al. Efficiellt Concurrency Control for Broadcast Environmqmts Univ. of Massachusetts Technical Report 199g.
• She94: S. Shekar and D. Liu. Genesis and Advanced Traveler Information Systems (ATIS): Killer App}tications for Mobile Computing. MOBID.~.TA Workshop, New Jersey, 1994.
• Vit: White Paper, http://www.vitria.com.
• Wan91: Yongdong Wang , Lawrence A. Rowe, Cache consistency and concurrency control in a client/server DBMS architecture, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.367-376, May 29-31, 1991, Denver, Colorado, United States
• Wei87: William E. Weihl, Distributed version management for read-only actions, IEEE Transactions on Software Engineering, v.13 n.1, p.55-64, Jan. 1987 [doi>10.1109/TSE.1987.232835]
• Wil90: Kevin Wilkinson , Marie-Anne Neitmat, Maintaining consistency of client-cached data, Proceedings of the sixteenth international conference on Very large databases, p.122-134, September 1990, Brisbane, Australia
• Xua97: Ping Xuan , Subhabrata Sen , Oscar Gonzalez , Jesus Fernandez , Krithi Ramamritham, Broadcast on Demand: Efficient and Timely Dissemination of Data in Mobile Environments, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.38, June 09-11, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.7 Digital Libraries
          Subjects: Dissemination

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

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