Efficient Concurrency Control for Libraries of Typed Objects

Concurrency control algorithms use a conflict detection strategy to determine operations that have to be delayed to provide a correct serialization order. To keep the cost of detecting conflicts feasible, most algorithms employ rather crude strategy that sometimes delays operations when in reality they could proceed concurrently. In an object oriented system where calls to objects can be nested this problem is exacerbated by the fact that a concurrency control decision is made at each level in the calling hierarchy. In this dissertation we address concurrency control issues in object oriented systems. We develop a model of execution for operations on objects, drawing on similar models developed for database systems. We propose a new serialization algorithm that keeps a partial history of operations at each site, and exploits semantic knowledge of operations to achieve a finer granularity of conflict detection. Conflict detection is based on user supplied conflict predicates, thus giving the user the option of fine grained concurrency control and the responsibility for the level of cost of the conflict detection strategy. We then show how to implement the algorithm in a distributed system where sites can fail and recover independently. Finally, we explore techniques to reduce the message overhead and latency for the algorithm in a distributed system