Lightweight Fault-Tolerance

As distributed computing becomes commonplace, and many more applications are faced with the current costs of high availability, there is a fresh need for recovery-based techniques that combine high performance during failure-free executions with fast recovery. However, although the literature contains approximately 300 papers in this area, rollback recovery is seldom used in practice to build reliable distributed applications. The Lightweight Fault-Tolerance (LiFT) project has focused on changing this state of affairs with an approach that blends algorithmic work, systems building, and empirical analysis.

Highlights

• The Survey This survey covers rollback-recovery techniques that do not require special language constructs. In the first part of the survey we classify rollback-recovery protocols into checkpoint-based and log-based. Checkpoint-based protocols rely solely on checkpointing for system state restoration. Checkpointing can be coordinated, uncoordinated, or communication-induced. Log-based protocols combine checkpointing with logging of nondeterministic events, encoded in tuples called determinants. Depending on how determinants are logged, log-based protocols can be pessimistic, optimistic, or causal. Throughout the survey, we highlight the research issues that are at the core of rollback recovery and present the solutions that currently address them. We also compare the performance of different rollback-recovery protocols with respect to a series of desirable properties and discuss the issues that arise in the practical implementations of these protocols.
  Relevant Publications:
  • A Survey of Rollback-Recovery Protocols in Message-Passing Systems. (with E. Elnozahy, Y.M. Wang and D.B. Johnson). ACM Computing Surveys, 34:3, September 2002, pp. 375-408.

• Causal Logging Protocols We have developed the first formal specification of the consistency condition common to all rollback recovery protocols, and we have derived from it causal logging, a novel technique that eliminates the traditional performance tradeoffs between pessimistic and optimistic protocols. Causal logging protocols perform as well as optimistic protocols during failure-free executions, but, like pessimistic protocols, never roll back correct processes during crash recovery.
  Relevant Publications:
  • Scalable Causal Message Logging for Wide-Area Environments. (with K. Bhatia and K. Marzullo). Concurrency and Computation: Practice and Experience, 15:3, August 2003, pp. 873-889.
  • Tracking Causality in Causal Message Logging Protocols. (with K. Bhatia and K. Marzullo). Distributed Computing, 15:1, January 2002, pp. 1-15.
  • Scalable Causal Message Logging for Wide-Area Environments (with K. Bhatia and K. Marzullo). In Proceedings of the European Conference on Parallel Computing (Euro-Par 2001), Manchester, UK, August 2001, pp. 864-873.
  • The Relative Overhead of Piggybacking in Causal Message-Logging Protocols.. (with K. Bhatia and K. Marzullo) Proceedings of the Workshop on Advances in Parallel and Distributed Systems (APADS) October 20, 1998, Purdue University, West Lafayette, Indiana.
  • Message Logging: Pessimistic, Optimistic, Causal, and Optimal. (with K. Marzullo) IEEE Transactions on Software Engineering . 24:2, February 1998, pp. 149-159.
  • Trade-Offs in Implementing Causal Message Logging Protocols. (with K. Marzullo) Proceedings of the 15th ACM Annual Symposium on the Priciples of Distributed Computing. Philadelphia, May 1996, pp. 58-67.
  • Message Logging: Pessimistic, Optimistic, and Causal. (with K. Marzullo) Proceedings of the 15th IEEE International Conference on Distributed Computing Systems. Vancouver, Canada, June 1995, pp. 229-236.
  • Deriving optimal checkpoint protocols for distributed shared memory architectures. (with K. Marzullo) Selected Papers, International Workshop in Theory and Practice in Distributed Systems , K. Birman, F. Mattern and A. Schiper editors, Springer-Verlag 1995, pp. 111-120.
  • Nonblocking and Orphan-Free Message Logging Protocols. (with B. Hoppe and K. Marzullo) Proceedings of the 23rd International Symposium on Fault Tolerant Computing, Toulouse, France, June 1993 pp. 145-154.

