Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.9 No.1, pp.103-122 (March 1993)
Message and Time Optimal Crash Recovery in
Tree Networks*

Tony T-Y. Juang and S. Venkatesan
Computer Science Program, EC 31
University of Texas at Dallas
Richardson, TX 75083-0688

Coping with processor failures is an important problem in distributed transaction processing systems. A crash recovery technique using optimistic message logging for tree networks that places the least possible overhead is presented in this paper. The application messages are not modified (no extra information is appended to them), and both volatile and stable logs are used. We show that úc(n) is the message complexity, and úc(h) is the time complexity of rollback recovery in tree networks, where n is the number of processors, and h is the height of the tree.

Keywords: distributed algorithms, fault tolerance, crash recovery, checkpointing, rollback, optimistic message logging, tree networks

Received November 17, 1992; revised February 24, 1993.
Communicated by Jun S. Huang
*This research was supported in part by NSF under Grant No. CCR-9110177 and by the Tesas Advanced Technology Program under Grant No. 9741-036.