About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
PODC 1991
Conference paper
Replay, recovery, replication, and snapshots of nondeterministic concurrent programs
Abstract
The problem of replaying computations of non-deterministic concurrent programs arises in contexts such as debugging and recovery. We investigate the problem for an abstract model of concurrency, which generalizes dataflow networks, processors with shared variables, and logic programming models of concurrency. We say that nondeterminism is visible if the state is determined, up to some (appropriately defined) notion of equivalence, by the external behavior. We show that if nondeterminism is visible then replay is achievable using a. one-step lookahead sequential simulation algorithm. If the program has an additional monotonicity property called stability then recovery is possible without simulating the original computation, by restarting the program from a. certain easily constructed state. Also, for stable programs with visible nondeterminism, a process composed of identical parallel processes has the same external behavior as each of its components. Hence high crash-failure resilience is achievable by simple process replication. For such programs there is also an easy solution to the asynchronous snapshot problem. Stability holds for certain concurrent logic/constraint programming languages. We describe an efficient method for transforming a given stable concurrent logic/constraint program to an equivalent one with visible nondeterminism. The transformation has acceptable execution overhead, thus it could be employed in a practical realization of the proposed methods.