Enhancing Concurrency Through Optimism: A Reason for HOPE

Optimism is a powerful technique for increasing concurrency. To date, use of optimism has been restricted to specialized systems due to the difficulty of writing optimistic programs. In this paper, we define optimism as any computation that uses rollback. We justify this definition, and describe how optimism can be used to increase concurrency. We then examine several well-known optimistic algorithms in this context. We conclude by presenting HOPE: our model of optimistic computation built upon these notions. 1 Introduction An optimistic computation is one that proceeds based on an optimistic assumption. An optimistic assumption is a property of a future state that has yet to be verified. If the optimistic assumption is found to be true, then the optimistic computation is retained, otherwise it is rolled back and discarded. Any kind of assumption can be made, as long as a reliable method exists for checking that the assumption was correct. Optimistic algorithms have been used for fau..