Software fault tolerance of concurrent programs using controlled re-execution

[0002] This application is a conversion from and claims priority of U.S. Provisional Application No. 60/159,253, filed Oct. 13, 1999.

[0003] The present invention is generally directed to methods for correcting synchronization faults in concurrently executed computer programs and, more particularly, to methods and systems for fault tolerance of concurrently executed software programs using controlled re-execution of the programs.

[0004] Concurrent programs are difficult to write. The programmer is presented with the task of balancing two competing forces: safety and liveness. Frequently, the programmer leans too much in one of the two directions, causing either safety failures (e.g. races) or liveness failures (e.g. deadlocks) Such failures arise from a particular kind of software fault (bug), known as a synchronization fault. Studies have shown that synchronization faults account for a sizeable fraction of observed software faults in concurrent programs. Locating synchronization faults and eliminating them by reprogramming is always the best strategy. However, many systems must maintain availability in spite of software failures. Concurrent programs include all parallel programming paradigms such as multi-threaded programs, shared-memory parallel programs, message-passing distributed programs, distributed shared-memory programs, etc. A parallel entity may be referred to as a process, although in practice it may also be a thread.

[0005] Traditionally, it was believed that software failures are permanent in nature and, therefore, they would recur in every execution of the program with the same inputs. This belief led to the use of design diversity to recover from software failures. In approaches based on design diversity, redundant modules with different designs are used, ensuring that there is no single point-of-failure. Contrary to this belief, it was observed that many software failures are, in fact, transient (they may not recur when the program is re-executed with the same inputs). In particular, the failures caused by synchronization faults are usually transient in nature.

[0006] The existence of transient software failures motivated a new approach to software fault tolerance based on rolling back the processes to a previous state and then restarting them (possibly with message reordering), in the hope that the transient failure will not recur in the new execution. Methods based on this approach have mostly relied on chance in order to recover from a transient software failure. In the special case of synchronization faults, however, it is desirable to do better.

[0007] It would therefore be desirable to be able to bypass a synchronization fault and recover from the resulting failure.

[0008] The present invention controls the re-execution of concurrent programs in order to avoid a recurrence of the synchronization failure. The invention provides a method of (i) tracing an execution, (ii) detecting a synchronization failure, (iii) determining a control strategy, and (iv) re-executing under control.

[0009] Control is achieved by tracing information during an execution and using this information to add synchronizations during the re-execution.

[0010] In accordance with the present invention, a method of providing fault tolerance in concurrently executing computer programs by controlling the re-execution of concurrent programs in order to avoid a recurrence of synchronization failures is provided, comprising:

[0011] (a) tracing the execution of concurrent programs;

[0012] (b) detecting synchronization failures resulting from said execution of the concurrent programs; and

[0013] (c) applying a control strategy, based on said detection of failures, for said execution of the concurrent programs.

[0014] Also in accordance with the present invention, application of a control strategy includes causing a re-execution of said concurrent programs under a control derived from tracing information during an execution, and wherein said control includes using said information to add synchronizations to said concurrent programs during re-execution.

[0015] For a more complete understanding of the invention and for application of further advantages thereof, reference is now made to the following description or preferred embodiments taken in conjunction with the accompanying drawings, in which:

[0016] FIG. 1 is an illustration of a tracing and controlling during rollback recovery;

[0017] FIG. 2 is an illustration of variants of Off-line exclusions;

[0018] FIG. 3 is an illustration of the algorithm used for Off-line independent read-write mutual exclusion;

[0019] FIG. 4 is an flow diagram showing the main steps of the invention; and

[0020] FIG. 5 is an illustration of tolerating races in a concurrent execution.

[0021] In accordance with the present, methods for tolerating transient synchronization failure in software is provided. The present invention controls the re-execution of concurrent programs, based on information traced during a failed execution. The following description will describe the management of races, tracing, failure detection, and re-execution under control in great depth.

