Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Fault tolerance in distributed computing is a wide area with a significant body of literature that is vastly diverse in methodology and terminology. This paper aims at structuring the area and thus guiding readers into this interesting field. We use a formal approach to define important terms like fault, fault tolerance, and redundancy. This leads to four distinct forms of fault tolerance and to two main phases in achieving them: detection and correction. We show that this can help to reveal inherently fundamental structures that contribute to understanding and unifying methods and terminology. By doing this, we survey many existing methodologies and discuss their relations. The underlying system model is the close-to-reality asynchronous message-passing model of distributed computing.

REFERENCES

• 1: Marcos Kawazoe Aguilera , Wei Chen , Sam Toueg, Heartbeat: A Timeout-Free Failure Detector for Quiescent Reliable Communication, Proceedings of the 11th International Workshop on Distributed Algorithms, p.126-140, September 24-26, 1997
• 2: Marcos K Aguilera , Wei Chen , Sam Toueg, On the Weakest Failure Detector for Quiescent Reliable Communication, Cornell University, Ithaca, NY, 1997
• 3: Marcos K Aguilera , Wei Chen , Sam Toueg, Quiescent Reliable Communication and Quiescent Consensus in Partitionable Networks, Cornell University, Ithaca, NY, 1997
• 4: Marcos Kawazoe Aguilera , Wei Chen , Sam Toueg, Failure Detection and Consensus in the Crash-Recovery Model, Proceedings of the 12th International Symposium on Distributed Computing, p.231-245, September 24-26, 1998
• 5: C. Almeida , P. Veríssimo , ssimo, Using Light-Weight Groups to Handle Timing Failures in Quasi-Synchronous Systems, Proceedings of the IEEE Real-Time Systems Symposium, p.430, December 02-04, 1998
• 6: ALMEIDA, C., VERISSIMO, P., AND CASIMIRO, A. 1998. The quasi-synchronous approach to fault-tolerant and real-time communication and processing. Technical Report CTI RT- 98-04. Instituto Superior T~cnico, Lisboa, Portugal.
• 7: ALPERN, B. AND SCHNEIDER, F. B. 1985. Defining liveness. Inf. Process. Lett. 21, 4 (Oct.), 181- 185.
• 8: Anish Arora , Mohamed Gouda, Closure and Convergence: A Foundation of Fault-Tolerant Computing, IEEE Transactions on Software Engineering, v.19 n.11, p.1015-1027, November 1993 [doi>10.1109/32.256850]
• 9: A. Arora , M. Gouda, Distributed Reset, IEEE Transactions on Computers, v.43 n.9, p.1026-1038, September 1994 [doi>10.1109/12.312126]
• 10: Anish Arora , Mohamed Gouda , George Varghese, Constraint satisfaction as a basis for designing nonmasking fault-tolerance, Journal of High Speed Networks, v.5 n.3, p.293-306, 1996
• 11: A. Arora , S. S. Kulkarni, Detectors and Correctors: A Theory of Fault-Tolerance Components, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.436, May 26-29, 1998
• 12: Anish Arora , Sandeep S. Kulkarni, Component Based Design of Multitolerant Systems, IEEE Transactions on Software Engineering, v.24 n.1, p.63-78, January 1998 [doi>10.1109/32.663998]
• 13: Anish Arora , Sandeep S. Kulkarni, Designing Masking Fault-Tolerance via Nonmasking Fault-Tolerance, IEEE Transactions on Software Engineering, v.24 n.6, p.435-450, June 1998 [doi>10.1109/32.689401]
• 14: Anish Kumar Arora, A foundation of fault-tolerant computing, University of Texas at Austin, Austin, TX, 1992
• 15: ATTIYA, H., BAR-NOY, A., DOLEV, D., KOLLER, D., PELEG, D., AND REISCHUK, R. 1987. Achievable cases in an asynchronous environment. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science (Oct. 1987). IEEE Computer Society Press, Los Alamitos, CA, 337-346.
• 16: AVIZIENIS, A. 1976. Fault-tolerant systems. IEEE Trans. Comput. 25, 12 (Dec.), 1304- 1312.
• 17: Özalp Babaoglu , Alberto Bartoli , Gianluca Dini, Replicated File Management in Large-Scale Distributed Systems, Proceedings of the 8th International Workshop on Distributed Algorithms, p.1-16, September 29-October 01, 1994
• 18: O. Babaoglu , R. Davoli , A. Montresor, Partitionable Group Membership: Specification and Algorithms, University of Bologna, 1997
• 19: Özalp Babaoğlu , Keith Marzullo, Consistent global states of distributed systems: fundamental concepts and mechanisms, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 20: Michael Barborak , Anton Dahbura , Minoslaw Malek, The consensus problem in fault-tolerant computing, ACM Computing Surveys (CSUR), v.25 n.2, p.171-220, June 1993 [doi>10.1145/152610.152612]
• 21: BARTLETT, J. F. 1978. A "NonStop" operating system. In Proceedings of the 11th Hawaii International Conference on System Sciences. IEEE Computer Society Press, Los Alamitos, CA.
• 22: Anindya Basu , Bernadette Charron-Bost , Sam Toueg, Simulating Reliable Links with Unreliable Links in the Presence of Process Crashes, Proceedings of the 10th International Workshop on Distributed Algorithms, p.105-122, October 09-11, 1996
• 23: Anindya Basu , Bernadette Charron-Bost , Sam Toueg, Solving Problems in the Presence of Process Crashes and Lossy Links, Cornell University, Ithaca, NY, 1996
• 24: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 25: Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993 [doi>10.1145/163298.163303]
• 26: Gabriel Bracha , Sam Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM (JACM), v.32 n.4, p.824-840, Oct. 1985 [doi>10.1145/4221.214134]
• 27: S. Chandra , P. M. Chen, How Fail-Stop are Faulty Programs?, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.240, June 23-25, 1998
• 28: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 29: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg , Bernadette Charron-Bost, On the impossibility of group membership, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.322-330, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248120]
• 30: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 31: K. M. Chandy , Jayadev Misra, How processes learn, Distributed Computing, v.1 n.1, p.40-52, Jan. 1986 [doi>10.1007/BF01843569]
• 32: Bernadette Charron-Bost , Carole Delporte-Gallet , Hugues Fauconnier, Local and temporal predicates in distributed systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.157-179, Jan. 1995 [doi>10.1145/200994.201005]
• 33: Bernadette Charron-Bost , Friedemann Mattern , Gerard Tel, Synchronous, asynchronous, and causally ordered communication, Distributed Computing, v.9 n.4, p.173-191, February 1996 [doi>10.1007/s004460050018]
• 34: Craig M. Chase , Vijay K. Garg, Detection of global predicates: techniques and their limitations, Distributed Computing, v.11 n.4, p.191-201, October 1998 [doi>10.1007/s004460050049]
• 35: Robert Cooper , Keith Marzullo, Consistent detection of global predicates, ACM SIGPLAN Notices, v.26 n.12, p.167-174, Dec. 1991
• 36: CRISTIAN, F. 1985. A rigorous approach to faulttolerant programming. IEEE Trans. Softw. Eng. 11, 1 (Jan.), 23-31.
• 37: Flavin Cristian, Understanding fault-tolerant distributed systems, Communications of the ACM, v.34 n.2, p.56-78, Feb. 1991 [doi>10.1145/102792.102801]
• 38: F. Cristian , C. Fetzer, The Timed Asynchronous Distributed System Model, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.140, June 23-25, 1998
• 39: J. -L. Dega, The redundancy mechanisms of the Ariane 5 Operational Control Center, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.382, June 25-27, 1996
• 40: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 41: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 42: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 43: Danny Dolev , Roy Friedman , Idit Keidar , Dahlia Malkhi, Failure Detectors in Omission Failure Environments, Cornell University, Ithaca, NY, 1996
• 44: Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
• 45: DOUDOU, A. AND SCHIPER, n. 1997. Muteness detectors for consensus with Byzantine processes. Technical report, EPFL. Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland.
• 46: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 47: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 48: Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Distributed Computing, v.1 n.1, p.26-39, Jan. 1986 [doi>10.1007/BF01843568]
• 49: GARG, V. K. 1997. Observation and control for debugging distributed computations. In 3rd Int. Workshop on Automated Debugging (AADEBUG 97, Link~ping, Sweden, May). 1-12.
• 50: V. K. Garg , J. R. Mitchell, Distributed Predicate Detection in a Faulty Environment, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.416, May 26-29, 1998
• 51: V. K. Garg , B. Waldecker, Detection of Weak Unstable Predicates in Distributed Programs, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.299-307, March 1994 [doi>10.1109/71.277788]
• 52: Vijay K. Garg , Brian Waldecker, Detection of Strong Unstable Predicates in Distributed Programs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1323-1333, December 1996 [doi>10.1109/71.553309]
• 53: GARTNER, F. C. 1998. Specifications for fault tolerance: A comedy of failures. Technical Report TUD-BS-1998-03. Darmstadt University of Technology, Darmstadt, Germany.
• 54: GARTNER, F. C. AND PAGNIA, H. 1998. Enhancing the fault tolerance of replication: another excercise in constrained convergence. In Digest of Fast Abstracts of the 28th IEEE Symposium on Fault Tolerant Computing Systems (FTCS- 28, June). IEEE Computer Society Press, Los Alamitos, CA.
• 55: Richard A Golding, ACCESSING REPLICATED DATA IN A LARGE-SCALE DISTRIBUTED SYSTEM (M.S. Thesis), University of California at Santa Cruz, Santa Cruz, CA, 1991
• 56: R. Guerraoui , M. Larrea , A. Schiper, Non blocking atomic commitment with an unreliable failure detector, Proceedings of the 14TH Symposium on Reliable Distributed Systems, p.41, September 13-15, 1995
• 57: Rachid Guerraoui , Andre Schiper, Consensus: The Big Misunderstanding, Proceedings of the 6th IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS '97), p.183, October 29-31, 1997
• 58: Vassos Hadzilacos , Sam Toueg, A Modular Approach to Fault-Tolerant Broadcasts and Related Problems, Cornell University, Ithaca, NY, 1994
• 59: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990 [doi>10.1145/79147.79161]
• 60: M. P. Herlihy , J. M. Wing, Specifying Graceful Degradation, IEEE Transactions on Parallel and Distributed Systems, v.2 n.1, p.93-104, January 1991 [doi>10.1109/71.80192]
• 61: Mei-Chen Hsueh , Timothy K. Tsai , Ravishankar K. Iyer, Fault Injection Techniques and Tools, Computer, v.30 n.4, p.75-82, April 1997 [doi>10.1109/2.585157]
• 62: HURFIN, M., MOSTEFAOUI, A., AND RAYNAL, M. 1997. Consensus in asynchronous systems where processes can crash and recover. Technical Report 1144. IRISA, Rennes Cedex, France.
• 63: Pankaj Jalote, Fault tolerance in distributed systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 64: D. Richard Kuhn, Sources of Failure in the Public Switched Telephone Network, Computer, v.30 n.4, p.31-36, April 1997 [doi>10.1109/2.585151]
• 65: Sandeep S. Kulkarni , Anish Arora, Compositional Design of Multitolerant Repetitive Byzantine Agreement, Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, p.169-183, December 18-20, 1997
• 66: LAMPORT, L. 1977. Proving the correctness of multiprocess programs. IEEE Trans. Softw. Eng. 3, 2 (Mar.), 125-143.
• 67: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 68: Leslie Lamport , Nancy Lynch, Distributed computing: models and methods, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 69: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 70: LAPRIE, J.C. 1985. Dependable computing and fault tolerance: concepts and terminology. In Proceedings of the 15th IEEE Symposium on Fault Tolerant Computing Systems (FTCS-15, June 1985). IEEE Computer Society Press, Los Alamitos, CA, 2-11.
• 71: Gérard Le Lann, On Real-Time and Non Real-Time Distributed Computing, Proceedings of the 9th International Workshop on Distributed Algorithms, p.51-70, September 13-15, 1995
• 72: LONG, D. D. E., CARROLL, J. L., AND PARK, C. J. 1991. A study of the reliability of Internet sites. In Proceedings of the l Oth IEEE Symposium on Reliable Distributed Systems (Pisa, Italy, Sept.). IEEE Press, Piscataway, NJ, 177-186.
• 73: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 74: Keith Marzullo , Gil Neiger, Detection of Global State Predicates, Proceedings of the 5th International Workshop on Distributed Algorithms, p.254-272, October 07-09, 1991
• 75: Sape Mullender, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 76: Victor P. Nelson, Fault-Tolerant Computing: Fundamental Concepts, Computer, v.23 n.7, p.19-25, July 1990 [doi>10.1109/2.56849]
• 77: OLIVEIRA, R., GUERRAOUI, R., AND SCHIPER, A. 1997. Consensus in the crash-recover model. Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland. Technical Report TR-97/239
• 78: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 79: RICCIARDI, A., SCHIPER, A., AND BIRMAN, K. 1993. Understanding partitions and the "no partition" assumption. In Proceedings of the 4th Workshop on Future Trends of Distributed Computing Systems (FTDCS-4).
• 80: Laura S. Sabel , Keith Marzullo, Election Vs. Consensus in Asynchronous Systems, Cornell University, Ithaca, NY, 1995
• 82: SCHIPER, n. AND RICCARDI, n. 1993. Virtuallysynchronous communication based on a weak failure suspector. In Proceedings of the 23rd IEEE Symposium on Fault Tolerant Computing Systems (FTCS-23). IEEE Computer Society Press, Los Alamitos, CA, 534-543.
• 83: André Schiper , Alain Sandoz, Primary Partition "Virtually-Synchronous Communication" harder than Consensus, Proceedings of the 8th International Workshop on Distributed Algorithms, p.39-52, September 29-October 01, 1994
• 84: Richard D. Schlichting , Fred B. Schneider, Fail-stop processors: an approach to designing fault-tolerant computing systems, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.222-238, August 1983 [doi>10.1145/357369.357371]
• 85: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 86: Fred B. Schneider, What good are models and what models are good?, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 87: Marco Schneider, Self-stabilization, ACM Computing Surveys (CSUR), v.25 n.1, p.45-67, March 1993 [doi>10.1145/151254.151256]
• 88: Reinhard Schwarz , Friedemann Mattern, Detecting causal relationships in distributed computations: in search of the holy grail, Distributed Computing, v.7 n.3, p.149-174, March 1994 [doi>10.1007/BF02277859]
• 89: Daniel P. Siewiorek , Robert S. Swarz, Reliable computer systems (2nd ed.): design and evaluation, Digital Press, Newton, MA, 1992
• 90: A. Singhai , S. -B. Lim, The SunSCALR Framework for Internet Servers, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.108, June 23-25, 1998
• 91: Alfred Spector , David Gifford, The space shuttle primary computer system, Communications of the ACM, v.27 n.9, p.872-900, Sept. 1984 [doi>10.1145/358234.358246]
• 92: Scott D. Stoller, Detecting Global Predicates in Distributed Systems with Clocks, Proceedings of the 11th International Workshop on Distributed Algorithms, p.185-199, September 24-26, 1997
• 93: Scott D. Stoller , Fred B. Schneider, Faster Possibility Detection by Combining Two Approaches, Proceedings of the 9th International Workshop on Distributed Algorithms, p.318-332, September 13-15, 1995
• 94: Gerard Tel, Introduction to distributed algorithms, Cambridge University Press, New York, NY, 1994
• 95: THEEL, O. AND GARTNER, F.C. 1998. On proving the stability of distributed algorithms: selfstabilization vs. control theory. In Proceedings of the International Computers Conference on Systems, Signals, Control (SSCC'98, Durban, South Africa, Sept.), V. B. Bajic, Ed. 58-66.
• 96: John Turek , Dennis Shasha, The Many Faces of Consensus in Distributed Systems, Computer, v.25 n.6, p.8-17, June 1992 [doi>10.1109/2.153253]
• 97: Hagen Völzer, Verifying Fault Tolerance of Distributed Algorithms Formally - An Example, Proceedings of the 1998 International Conference on Application of Concurrency to System Design, p.187, March 23-26, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

Additional Classification:
  A. General Literature

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Algorithms, Design, Reliability, Theory

Keywords:
agreement problem, asynchronous system, consensus problem, failure correction, failure detection, fault models, fault tolerance, liveness, message passing, possibility detection, predicate detection, redundancy, safety