Software Fault Tolerance of Concurrent Programs Using Controlled Re-execution

Abstract. Concurrent programs often encounter failures, such as races, owing to the presence of synchronization faults (bugs). One existing tech-nique to tolerate synchronization faults is to roll back the program to a previous state and re-execute, in the hope that the failure does not recur. Instead of relying on chance, our approach is to control the re-execution in order to avoid a recurrence of the synchronization failure. The control is achieved by tracing information during an execution and using this information to add synchronizations during the re-execution. The approach gives rise to a general problem, called the o-line predicate control problem, which takes a computation and a property specied on the computation, and outputs a \controlled " computation that maintains the property. We solve the predicate control problem for the mutual exclusion property, which is especially important in synchronization fault tolerance.