Consistency verification in transaction-based optimistic steering of distributed computations

Abstract

We present an optimistic approach for consistent, interactive steering of distributed computations. In contrast to conservative approaches, the optimistic steering approach assumes that next steerable points are consistent and invokes steering updates without concern for the state of any other process. This approach is expected to perform well since it eliminates the need for blocking processes. Furthermore, we introduce a novel transaction-based computation model. We view the local computation of a process as a sequence of local transactions and a distributed computation as a set of partially ordered global transactions. This abstraction not only gives users a simple and high-level view of distributed computation, but also simplifies reasoning about consistency problems by reducing the amount of information to be handled. Using the Higher KdV (HiKdV) equation simulation program, we evaluate the performance of the optimistic steering approach. Our experiments show that when the percentages of consistency on the first attempt are large enough, the optimistic approach will achieve better performance; otherwise, the conservative approach will be better.

Keywords:

• Causality
• Consistency
• Interactive steering
• Optimistic steering
• Vector time

Keywords:

• 68M14
• 68M20
• 65Y05

Acknowledgements

This work is supported by the National Science Foundation under Grant No. 9996082. The author would like to thank several people who have contributed to the Pathfinder system: Eileen Kraemer, Delbert Hart, David Miller, Arumugaraja Selvaraj, Yin Xiong, Brandon Kohn, Navin Gupta, and Himabindu Vuppula.