[0022] Referring to FIG. 1, illustrated is an example of tracing and controlling during rollback recovery. To illustrate what determining a control strategy involves, consider the execution shown in FIG. 1(a). CS1-CS4 are the critical sections of the execution. The synchronizations between processes are shown as arrows from one process execution to another. A synchronization ensures that the execution after the head of the arrow can proceed only after the execution before the tail has completed. A race occurs when two critical sections execute simultaneously. For example, CS1 and CS2 may have a race, since the synchronizations do not prevent them from executing simultaneously. A control strategy is a set of added synchronizations that would ensure that a race does not occur. The race can be avoided by adding synchronizations, shown as broken arrows in FIG. 1(b).

[0023] The present invention allows for the development of a control strategy by determining which synchronizations to add to an execution trace in order to tolerate a synchronization fault during the re-execution of a computer program, or programs, encountering fault. This proves to be an important problem in its own right and can be applied in areas other than software fault tolerance, such as concurrent debugging. The problem is generalized using a framework known as the off-line predicate control problem. The problem, as it applied to debugging, was introduced in a paper entitled “Predicate control for active debugging of distributed programs,” by A. Tarafdar and V. K. Garg. IEEE Proceedings of the 9^thsymposium on Parallel and Distributed Processing, Orlando, USA, April 1998. Informally, off-line predicate control specifies that, given a computation and a property on the computation, one must determine a controlled computation (one with more synchronizations) that maintains the property (used is the term computation for a formal model of an execution). Previous attempts solved the predicate control problem for a class of properties called disjunctive predicates. Applying the results of the Tarafdar et al. study to software fault tolerance would mean avoiding synchronization failures of the form: l₁{circumflex over ( )}l₂{circumflex over ( )}l₃, where l₁is a local property specified on process P₁. For example, if l₁specifies that a server is unavailable, the synchronization failure is that all servers are unavailable at the same time.

[0024] The invention addresses a class of off-line predicate control problems, characterized by the mutual exclusion property, that is especially useful in tolerating races. Four classes of mutual exclusion properties are considered: off-line mutual exclusion, off-line readers writers, off-line independent mutual exclusion, and off-line independent read-write mutual exclusion. For each of these classes of properties, necessary and sufficient conditions under which the problem may be solved are determined. Furthermore, an efficient algorithm that solves the most general of the problems, off-line independent read-write mutual exclusion, is presented, which also solves each of the other three problems. The algorithm takes O(np) time, where n is the number of concurrent processes and p is the number of critical sections.

[0025] The said problems have been termed off-line problems to distinguish them from their more popular on-line variants (i.e. the usual mutual exclusion problems). The difference between the on-line and off-line problems is that in the on-line case, the computation is provided on-line, whereas in the off-line case, the computation is known a priori. Ignorance of the future makes on-line mutual exclusion a harder problem to solve.

[0026] In general, in on-line mutual exclusion, one cannot avoid deadlocks without making some assumptions (e.g. critical sections do not block). Thus, on-line mutual exclusion is impossible to solve. To understand why this is true, consider the scenario in FIG. 1. Any on-line algorithm, being unaware of the future computation, would have a symmetric choice of entering CS1 or CS2 first. If CS2 is entered first, it would result in a deadlock. An off-line algorithm, being aware of the future computation, could make the correct decision to enter CS1 first and add a synchronization from CS1 to CS2. There will always be scenarios where on-line mutual exclusion algorithms will fail, resulting in either race conditions or deadlocks. In such scenarios, controlled re-execution based on off-line mutual exclusion becomes vitally important.

[0027] The model that is now presented is of a single execution of the concurrent program. The model is not at the programming language level, but at a lower level, at which the execution consists of a sequence of states for each process and the communications that occurred among them, let S be a finite set of elementary entities known as states. S is partitioned into subsets S₁, S₂, . . . , S_n, where n>1. These partitions correspond to n processes in the system. A subset G of S is called a global state if ∀i: |G∩S_i|=1. Let G_idenote the unique element in G∩S_i. A global predicate is a function that maps a global state onto a boolean value.

