SYNTHESIZING DISTRIBUTED AND PARALLEL PROGRAMS THROUGH OPTIMISTIC TRANSFORMATIONS.

Abstract

A programming methodology for synthesizing efficient distributed and parallel implementations of serial programs by applying correctness-preserving program transformations is proposed. One particular family of such program transformations, called optimistic transformations is introduced. Optimistic transformations allow a logically serial sequence of computations C1; C2 to be executed in parallel whenever C1's effect on C2 can be guessed in advance with high probability. If the guess is wrong, C2 will have to be undone, but if the probability of a correct guess is sufficiently high, the losses due to undoing computations will be compensated by performance gains due to increased parallelism. Three examples of guesses which lead to optimistic transformations of practical value, namely, that multiple iterations of a loop will not conflict, that exceptional program conditions will not occur, and that machine failures will not occur are given. The practicality of the approach is demonstrated by synthesizing a distributed version of a transaction-processing program from a serial program to which one can apply first a data distribution transformation, and then three optimistic transformations based on the three guesses described above. The distributed transaction-processing program synthesized in this way is shown to be an improved-response-time version of the classical distributed two-phase commmit protocol.