Token transactions: managing fine-grained migration of data

ABSTRACT

Executing a transaction in a conventional distributed database system involves the execution of several subtransactions, each at a remote site where the data reside and running a two-phase commit protocol at the end of the transaction. With the advent of fast communication networks, we consider an alternative paradigm where the remote data being accessed are dynamically migrated to the initiation site of the transaction. One example of such a system is a distributed shared virtual memory system. In this paper, we examine the problem of recovery from system failure in data migration systems. Most data migration systems use the notion of tokens for the access rights a site has on the data elements it caches. Our goal is to recover the site's knowledge of the set of tokens it owned when a system failure occurred. Our approach is to consider the token knowledge at each site as a fragment of a global token database and the data migration activities as token transactions that update this distributed database. We have developed a unique commit protocol for token transactions, called unilateral commit (UCP), that efficiently achieves consistency and recoverability of the token state. The correctness of UCP with respect to the two-phase commit protocol is also presented.

REFERENCES

• Bellew et.al. 90: Matthew Bellew , Meichun Hsu , Va-On Tam, Update Propagation in Distributed Memory Hierarchy, Proceedings of the Sixth International Conference on Data Engineering, p.521-528, February 05-09, 1990
• Bernstein et.al. 87: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• Delp 88: Delp, G. S., The Architecture and Ira. plementation of Memnet: a High-Speed Shared.Memory Computer Communication Network. Technical Report 88-05- 1. Department of Electrical Engineering, University of Delaware, May 1988.
• Forin et.al. 89: Forin, A., Barrera, J., and Sanzi, R., The Shared Memory Server. Proceedings of USENIX Winter Conference. January 1989.
• Gray 78: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• Hsu et.al. 89: Hsu, M., and Tam, V., Transaction Synchronization in Distributed Virtual Memory Systems. Proceeding of 13th Computer Software ~~ Applications Conference. September 1989.
• Hsu et.al. 89a: Hsu, M., and Tam, V., Conflict Resolution of Token Transfers in Data Mi. gration Systems. In preparation.
• Jul et.al. 88: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• Li 86: Kai Li, Shared virtual memory on loosely coupled multiprocessors, 1986
• Minoura et.al.82: Minoura, T. and Wiederhold, G. Resilient Extended True-Copy Token Scheme for a Distributed Database System. ~ IEEE Transactions on Software En. gineering, Vol SE-8, No. 3, May 1982.
• Nelson 81: Bruce Jay Nelson, Remote procedure call, 1981
• Ramachandran et.al. 88: Ramachandran, U., Ahamad, M., and Khalidi, M. Y. A., Unifying Synchronization and Data Transfer in Maintaining Coherence of Distributed Shared Memory. Technical Report Girl'. ICS-88/23, School of Information and Computer Science, Georgia Institute of Technology. June 1988.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases
      H.2.7 Database Administration
          Subjects: Logging and recovery

General Terms:
Algorithms, Design, Management, Performance, Reliability, Standardization, Theory, Verification