[0028] A computation is a partial order → on S such that ∀i:→_iis a total order on S_i, where →_irepresents → restricted to the set S_i. Note that the states in a single process are totally ordered while the states across processes are partially ordered. We will use →, →^k, →^cto denote computations, and ∥, ∥^k, ∥^oto denote the respective incomparability relations (e.g. s∥t≡(s≯t){circumflex over ( )}(t≯s)). Given a computation → and a subset K of S, →-consistent (K)≡∀s, tεK s∥t. In particular, a global state may be →-consistent. The notion of consistency indicates when a set of states could have occurred concurrently in a computation.

[0029] A computation → is extensible in S if:

[0030] ∀KS:→-consistent (K) ∃global state GK:→-consistent (G)

[0031] Intuitively, extensibility allows for the extension of a consistent set of states to a consistent global state. Any computation in S can be made extensible by adding “dummy” states to S. Therefore, it can be implicitly assumed that any computation is extensible.

[0032] Given a computation →, let ≦ be a relation on global states defined as: G≦H≡∀i: (G_i→i H_i) (G_i≡H_i). It is a well-known fact that the set of →-consistent global states is a lattice with respect to the ≦ relation. In particular, →-glb(G,H) is used for the greatest lower bound of G and H with respect to → (so, →-glb(G,H)_i≡→_i-min (G_i,Hi)). If G and H are →-consistent, then →-glb(G,H) is also →-consistent.

[0033] Given a computation → and a global predicate B, a computation →^cis called a controlling computation of B in → if (1) →→^c, and (2) ∀G:→^c-consistent(G)B(G). This indicates that a controlling computation is a stricter partial order (containing more synchronizations). Further, any global state that may occur in the controlling computation must satisfy the specified global predicate. Thus, the problem of finding a controlling computation is to add synchronizations until all global states that violate the global predicate are made inconsistent.

[0034] In the paper by Tarafdar et al., it was proved that the Off-line Predicate Control is NP-Hard. Therefore, it is important to solve useful restricted forms of the Off-line Predicate Control Problem. Since it is desirable to avoid race conditions, the general problem is restricted by letting B specify the mutual exclusion property.

[0035] Referring to FIG. 2, an illustration of variants of off-line mutual exclusion is provided. The simplest specification for mutual exclusion is: no two critical sections execute at the same time. This corresponds to the semantics of a single exclusive lock for all the critical sections. The corresponding problem can be referred to as an Off-line Mutual Exclusion Problem. This can be generalized to the Off-line Readers Writers Problem by specifying that only critical sections that “write” must be exclusive, while critical sections that “read” need not be exclusive. This corresponds to the semantics of read-exclusive-write locks. Another way to generalize the Off-line Mutual Exclusion Problem is to allow the semantics of independent locks. In this Off-line Independent Mutual Exclusion Problem, no two critical sections of the same lock can execute simultaneously. Finally, critical sections may be associated with the semantics of independent read-exclusive-write locks. This is the Off-line Independent Read-Write Mutual Exclusion Problem. FIG. 2 illustrates the relative generality of the four problems.

[0036] In traditional on-line mutual exclusion, there has been no “independent” variant, since it trivially involves applying the same algorithm for each lock. However, in off-line mutual exclusion, such an approach will not work, since the synchronizations added by each independent algorithm may cause deadlocks when applied together.

[0037] For the practitioner, an algorithm which solves Off-line Independent Read-Write Mutual Exclusion would suffice, since it can be used to solve all other variants. For the purpose of describing the invention in straight-forward terms, however, the simplest off-line mutual exclusion Problem will be described in generalized steps. For each problem, the necessary and sufficient conditions for finding a solution will also be described.

[0038] Off-line Mutual Exclusion is a specialization of Off-line Predicate Control to the following class of global predicates:

[0039] B_mutex(G)≡∀distinct s,t∈G: (critical(s)critical(t))

