Efficient concurrency control for broadcast environments

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

1. Ach95 S. Acharya, et. al. Broadcast Disks: Data Management for Asymmetric Communications Environments. Proceedings of the A CM SIGMOD Conference, California, May 1995.
2. Ach96 S. Achaxya, M. Franklin and S. Zdonik. Disseminating Updates on Broadcast Disks Proceedings of the VLDB Conference, Mumbai(Bombay), India, 1996.
3. Alo90 R. Alonso, D. Barbara and H. Garcia-Molina. Data Caching issues in an Information Retrieval System. A CM 7t~ansactions on Database Systems, 15(3), September 1!990.
4. Ber87 P. Bernstein, V. Hadzilacos and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Massachusetts, 1987.
5. Bob92 P.M. Bober and M.J. Carey. Multiversion Query Locking. Proceedings of the VLDB Conference, Vancouver, Canada, August 1992.
6. Bob93 P.M. Bober and M.J. Carey. Multiversion Query Locking. Computer Science Technical Report TR 1160, University of Wisconsin-Madison, 1993.
7. Car91 M.J. Carey, et. al. Data Caching Tradeoffs in Client-Server DBMS Architectures. Proceedings of the A CM SIGMOD Conference, Denver, June 1991.
8. Fra93 M.J. Franklin. Caching and Memory Management in Client-Server Database Systems. Ph.D. Thesis, University of Wisconsin-Madison, 1993.
9. Guk96 S. Gukal, E. Omiecinski and U. Ramachandran. Transient Versioning for Consistency and Concurrency in Client-Server Systems. Proceex!ings of the Conference on Parallel and Distributed l~formation Systems (PDIS), Florida, December 19~'6.
10. Her87 G. Herman, et. al. The Datacycle Archltecture for Very High Throughput Database Systenas Proceedings of the A CM SIGMOD Conference, 1987.
11. Imi94 T. Imielinski and B.R. Badrinath. Mobile Wireless Computing: Challenges in Data M~magement. Communications of the ACM, 37(10), 1994.
12. Kum97 S. Kumar, E. Kwang and D. Agrawal. Caprera: An Activity Framework for Transaction Processing on Wide-Area Networks Proceedings o} the ViSDB Conference, Athens, Greece, August 19.c17.
13. Mol82 H. Garcia-Molina and G. Wiederhohi. Read- Only Transactions in a Distributed Database. A CM 7~nsactions on Database Systems, 7(2), 1982.
14. Oki93 B. Oki, et. al. The Information Bus- An Architecture for Extensible Distributed Systems. Proceedings of the SOSP Conference, Nort}l Carolina, December 1993.
15. Pap88 C.H. Papadimitriou. The Theory of Database Concurrency Control. Computer Science Prq~ss, 1988.
16. Pit99 E. Pitoura and P. Chrysanthis, Scalable Processing of Read-Only Transactions in Broadcast Push, IEEE International Conference on Distributed Computing Systems, Austin, 1999
17. Ram96 K. Ramamritham and P. Chrysanthis. A Ta~onomy of Correctness Criteria in Databa~e Applications. VLDB Journal, 5(1), January 1996.
18. Sha99 J. Shanmugasundaram, et. al. Efficiellt Concurrency Control for Broadcast Environmqmts Univ. of Massachusetts Technical Report 199g.
19. 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.
20. Vit White Paper, http://www.vitria.com.
21. Wan91 W. Wang and L. Rowe. Cache Consi,~tency and Concurrency Control in a Client/Ser~,er DBMS Architecture. Proceedings of the A CM" SIGMOD Conference, June 1991.
22. Wei87 W. Weihl. Distributed Version Manal,~ement for Read-Only Actions. IEEE Transactior~s on Software Engineering, 13(1), January 1987.
23. Wil90 W. Wilkinson and M.A. Nemat. Iv{aintaining Consistency of Client Cached Data. JYroceedings of the VLDB Conference, Australia, Au,,ust 1990.
24. Xua97 P. Xuan, et. al. Broadcast on Demand- Efficient and Timely Dissemination of Data in Mobile Environments. IF, BE Real-Time Tech~wlogy and Applications Symposium, June 1997, pp 38-48.

Index Terms

• Applied computing

  • Computers in other domains

    • Digital libraries and archives

• Computing methodologies

  • Modeling and simulation

• Hardware

  • Communication hardware, interfaces and storage

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

      • Database transaction processing

  • Information systems applications

    • Digital libraries and archives

• Networks

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)