Semantics of optimistic computation

The derivation of a semantically equivalent optimistic computation from a pessimistic computation by application-independent transformations is discussed. 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. Semantics-preserving transformations are applied to PDGS of the pessimistic computation to produce an optimistic version. The transformations result from guessing data values and control flow decisions in the computation. The transformations are used 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 implementatio