[0040] where critical is a function that maps a state onto a boolean value. Thus, B_mutexspecifies that at most one process may be critical in a global state.

[0041] Based on the critical boolean function on states, critical sections are defined as maximal intervals of critical states. More precisely; given a critical function on S and a computation→on S, a critical section, CS, is a non-empty, maximal subset on a S_isuch that: (1) ∀s∈CS: critical(s), and (2) ∀s,t∈CS: ∀u∈S_i: s→u→t u∈CS.

[0042] Let CS.first and CS.last be the minimum and maximum states respectively in CS (w.r.t. →_i). Let be a relation on critical sections defined as: CSCS′≡CS.first→CS′.lastCS≠CS′ Thus, orders a critical section before another if some state in the first happened before some state in the second. Note that may have cycles.

[0043] All computations will have the same total order →_ifor each S_i. Therefore, the set of critical sections will not change for each computation. However, the relation will change, in general. For computations →, →^k, and →^c, the relation on critical sections will be denoted as , ^kand ^crespectively.

[0044] Theorem 1 (Necessary Condition) For a computation → of S, and a global predicate B_mutex,

[0045] a controlling computation of B_mutexin → exists has no cycles

[0046] Proof: The contrapositive is proved. Let have a cycle, say CS₁CS₂ . . . CS_mCS₁, (m≧2) and let →^cbe a computation such that →^c. Since →^ccannot have a cycle, at least one of: CS₁.last≯^cCS₂.first, CS₂.last≯^cCS₃.first, . . . , and CS_m.last≯^cCS₁.first must hold. Without loss of generality, let CS₁.last≯^cCS₂.first. Also CS₂.last≯^cCS₁.first (since CS₁CS₂) Since →^cis extensible, s₂can be defined as the maximum state in S₂such that CS₁.last∥^cs₂and s₁as the maximum state in S₁such that CS₂.last∥^cs₁. By extensibility of →^c, →^c-consistent global states G₁and G₂can be found containing {CS₁.last, s₂} and {CS₂.last, s₁} respectively. There are now two cases:

[0047] Case 1: [s₁∈CS₁s₂∈CS₂] In this case B_mutex. (G₁).

[0048] Case 2: [s₁∉CS₁s₂∉CS₂] Since s₁∉CS₁, there are two ways to position s₁: (a) s₁→^cCS₁.first or (b) CS₁.last→^cs₁. In sub-case (a), since CS₂.last≯^cCS₁.first, either CS₂.last∥^cCS₁.first or CS₁.first→^cCS₂.last, which gives s₁→^cCS₂.last. Both possibilities contradict the definition of s₁. This leaves sub-case (b) as the only possibility. Therefore, CS₁.last→^cs₁. Similarly, CS₂.last→^cs₂can be proved. Let H=→^c-glb(G₁, G₂). H contains CS₁.last and CS₂.last and, so, (H). Further, H is →^c-consistent (by the lattice property).

[0049] So in either case, →^cis not a controlling computation of B_mutexin →.

[0050] Theorem 2 (Sufficient Condition) For a computation → of S and a global predicate B_mutex,

[0051] has no cycles a controlling computation of B_mutexin → exists

[0052] Proof: Since has no cycles, all of the critical sections can be arranged in a sequence: CS₁CS₂, . . . Cs_msuch that Cs_i→Cs_ii<j. Let →^cbe defined as (→∪{(CS₁.last, CS_i+1.first)|1≦i≦m−1})⁺, where ( )⁺ is the transitive closure. Clearly →→^c. In the next paragraph, →^cis proved a partial order. Assume that there is a global state G such that B_mutex(G). Let Cs_iand Cs_jbe the two critical sections to which s and t belong respectively. w.l.o.g, let i<j. Therefore, s→^ct, and →^c-consistent(G). Therefore, →^c-consistent(G) B_mutex(G). So →^cis a controlling computation of B_mutexin →.

