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 implementation
00089328.pdf
openaccess
624.67 KB
Adobe PDF
8a9ff66c8a428b267ff3afc72fb68d88