3) WEB, TEXT, MULTIMEDIA etc. APPLICATIONS P010

Efficient Concurrency Control for Broadcast Environments

Jayavel Shanmugasundaram*       Arvind Nithrakashyap       Rajendran Sivasankaran
University of Wisconsin-Madison       Oracle Corporation       University of Massachusetts-Amherst
jai@cs.wisc.edu       anithrak@us.oracle.com       sivasank@cs.umass.edu

Krithi Ramamritham
University of Massachusetts-Amherst
krithi@cs.umass.edu

Abstract

A crucial limitation 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 approaches to meeting these requirements are too restrictive, unnecessary, and impractical. Hence weaker alternatives that are sufficient and practical for such environments are needed. We use a correctness criterion called update consistency that allows read-only transactions to read current and consistent data ``off the air'', i.e., without contacting the server to, say, obtain locks. Update transactions, however, need to validate their updates at the server. Even though update consistency is weaker than serializability, determining legality of histories with respect to this consistency requirement is NP-Complete. So, APPROX, a polynomial time algorithm, to efficiently detect (a subset of) legal histories is outlined. F-Matrix, a protocol to implement APPROX in broadcast disk environments, is then proposed. Our protocol requires additional control information to be broadcast with the data in order for a client to ensure the mutual consistency of data that it uses and so a key issue is how to minimize the overhead entailed by this additional information. To this end, we propose R-Matrix, a simpler version of F-Matrix, to implement APPROX. Experimental results confirm the hypothesis that update consistency would lead to substantially lower response times compared to using serializability, as exemplified by the concurrency control algorithm used in the Datacycle architecture. Furthermore, even though F-Matrix incurs higher overheads than R-Matrix, it leads to better response times and is also more scalable than R-Matrix and Datacycle.

* Contact Author.
address:
Jayavel Shanmugasundaram
Department of Computer Sciences
1210 West Dayton Street
University of Wisconsin-Madison
Madison, WI 53706

email: jai@cs.wisc.edu
phone: (608)-262-6624
fax: (608)-262-9777
web: http://www.cs.wisc.edu/~jai

This page was generated on Sun Oct 25 20:36:57 EST 1998