[0053] The remaining obligation of proof is that →^cis a partial order. To this end, let →^kbe defined as: (→∪{(CS_i.last, CS_i+1.first)|1≦i≦k−1})⁺. The following claim can be made: Claim:∀1≦k≦m: (1)→^kis a partial order, and (2) CS_iCs_ji<j Clearly →^c=→^mand so this claim implies that →^cis a partial order.

[0054] Proof of Claim: (by Induction on k)

[0055] Base Case: Immediate from →=→¹.

[0056] Inductive Case: We make the inductive hypothesis that →^k−1is a partial order, and that CS_i^k−1CS_ji<j. The definition of →^kcan be rewritten as: (→^k−1∪{(CS_k−1.last, CS_k.first)})⁺. First it is demonstrated that →^kis irreflexive and transitive (which together imply asymmetry).

[0057] (i) Irreflexivity: Let s→^kt. There are two possibilities: either s^k−1t or s^k−1Cs_k−1.last.Cs_k.first→^k−1t. In the first case, the inductive hypothesis indicates that ^k−1is irreflexive and so s≠t. In the second case, part (i) of the inductive hypothesis indicates that ^k−1, is transitive, and part (2) of the inductive hypothesis indicates that CS_k.first≯^k−1CS_k−1.last and so s≠t.

[0058] (ii) Transitivity: This is immediate from the definition of →^k.

[0059] Therefore, →^kis a partial order. The second part of the claim is now illustrated. Suppose Cs_i^kCs_j. This implies that Cs_i.first→^kCs_j.lasti≠j. There are two cases: either Cs_i.first→^k−1Cs_j.lasti≠j or Cs_i.first→^k−1Cs_k−1.last Cs_k.first→^k−1Cs_j.lasti≠j. In the first case, we have Cs_i^k−1Cs_jand so by the inductive hypothesis, i<j. In a similar manner, the second case would give i≦k−1k≦j and so i<j.

[0060] In conclusion, the necessary and sufficient condition for finding a controlling computation for B_mutexis that there is no cycle of critical sections with respect to . Further note that, since the proof of Theorem 2 is constructive, it can be used to design a naive algorithm to find a controlling computation.

[0061] The following is an explanation of off-line Readers Writers Problem. Let read_critical and write_critical be functions that map a state onto a boolean value. Further, no state can be both read_critical and write_critical (any read and write locked sate is considered to be only write locked). Let critical(s)≡read_critical(s) write_critical(s). The Off-line Readers Writers Problem is a specialization of the Off-line Predicate Control Problem to the following class of global predicates:

[0062] B_rw(G)≡∀distinct s,t∈G:(write_critical(s) critical(t))

[0063] Given a read-critical function and a write-critical function on S and a computation → on S, we define a read critical section and a write critical section in an analogous fashion to the critical sections that were defined before. Note that, since no state is both read_critical and write_critical, critical sections in a process do not overlap.

[0064] Let be a relation on both read and write critical sections defined as:

[0065] CSCS′≡CS.first→CS′.lastCS≠CS′

[0066] Theorem 3 (Necessary Condition) For a computation → of S, and a global predicate B_rw,

[0067] Proof: The proof is similar to the proof of Theorem 1. Providing the contrapositive: Let have a cycle, say CS₁CS₂ . . . Cs_mCS₁. Without loss of generality, let CS₁be a write critical section. Let →^cbe a computation such that →→^c.

[0068] First, there is at least one critical section in the cycle say Cs_k(where k≠1), such that CS₁.last≯^cCS_k.first and Cs_k.lasts≯^cCS₁.first. To prove this, assume the opposite:

[0069] ∀Cs_k(k≠1): CS₁.last→^cCs_k.first Cs_k.last→^cCS₁.first—(i)

