On designing direct dependency: based fast recovery algorithms for distributed systems

ABSTRACT

In this paper, we have proposed two recovery algorithms for distributed systems. Both algorithms follow a revolving centralized scheme. The direct dependency tracking of an integer representing the number of messages sent by each process has been shown to be sufficient to determine the maximum consistent state. The main feature of the recovery algorithms is that they are executed simultaneously by all the participating processes while determining the maximum consistent state. It thus ensures fast execution. The time overheads of the recovery algorithms are reduced further because both algorithms avoid some unnecessary comparisons while determining a consistent global checkpoint. The second algorithm has been shown to be faster than the first one, because it avoids, in general, much larger number of unnecessary comparisons compared to the first one; however the trade off is the increased amount of control information to be stored at each checkpoint in the second algorithm.

REFERENCES

• 1: E. N. Elnozahy, D. B. Johnson, and Y. M. Wang, "A Survey of Rollback-Recovery Protocols in Message-Passing System", Technical Report. No CMU-CS-96-181, School of Computer Science, Carnegie Mellon Univ., 1996.
• 2: B. Randell , P. Lee , P. C. Treleaven, Reliability Issues in Computing System Design, ACM Computing Surveys (CSUR), v.10 n.2, p.123-165, June 1978 [doi>10.1145/356725.356729]
• 3: Richard Koo , Sam Toueg, Checkpointing and rollback-recovery for distributed systems, IEEE Transactions on Software Engineering, v.13 n.1, p.23-31, Jan. 1987 [doi>10.1109/TSE.1987.232562]
• 4: Yi-Min Wang , Andy Lowry , W. Kent Fuchs, Consistent global checkpoints based on direct dependency tracking, Information Processing Letters, v.50 n.4, p.223-230, May 25, 1994 [doi>10.1016/0020-0190(94)00038-7]
• 5: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 6: Yi-Min Wang, Consistent Global Checkpoints that Contain a Given Set of Local Checkpoints, IEEE Transactions on Computers, v.46 n.4, p.456-468, April 1997 [doi>10.1109/12.588059]
• 7: Mukesh Singhal , Niranjan G. Shivaratri , Niranjan Shivaratro, Advanced Concepts in Operating Systems, McGraw-Hill, Inc., New York, NY, 1994
• 8: T. Juang, and S. Venkatesan, "Crash Recovery with Little Overhead", Proc. 11th Intl Conf. Distributed Computing Systems, pp. 454--461, May 1991.
• 9: S. Venkatesan , Tony Tong-Ying Juang , Sridhar Alagar, Optimistic Crash Recovery without Changing Application Messages, IEEE Transactions on Parallel and Distributed Systems, v.8 n.3, p.263-271, March 1997 [doi>10.1109/71.584092]
• 10: A low-overhead recovery technique using quasi-synchronous checkpointing, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.100, May 27-30, 1996
• 11: Jichiang Tsai , Sy-Yen Kuo , Yi-Min Wang, Theoretical Analysis for Communication-Induced Checkpointing Protocols with Rollback-Dependency Trackability, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.963-971, October 1998 [doi>10.1109/71.730526]
• 12: Vijay Kumar Garg, Principles of Distributed Systems, Kluwer Academic Publishers, Norwell, MA, 1996
• 13: B. Gupta , Z. Liu , Z. Liang, A Fast Recovery Scheme for Distributed Systems, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, p.360-366, June 24-27, 2002

INDEX TERMS

Keywords:
communication-induced checkpoint, consistency, maximum consistent state