A Programming Model For Optimism

Technological advances are increasing the throughput of most aspects of computing systems. However, latency is being held back by the speed of light, particularly in distributed systems. Optimistic algorithms that guess the results of operations and proceed in parallel with confirmation of the guess are an effective way to hide the latency of slow operations with predictable outcomes. Optimism is used in concurrency control and distributed simulation systems, but is not generally used. Optimistic algorithms are difficult to write because of the necessity for checkpointing, rollback, and dependency tracking. This thesis presents a set of primitives called HOPE that simplifies the expression of optimistic algorithms. HOPE provides primitives to specify, confirm, and deny any optimistic assumption about a future state of the program. Dependence on optimistic assumptions is automatically tracked so that data can be exchanged without regard to the speculative status of the tasks involved.;We begin by defining the principles of optimism, and present some example applications of optimism. The HOPE programming model is presented, using both an informal description of its primitives, and a definition of its formal semantics. We then describe the abstract algorithms for implementing HOPE in a distributed environment, as well as the prototype HOPE system that embeds the HOPE primitives in C using the PVM message passing library. Finally, we introduce the performance characteristics of the prototype HOPE system, and describe future research directions