Semantics of Optimistic Computation

We address the issue of deriving a semantically equivalent optimistic computation from a pessimistic computation by application-independent transformations. Computations are modeled by program dependence graphs (pdgs). The semantics of a computation is defined by a mapping from an initial state to a final state, and is realized by a graph rewriting system. Semanticspreserving transformations are applied to the pdgs of the pessimistic computation to produce an optimistic version. The transformations result from guessing data values and control flow decisions in the computation. We use our transformations to derive an optimistic version of fault tolerance based on message logging and checkpointing. The transformations yield an optimistic version similar to optimistic fault tolerance algorithms reported in the literature, although additional application-dependent transformations are necessary to produce a realistic optimistic implementation. 1 Introduction Optimistic computations use gu..