Multi-node fault-tolerant timestamp generation

Details Multi-node fault-tolerant timestamp generation Multi-node fault-tolerant timestamp generation

1997-10-31

2000-06-20

Kulik, Paul V.

Data processing: database and file management or data structures

Database design

Data structure types

707203, 714 20, G06F 1700, G06F 1100

Patent

active

060789301

ABSTRACT:
Techniques for determining a safe recovery time value after a failure of a first node in a computer system are described. According to the techniques, every node in a multi-node parallel database system maintains a logical clock for generating timestamps. The logical clocks are synchronized by attaching a current timestamp to every message that is sent by a node. When a node receives an incoming timestamp that is greater than the value indicated by the associated logical clock, it sets the associated logical clock forward to at least the value of the timestamp. When a node fails, a recovery node calculates a "safe" logical clock value to use in recovering the crashed node. In calculating the "safe" logical clock value, the recovery node searches specific areas of the database to locate and recover a most recent timestamp value associated with the crashed node. The recovery node then compares its current logical clock time value with the most recent crash node timestamp value to determine which timestamp is most recent. If the most recent crash node timestamp value is more recent than the recovery node's current logical clock time value, the recovery node's logical clock is updated to be at least as recent as the most recent crash node timestamp value. The recovery node then recovers the crashed node as its logical clock is guaranteed to be at least as recent as any timestamp value that was previously written to the database by the crashed node prior to failure.

REFERENCES:
patent: 4507751 (1985-03-01), Gawlick et al.
patent: 5001730 (1991-03-01), Franaszek et al.
patent: 5155678 (1992-10-01), Fukumoto et al.
patent: 5278982 (1994-01-01), Daniels et al.
patent: 5280611 (1994-01-01), Mohan et al.
patent: 5561795 (1996-10-01), Sarkar
patent: 5566180 (1996-10-01), Eidson et al.
patent: 5613113 (1997-03-01), Goldring
patent: 5737600 (1998-04-01), Geiner et al.
patent: 5778387 (1998-07-01), Wilkerson et al.
patent: 5784421 (1998-07-01), Dolev et al.
patent: 5822381 (1998-10-01), Parry et al.
Lamport, Leslie, "Time, Clocks, and the Ordering of Events in a Distributed System," Operating Systems, Communications of the ACM, Jul. 1978, vol. 21, No. 7, pp. 558-565, ACM 0001-0782/78/0700-0558.
Li, Chung-Sheng and Ofek, Yoram, "Distributed Souce-Destination Synchronization Using Inband Clock Distribution," IEEE Journal on Selected Areas in Communications, vol. 14, No. 1, Jan. 1996.
Sens, Pierre, "The Performance of Independent Checkpointing in Distributed Systems," Proceedings of the 28.sup.th Annual Hawaii International Conference on System Sciences--1995.
Abali, Bulent and Stunkel, Craig B., "Time Synchronization on SP1 and SP2 Parallel Systems," IBM Thomas J. Watson Research Center, N.Y., 1995.
Vervoort, W.A., teWest, R., Schoute, A.L. and Hofstede, J., "Distributed Time-Management in Transputer Networks," Department of Computer Science, University of Twente, The Netherlands, 1991.
Comer, Douglas E. and Yavatkar, Raji, "High-Speed Propagation of Link Status Routing Control Information," Department of Computer Science at Purdue University and the Univeristy of Kentucky, 1990.

Affiliated with

Also associated with

Rating

Multi-node fault-tolerant timestamp generation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multi-node fault-tolerant timestamp generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-node fault-tolerant timestamp generation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1863366