• The Egida Toolkit Research in rollback recovery has long suffered from a flourishing of algorithmic results that are rarely supported by careful experimental evaluation of their practical significance. As a result, the performance of these algorithms in practice is not well understood, and little attention has been given to simplifying the difficult task of integrating rollback recovery protocols with applications. To address these issues, we have developed the Egida toolkit. Egida’s design addresses for the first time the fundamental problem of characterizing the set of functionalities that are at the core of all message-logging protocols. This characterization, based on a framework for handling non-determinism in a process execution, gives Egida the expressiveness to encompass the diversity of rollback recovery protocols. A protocol is specified using a simple, high-level language; the protocol’s implementation is synthesized from this specification by gluing together appropriate modules from a library. As a result, Egida allows the implementation of arbitrary rollback recovery protocols with minimal programming effort. A version of Egida for Solaris 2.8 is available for downlaod.
  Relevant Publications:
  • Egida: An Extensible Toolkit For Low-overhead Fault-Tolerance. (with S. Rao and H. Vin) In Proceedings of the 29th Fault-tolerant Computing Symposium (FTCS-29), Madison, Wisconsin, June 1999, pp. 48-55.

• Understanding the Cost of Recovery Using Egida, we have performed the first study of the recovery performance of message-logging protocols. This study has revealed that no existing protocol can simultaneously guarantee low overhead during failure-free execution, fast recovery, and fault-containment, leaving applications to face a complex tradeoff. To eliminate this tradeoff, we have developed a new class of protocols that never roll back correct processes, recover quickly (within 2% of the protocol with the best recovery time) and impose little overhead during failure-free execution (within 2% of the protocol with the best failure-free time). Relevant Publications:
  • The Cost of Recovery in Message Logging Protocols. (with S. Rao and H.Vin). IEEE Transactions on Knowledge and Data Engineering, 12:2, March/April 2000, pp. 160-173.
  • The Cost of Recovery in Message Logging Protocols. (with S. Rao and H.Vin). Proceedings of the 17th International Symposium on Reliable Distributed Systems. West Lafayette, Indiana, October 1998.
  • Hybrid Message-Logging Protocols for Fast Recovery. (with S. Rao and H. Vin) Digest of FastAbstracts. The 28th International Symposium on Fault-Tolerant Computing. Munich, Germany, June 1998, pp. 41-42.

• An Analysis of Communication-Induced Checkpointing Communication-induced checkpointing considerable autonomy in deciding when to take checkpoints and guarantee that no process will ever take a useless checkpoint, i.e. a checkpoint that will never belong to any consistent global state. Before our study, it had been qualitatively argued that the value of CIC protocols lies in their ability to allow processes to take checkpoints independently. We have shown that this ability offers no substantial benefit. First, even though choosing when to take a checkpoint can be useful --- for example, a process can delay checkpointing until it has very little state to record --- our experiments show that the number of forced checkpoints CIC imposes to ensure no checkpoints are useless are more than twice the number of independent checkpoints. Second, the number of forced checkpoints grows linearly with the number of processes in the system, suggesting that CIC protocols may be difficult to scale. Third, the nature of a checkpoint in CIC hurts performance. While in coordinated checkpointing processes can checkpoint asynchronously, in CIC processes must checkpoint synchronously to prevent the creation of useless checkpoints. As a result, the overhead imposed by CIC during failure-free executions is about an order of magnitude higher than that of coordinated checkpointing.
  Relevant Publications:
  • An Analysis of Communication-Induced Checkpointing. (with E. Elnozahy, S. Rao, S.A. Husain and A. de Mel) In Proceedings of the 29th Fault-tolerant Computing Symposium (FTCS-29), Madison, Wisconsin, June 1999, pp. 242-249.