[0070] and prove a contradiction as follows: Cs_mCS₁implies CS₁.last≯^cCS_m.first. Therefore, by (i), Cs_m.last→^cCS₁.first. This allows the definition of j as the smallest integer such that Cs_j.last→^cCS₁.first. CS₁CS₂implies that CS₂.last≯^cCS₁.first. Therefore, j≠2. In particular, Cs_j−1and CS₁are distinct. By the choice of j, Cs_j−1.last≯^cCS₁.first. So, using (i), CS₁.last→^cCs_j−1.first. We now have a cycle: CS₁.last→^cCS_j−1.first (as above), Cs_j−1.first→^cCs_j.last (since Cs_j−1Cs_j), Cs_j.last→^cCS₁.first (by our choice of j), and CS₁.first→^cCS₁.last (by the definition of first and last) This cycle contradicts the fact that →^cis a partial order.

[0071] Since the existence of a Cs_khas been demonstrated such that CS₁.last≯^cCs_k.first and Cs_k.last≯^cCS₁.first, a proof similar to the one in Theorem 1 can be used to show that →^cis not a controlling computation of B_rwin →.

[0072] Theorem 4 (Sufficient Condition) For a computation → of S, and a global predicate B_rw,

[0073] Proof: Consider the set of strongly connected components of the set of critical sections with respect to the relation. Define the relation on strongly connected components as SCCSCC′≢∃CS∈SCC,CS′∈SCC′:CSCS′SCC≠SCC′. It is verifiable that is a partial order. Therefore, it can be linearized to get a sequence of all strongly connected components, say SCC₁,SCC₂, . . . SCC₁such that SCC_iSCC_ji<j. Let →^cbe defined as (→∪{(Cs_i.last,CS_j.first)|Cs_i∈SCC_k,CS_j∈SCC_k+1for some 1≦k≦1−1})⁺. Clearly →→^c. It can be shown that →^cis a partial order along similar lines as the proof of Theorem 2.

[0074] It is shown that →^cis a controlling computation of B_rwin →. Suppose G is a global state such that B_rw(G). Therefore, states s and t can be found such that write_critical(s) and critical(t). Let CS be a write critical section that contains s and let CS′ be a critical section that contains t. Let SCC_iand SCC_jbe the strongly connected components that contain CS and CS′ respectively. SCC_iis distinct from SCC_jsince, otherwise, there would be a cycle in that contains a write critical section. Without loss of generality, let i<j. By the definition of →^c, we have s→^ct and, therefore, →^c-consistent(G). Therefore, →^cis a controlling computation of B_rwin →.

[0075] Note, as before, that the proof of Theorem 4 can be used to design an algorithm to find a controlling computation.

[0076] The following is an explanation of off-line Independent Mutual Exclusion. Let critical₁, critical₂, . . . critical_mbe functions that map an event onto a boolean value. The Off-line Independent Mutual Exclusion Problem is a specialization of the Off-line Predicate Control Problem to the following class of global predicates:

[0077] B_ind(G)≢∀distinct s, t∀∈G:∀l:(critical_i(s)critical_i(t))

[0078] Given a function critical_ion S and a computation → on S, an i-critical section is defined in an analogous fashion to the critical sections that were defined before. Note that the definition allows independent critical sections on the same process to overlap. In particular the same set of states may correspond to two different critical sections (corresponding to a critical section with multiple locks). Let be a relation on all critical sections defined as before.

[0079] Theorem 5 (Necessary Condition)

[0080] For a computation → of S, and a global predicate B_ind,

[0081] Proof: The proof is almost identical to the proof of Theorem 1.

[0082] Theorem 6 (Sufficient Condition) For a computation → of S, and a global predicate B_ind.

[0083] Proof: The proof is along similar lines to the proof of Theorem 4. In this case strongly connected components are taken as before, but utilize the fact that no two i-critical sections may be in the same strongly connected component (otherwise, there would be a cycle of i-critical sections).

[0084] Using similar definitions, the Off-line Independent Read-Write Mutual Exclusion Problem is a specialization of the Off-line Predicate Control Problem to the following class of global predicates:

