Timestamp-Based Orphan Elimination

ABSTRACT

An orphan in a distributed transaction system is an activity executing on behalf of an aborted transaction. A method is proposed for managing orphans created by crashes and by aborts that ensures that orphans are detected and eliminated in a timely manner, and also prevents them from observing inconsistent states. The method uses timestamps generated at each site. Transactions are assigned timeouts at different sites. These timeouts are related by a global invariant, and they may be adjusted by simple two-phase protocols. The principal advantage of this method is simplicity: it is easy to understand, and to implement, and it can be proved correct. An 'eager' version of this method uses approximately synchronized real-time clocks to ensure that orphans are eliminated within a fixed duration, and a 'lazy' version uses logical clocks to ensure that orphans are eventually eliminated as information propagates through the system. The method is fail-safe: unsynchronized clocks and lost messages may affect performance, but they cannot produce inconsistencies or protect orphans from eventual elimination. Although the method is informally described in terms of two-phase locking, the formal argument shows it is applicable to any concurrency control method that preserved atomicity.

REFERENCES

• 1: {1} J. Allchin, "An architecture for reliable decentralized systems," Georgia Inst. Technol., Tech. Rep. GIT-ICS-83/23, 1983.
• 2: Kenneth P. Birman, Replication and fault-tolerance in the ISIS system, Proceedings of the tenth ACM symposium on Operating systems principles, p.79-86, December 1985, Orcas Island, Washington, United States
• 3: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 4: {4} M. P. Herlihy, N. A. Lynch, M. Merritt, and W. E. Weihl, "On the correctness of orphan elimination algorithms," <i>ACM</i>, to be published; abbreviated version in 17th FTCS.
• 5: J. A. Goree, INTERNAL CONSISTENCY OF A DISTRIBUTED TRANSACTION SYSTEM WITH ORPHAN DETECTION, Massachusetts Institute of Technology, Cambridge, MA, 1983
• 6: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 7: {7} G. G. Kenky, "An action management system for a distributed operating system," Master's thesis, Georgia Inst. Technol., Dec., 1985.
• 8: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 9: {9} B. Lampson, <i>Remote Procedure Calls (Lecture Notes in Computer Science 105)</i>. Berlin: Springer-Verlag, 1981, pp. 365-370.
• 10: Barbara Liskov , Robert Scheifler, Guardians and Actions: Linguistic Support for Robust, Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.381-404, July 1983 [doi>10.1145/2166.357215]
• 11: {11} B. H. Liskov, R. Scheifler, E. Walker, and W. E. Weihl, "Orphan detection," in <i>17th Symp. Fault-Tolerant Computer Systems (FTCS)</i>, July 1987, pp. 2-7.
• 12: Nancy A. Lynch, Concurrency control for resilient nested transactions, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588080]
• 13: Keith Marzullo , Susan Owicki, Maintaining the time in a distributed system, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.295-305, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806730]
• 14: {14} M. S. McKendry, "Clouds: A fault-tolerant distributed operating system," <i>IEEE Tech. Com. Distributed Processing Newslett.</i>, vol. 2, no. 6, June 1984.
• 15: E. B. Moss, NESTED TRANSACTIONS: AN APPROACH TO RELIABLE DISTRIBUTED COMPUTING, Massachusetts Institute of Technology, Cambridge, MA, 1981
• 16: {16} B. Nelson, "Remote procedure call," Xerox Palo Alto Research Center, Tech. Rep. CSL-79-3, 1981.
• 17: Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
• 18: {18} Rajdoot, "A remote procedure call mechanism supporting orphan detection and killing," Univ. Newcastle upon Tyne, Tech. Rep. TR 200, Apr. 1985.
• 19: 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]
• 20: {20} M. S. McKendry and M. P. Herlihy. "Time-driven orphan elimination," in <i>Proc. Fifth Symp. Reliability in Distributed Software and Database Systems</i>, Jan. 1986; also available as Tech. Rep. CMU-CS- 85-138.
• 21: {21} M. D. Skeen, "Crash recovery in a distributed database system," Ph.D. dissertation, Univ. California, Berkeley, May 1982.
• 22: Alfred Z. Spector , Dean Daniels , Daniel Duchamp , Jeffrey L. Eppinger , Randy Pausch, Distributed transactions for reliable systems, Proceedings of the tenth ACM symposium on Operating systems principles, p.127-146, December 1985, Orcas Island, Washington, United States
• 23: {23} A. Z. Spector, J. J. Bloch, D. S. Daniels, R. P. Draves, D. Duchamp, J. L. Eppinger, S. G. Menees, and D. S. Thompson, "The Camelot project," <i>Database Eng.</i>, vol. 9, no. 4, Dec. 1986; also available as Tech. Rep. CMU-CS-86-166, Carnegie-Mellon Univ., Nov. 1986.
• 24: E. F. Walker, ORPHAN DETECTION IN THE ARGUS SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 25: W. E. Weihl, SPECIFICATION AND IMPLEMENTATION OF ATOMIC DATA TYPES, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 26: William Weihl , Barbara Liskov, Implementation of resilient, atomic data types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.244-269, April 1985 [doi>10.1145/3318.3319]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.7 Organization and Design
          Subjects: Distributed systems

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

General Terms:
Algorithms, Design, Performance, Reliability, Verification

Keywords:
aborted transaction, concurrency control, concurrency control method, database management systems, distributed processing, distributed transaction system, real-time clocks, timestamp based orphan elimination, transaction processing, two-phase protocols