Abstract
An important aspect which is often overlooked in software _design of distributed environments is that of fault tolerance. Many methodologies in the past have attempted to provide fault tolerance efficiently, but have never been successful at eliminating explicit time and space redundancy. One approach is the Application-Oriented Fault Tolerance Paradigm, which provides fault tolerance by examining the behavior and properties of the application and deriving executable assertions for the detection of faults. Previous work has demonstrated the feasibility of the application-oriented fault tolerance paradigm for various applications. However, the executable assertions were guided by the natural constraints of the problem. This work uses Changeling to apply concurrent programming axiomatic proof systems to formally generate executable assertions in a distributed environment, by showing a transformation of the assertions derived from the verification proof of a program into executable assertions. These executable assertions are then embedded into the program to create a fault-tolerant program. The model used to demonstrate this approach is the class of Branch and Bound problems. The resulting error-detecting algorithm is implemented in parallel on a distributed memory machine. Experimental performance results and analytical bounds on the fault tolerance are reported for the Traveling Salesman application.
Recommended Citation
Sun, Aggie Y.; Lutfiyya, Hanan; and McMillin, Bruce, "An Application-Oriented Approach to Distributed Error-Detecting Branch & Bound" (1992). Computer Science Technical Reports. 149.
https://scholarsmine.mst.edu/comsci_techreports/149
Department(s)
Computer Science
Keywords and Phrases
Distributed Algorithms, Fault Tolerance, Branch and Bound, Error Detection,Application-Oriented Techniques, Naturally Redundant Algorithms, Loose Synchrony, PerformanceValidation
Report Number
CSc-92-26
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1992 University of Missouri - Rolla, All rights reserved
Publication Date
18 December, 1992
Comments
The first and second Authors are Graduate Students.
This work was supported in part by the National Science Foundation under Grant Number MSS-9216479, and, in part, from the Air Force Office of Scientific Research under contract number F49620-92-J-0546.
Hanan Lutfiyya is with the Department of Computer Science at the University of Western Ontario, London, ONTARIO N6A 5B7 (hanan@csd.uwo.ca). The work was performed when Dr. Lutfiyya was at the University of Missouri-Rolla.
Aggie Sun (aggies@cs.umr.edu) and Bruce McMillin (ff@cs.umr.edu) are with the Department of Computer Science at the University of Missouri-Rolla, Rolla, MO 65401.