[0085] B_ind-rw(G)≡∀distinct s, t∈G:∀i :write-critical_i(s)critical_i(t))

[0086] As before, we defined i-read critical sections and i-write critical section (1≦i≦m). Similarly, let → be a relation on all critical selections. The-necessary and sufficient condition is a combination of that of the previous two sections. Since the proofs are similar to the previous ones, we simply state:

[0087] Theorem 7 (Necessary and Sufficient Condition)

[0088] For a computation → of S_iand a global predicate B_ind-rw,

[0089] FIG. 3 shows the algorithm to find a controlling computation of B_ind-rwin →. Since the other forms of mutual exclusion are special cases of B_ind-rw, this algorithm can be applied to any of them.

[0090] The input to the algorithm is the computation, represented by n lists of critical sections C₁, . . . , C_n. For now, to simplify presentation, assume that critical sections are totally ordered on each process. Each critical section is represented as its process id, its first and last states, a type identifier cs_id that specifies the critical_csidfunction, and a flag indicating if it is a write or read critical section. The partial order is implicitly maintained by vector clocks associated with the first and last states of each critical section. The algorithm outputs the →ⁿrelation specified as a list of ordered pairs of states.

[0091] The first while loop of the algorithm builds ordered, a totally ordered set of strongly connected components of critical sections (called scc's from here on). The second while loop simply uses ordered to construct the →^crelation.

[0092] The goal of each iteration of the first loop is to add an scc, which is minimal w.r.t. →, to ordered (where → is the relation on scc's defined in the proof of Theorem 4). To determine this scc, it first computes the set of scc's among the leading critical sections in C₁, . . . C_n. Since no scc can contain two critical sections from the same process, it is sufficient to consider only the leading critical sections. From the set of scc's, it determines the set of minimal scc's, crossable. In then randomly selects one of the minimal scc's. Finally, before adding the scc to ordered, it must check if the scc is not_valid, where not_valid(crossed)≡∃cs₁cs¹∈crossed:cs.cs^—id . . . cs₁.cs_idcs.write_critical. If an invalid scc is found, no controlling computation exists (by Theorem 7).

[0093] The main while loop of the algorithm executes p times in the worst case, where p is the number of critical sections in the computation. Each iteration takes O(n²) since it must compute the scc's. Thus, a simple implementation of the algorithm will have a time complexity of O(n²p). A better implementation of the algorithm, however, would amortize the cost of computing scc's over multiple iterations of the loop. Each iteration would compare each of the critical sections that have newly reached the heads of the lists with the existing scc's, thus forming new scc's. Each of the p critical section, therefore, reaches the head of the list just once, when it is compared with n−1 critical sections to determine the new scc's. The time complexity of the algorithm with this improved implementation is, therefore, O(np). Note that a naive algorithm based directly on the constructive proof of the sufficient condition in Theorem 7 would take O(p²). The complexity has been significantly reduced by using the fact that the critical sections in a process are totally ordered.

[0094] The algorithm has implicitly assumed a total ordering of critical sections in each process. As noted before, however, independent critical sections on the same process may overlap, and may even coincide exactly (a critical section with multiple locks is treated as multiple critical sections that completely overlap). The algorithm can be extended to handle such cases by first determining the scc's within a process. These scc's correspond to maximal sets of overlapping critical sections. The input to the algorithm would consist of n lists of such process-local scc's. The remainder of the algorithm remains unchanged.

[0095] Referring to FIG. 4, in its application to software fault tolerance, the present invention consists of four parts: (A) tracing an execution, (B) detecting a synchronization failure, (C) determining a control strategy, and (D) re-executing under control.

[0096] After determining a control strategy the algorithm used in the present invention determines which synchronizations to add in order to avoid very general forms of mutual exclusion violation. As mentioned before, the other three parts of our scheme have been addressed as independent problems. All of the pieces are at this point put together for a comprehensive look at how race failures (mutual exclusion violations) can be tolerated.

[0097] FIG. 5 illustrates an example of tolerating races in a concurrent execution. The problem of determining a control strategy was placed in a very general model of concurrent execution. Tracing, detection, and controlled re-execution, however, depend greatly on the particular concurrent paradigm. A simple example is best chosen to demonstrate the key issues that will arise in most concurrent paradigms.

[0098] Consider a distributed system of processes that write to a single shared file. The file system itself does not synchronize accesses and so the processes are responsible for synchronizing their accesses to the file. If they do not do so, the writes may interleave and the data may be corrupted. Since the file data is very crucial, it must be ensured that races can be tolerated.

[0099] Synchronization occurs through the use of explicit message passing between the processes. The first part of our mechanism involves tracing the execution. The concern during tracing is to reduce the space and time overhead, so that tolerating a possible fault does not come at too great a cost. In the example, a vector clock mechanism is used, updating the vector clock at each send and receive point. This vector clock needs to be logged for each of the writes to the file (for the algorithm of the present invention). The vector clock values must also be logged for each receive point (for replay purposes). When a write is initiated, and when it returns, the vector clock must be logged. In the example, the writes are typically very long and therefore are performed asynchronously. Thus, execution continues while the write is in progress. In particular, the process may receive a message from another process during its write to the file. Inserting some computation at the send, receive, write initiation, and write completion points can be achieved either by code instrumentation, or by modifying the run-time environment (message-passing interface and the file system interface).

[0100] The second part of our mechanism is detecting when a race occurs. Since message passing is used as the synchronization mechanism, the methods described in a Ph.D. thesis by R. H. B. Netzer, entitled “Race condition detection for debugging shared-memory parallel programs,” University of Wisconsin-Madison, 1991, are particularly applicable. Once a race has been detected, all processes are rolled back to a consistent global state prior to the race. The file is also rolled back to a version consistent with the rolled-back state of the processes. (A versioned file system with the ability to roll back must be assumed.) The section of the traced vector clock values that occur after the rolled-back state is then noted. The section indicates the critical section entry and exit points required by the algorithm. The algorithm would take O(np) time, where n is the number of processes and p is the number of critical sections that have been rolled back. The output of the algorithm is the set of added synchronizations specified as pairs of critical section boundary points.

[0101] FIG. 5 demonstrates a possible scenario. Here the semantics of mutual exclusion correspond to a single exclusive lock. Therefore, the necessary and sufficient condition is that there are no cycles in the critical section graph shown in FIG. 4(b) Applying the algorithm would add synchronizations to give the controlling computation shown in FIG. 5(c).

[0102] The next step is to replay the processes using the logged vector clock values of the receive points. Each receive point must be blocked until the same message arrives as in the previous execution. This is a standard replay mechanism. In addition in this replay, additional synchronizations must be imposed. For example, suppose (s, t) in one of the synchronizations output by our algorithm. The state s is a critical section exit point while t is a critical section entry point. Each of these additional synchronizations is implemented by a control message sent from s and received before t. Thus, at each critical section exit point, the added synchronizations must be checked to decide if a control message must be sent. At each critical section entry point, the added synchronizations must be checked to decide if the process must block waiting for a control message. As in tracing, the points at which computation must be added are the write initiation and completion points, and the send and receive points. Again, this can be accomplished by code instrumentation or run-time environment modification.

[0103] An example has been chosen in which the processes only write to the file. If the processes were to read from the file as well, then that would cause causal dependencies between processes. Then these causal dependencies would have to be tracked as in the tracking for the messages. Another option would be to assume that these causal dependencies do not affect the message communications, in which case, they do not need to be tracked. However, if this approach is taken, it would have to be checked out to determine that the traced computation is the same as the one being replayed. In case of a divergence, the execution would be left to proceed uncontrolled from the point of divergence.

[0104] Whereas the invention has been described with respect to specific embodiments thereof, it will be understood that various changes and modifications will be suggested to one skilled in the art and it is intended to encompass such changes and modifications as fall within the scope of the appended claims.