• Efficient support of file I/O Traditional rollback recovery techniques treat the file system as part of the "outside world". As a result, processes may be forced to execute a blocking output commit protocol whenever they interact with the file system.
  We have derived a new protocol that integrates records and efficiently replicates the information necessary to reproduce file I/O operations during recovery. Our simulation studies show that this approach eliminates all synchronous logging to stable storage, thereby reducing the cost of performing file I/O dramatically.
  Relevant Pulications:
  • Low-Overhead Protocols for Fault-Tolerant File Sharing. (with S. Rao and H. Vin) Proceedings of the 18th IEEE International Conference on Distributed Computing Systems. Amsterdam, The Netherlands, May 1998, pp. 452-461.

• Fault-Tolerant TCP. We have developed an implementation of a fault-tolerant TCP (FT-TCP) that allows a faulty server to keep its TCP connections open until it either recovers or it is failed over to a backup. The failure and recovery of the server process are completely transparent to client processes connected with it via TCP. FT-TCP does not affect the software running on a client, does not require to change the server's TCP implementation, and does not use a proxy. We have studied the performance of FT-TCP for Microsoft's Samba file server and a multimedia streaming server from Apple comparing two implementations of FT-TCP, one based on primary-backup and another based on message logging. Our focus was on scalability, failover time, and application transparency. Our experiments suggest that FT-TCP is a practicable approach for replicating TCP/IP-based services that incurs low overhead on throughput, scales well as the number of clients increases, and allows recovery of the service in near-optimal time.

  Although the details of our solution are specific to TCP, the architecture that we propose is sufficiently general to be applicable in principle to other connection-oriented network protocols.

Relevant Publications:
• Engineering Fault Tolerant TCP/IP Services Using FT-TCP (with D. Zagorodnov, K. Marzullo, and T. Bressoud). To appear in Proceedings of the International Conference on Dependable Systems and Networks (DSN 2003), DCC Symposium, June 2003.
• Wrapping Server-Side TCP to Mask Connection Failures. (with T.C. Bressoud, A. El-Khashab, K. Marzullo, and D. Zagorodnov). In Proceedings of Infocom 2001 , Anchorage, Alaska, April 2001, pp. 329-338.
• A Fault-Tolerant JVM. We have showed, for the first time, how to apply state machine replication to multi-threaded state machines. In particular, we have modified the Sun JDK1.2 to provide transparent fault tolerance for many Java applications using a primary backup architecture. We identify the sources of nondeterminism in the JVM (including asynchronous exceptions, multi-threaded access to shared data, and the nondeterminism present at the native method interface) and guarantee that primary and backup handle them identically. We analyze the overhead introduced in our system by each of these sources of non-determinism and compare the performance of different techniques for handling multithreading.

Relevant Publications:
• A Fault-Tolerant Java Virtual Machine (with J. Napper and H. Vin). To appear in Proceedings of the International Conference on Dependable Systems and Networks (DSN 2003), DCC Symposium, June 2003.
• Fault-Tolerance: Java's Missing Buzzword. Invited Paper. Proceedings of the 7th Heterogeneous Computing Workshop (HCW '98), Orlando, Florida, March 1998, pp. 156-158.

Collaborators and Alumni

• Tom Bressoud (Denison University)
• Elmootazbellah Elnozahy (IBM Austin Research Lab)
• Keith Marzullo (UCSD)
• Jeff Napper
• Sriram Rao, Ph.D. August 1999, UT Austin
• Harrick Vin
• Kalpana Ravinarayanan, M.S. May 2000, UT Austin
• Karan Bhatia, Ph.D. December 2000, UCSD
• Ravishankar C.V., M.S. May 2001, UT Austin
• Dmitri Zagarodnov (UCSD)

Sponsors

• The Alfred P. Sloan Foundation through a Research Fellowship
• NSF through a CAREER award, Grant no. 9734185
• DARPA through its support of the WAFT project
• Dell through a LARIAT award
• IBM through a Faculty Partnership award