Multiversion divergence control of time fuzziness

ABSTRACT

Epsilon Serializability (ESR) has been proposed to manage and control inconsistency in extending the classic transaction processing. ESR increases system concurrency by tolerating a bounded amount of inconsistency. In this paper, we present multiversion divergence control (mvDC) algorithms that support ESR with not only value but also time fuzziness in multiversion databases. Unlike value fuzziness, accumulating time fuzziness is semantically different. A simple summation of the length of two time intervals may either underestimate the total time fuzziness, resulting in incorrect execution, or overestimate the total time fuzziness, unnecessarily degrading the effectiveness of mvESR. We present a new operation, called TimeUnion, to accurately accumulate the total time fuzziness. Because of the accurate control of time and value fuzziness by the mvDC algorithm, mvESR is very suitable for the use of multiversion databases for real-time applications that may tolerate a limited degree of data inconsistency but prefer more data recency.

REFERENCES

• 1: D. Agrawal , S. Sengupta, Modular synchronization in multiversion databases: version control and concurrency control, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.408-417, June 1989, Portland, Oregon, United States
• 2: Philip A. Bernstein , Nathan Goodman, Multiversion concurrency control—theory and algorithms, ACM Transactions on Database Systems (TODS), v.8 n.4, p.465-483, Dec. 1983 [doi>10.1145/319996.319998]
• 3: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 4: Paul M. Bober , Michael J. Carey, On Mixing Queries and Transactions via Multiversion Locking, Proceedings of the Eighth International Conference on Data Engineering, p.535-545, February 03-07, 1992
• 5: Michael J. Carey , Waleed A. Muhanna, The performance of multiversion concurrency control algorithms, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.338-378, Nov. 1986 [doi>10.1145/6513.6517]
• 6: A. Chan and R. Gray. Implementing distributed readonly transactions. IEEE Trans. on Software Engineering, SE-11(2):205-212, Feb. 1985.
• 7: T.-W. Kuo and A. K. Mok. Apphcation semantics and concurrency control of real-time data-intensive apphcations. In Proc. of Real- Time Systems Symposium, pages 35-45, 1992.
• 8: Arif Merchant , Kun-Lung Wu , Philip S. Yu , Ming-Syan Chen, Performance analysis of dynamic finite versioning for concurrent transaction and query processing, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.103-114, June 01-05, 1992, Newport, Rhode Island, United States
• 9: C. Mohan , Hamid Pirahesh , Raymond Lorie, Efficient and flexible methods for transient versioning of records to avoid locking by read-only transactions, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.124-133, June 02-05, 1992, San Diego, California, United States
• 10: C. Pu, W. Hseush, G. E. Kaiser, K.-L. Wu, and P. S. Yu. Distributed divergence control for epsilon serializability. In Proc. of Int. Conf. on Distributed Computing Systems, pages 449-456, 1993.
• 11: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.377-386, May 29-31, 1991, Denver, Colorado, United States
• 12: K. Ramamrithan and C. Pu. A formal characterization of epsflon-serializabihty. Technical Report CUCS-044- 91, Department of Computer Science, Columbia University, Dec. 1991.
• 13: David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983 [doi>10.1145/357353.357355]
• 14: S. H. Son and S. Kouloumbis. Rephcation control for distributed real-time database systems. In Proc. of Int. Conf. on Distributed Computing Systems, pages 144- 151, 1992.
• 15: 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]
• 16: Kun-Lung Wu , Philip S. Yu , Ming-Syan Chen, Dynamic Finite Versioning: An Effective Versioning Approach to Concurrent Transaction and Query Processing, Proceedings of the Ninth International Conference on Data Engineering, p.577-586, April 19-23, 1993
• 17: Kun-Lung Wu , Philip S. Yu , Calton Pu, Divergence Control for Epsilon-Serializability, Proceedings of the Eighth International Conference on Data Engineering, p.506-515, February 03-07, 1992

INDEX TERMS

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

General Terms:
Algorithms, Theory, Verification