Transactional Data Structures

Concurrent programming is difficult and the effort is rarely rewarded by fasterexecution. The concurrency problem arises because information cannot passinstantly between processors resulting in temporal uncertainty.This thesis explores the idea that immutable data and distributed concurrencycontrol can be combined to allow scalable concurrent execution and makeconcurrent programming easier. A concurrent system that does not impose a globalordering on events lends itself to a scalable distributed implementation. Aconcurrent programming environment in which the ordering of events affecting anobject is enforced locally has intuitive concurrent semantics.This thesis introduces Transactional Data Structures which are data structuresthat permit access to past versions, although not all accesses succeed. Thesedata structures form the basis of a concurrent programming solution thatsupports database type transactions in memory. Transactional Data Structurespermit non-blocking concurrent access to familiar abstract data types such asdeques, maps, vectors and priority queues. Using these data structures aprogrammer can write a concurrent program in C without having to reason aboutlocks.The solution is evaluated by comparing the performance of a concurrent algorithmto calculate the minimum spanning tree of a graph with that of a similaralgorithm which uses Transactional Memory and by comparing a non-blockingProducer Consumer Queue with its blocking counterpart.Kimberley JarvisTransactional Data StructuresDoctor of PhilosophyThe University of Manchester11 November 2011