Optimistic Program Transformations
Original Publication Date: 1985-Nov-01
Included in the Prior Art Database: 2005-Feb-19
Programs initially written as serialized computations can be automatically converted to synthesize a distributed protocol in which certain of the serial computations can be scheduled in parallel, even though some computations may depend on other computations. This end is realized by applying optimistic transformations when the effect of one computation on another computation can be guessed with high probability. If the guess is wrong, then the computation is undone. Because the probability of a correct guess is high, there is an overall performance gain achieved by the increased parallel processing. In applying the optimistic transformations, a program must be distributed over multiple processors. Hence, for centralized systems, a distributed implementation of the database must be derived.