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.