Abstract

Concurrent programming is difficult and the effort is rarely rewarded by faster
execution. The concurrency problem arises because information cannot pass
instantly between processors resulting in temporal uncertainty.

This thesis explores the idea that immutable data and distributed concurrency
control can be combined to allow scalable concurrent execution and make
concurrent programming easier. A concurrent system that does not impose a global
ordering on events lends itself to a scalable distributed implementation. A
concurrent programming environment in which the ordering of events affecting an
object is enforced locally has intuitive concurrent semantics.

This thesis introduces Transactional Data Structures which are data structures
that permit access to past versions, although not all accesses succeed. These
data structures form the basis of a concurrent programming solution that
supports database type transactions in memory. Transactional Data Structures
permit non-blocking concurrent access to familiar abstract data types such as
deques, maps, vectors and priority queues. Using these data structures a
programmer can write a concurrent program in C without having to reason about
locks.

The solution is evaluated by comparing the performance of a concurrent algorithm
to calculate the minimum spanning tree of a graph with that of a similar
algorithm which uses Transactional Memory and by comparing a non-blocking
Producer Consumer Queue with its blocking counterpart.