AbstractsComputer Science

Two well-known mechanisms for automatically executing sequential code segments in aconcurrent environment are universal constructions and software transactional memory.They both have the same goal of simplifying the task of parallel programming. A universalconstruction is a mechanism which takes as input the sequential code and executes itin a concurrent environment. Software transactional memory (STM) employs transactionsto avoid conflicting accesses to common data (known as data items or transactional variables).A transaction may either commit, in which case it appears as if it has been executedat a single point in time, or abort, in which case it appears as if it is never executed. Noticethat if a transaction commits, then its updates to data items become visible, otherwise, if itaborts, all its changes are discarded.In this thesis, we study how to achieve increased concurrency while designing suchmechanisms, without sacrificing correctness and progress. One well-studied technique forenhancing concurrency is ensuring a property called disjoint-access parallelism. Roughlyspeaking, disjoint-access parallelism guarantees that processes operating on different partsof an implemented object do not interfere with each other. Thus, disjoint-access parallelimplementations allow for increased parallelism.Wait-freedom is a well-known progress property which ensures that each process completesits execution, even when other processes run at arbitrary speeds or crash. Waitfreedomis highly desirable because implementations ensuring this property are highly faulttolerantand usually ensure bounds on the number of steps executed before an implementedoperation responds.In this thesis, we prove that it is not possible for a universal construction to achieveboth disjoint-access parallelism and wait-freedom; this impossibility result holds for STMas well. Specifically, we identify a natural property of universal constructions and provethat there is no universal construction (with this property) that ensures both disjoint-access parallelism and wait-freedom. Our impossibility proof is obtained by considering a dynamicdata structure that can grow arbitrarily large during an execution. This impossibility resultcan be beaten if we focus on data structures that have a bound on the number of piecesof data accessed by each operation they support. For this setting, we present a universalconstruction that ensures both wait-freedom and disjoint-access parallelism.We further introduce and study weaker versions of disjoint-access parallelism, whichstill however allow for increased parallelism. Motivated be the way current STM algorithmwork, we introduce timestamp-ignoring disjoint-access parallelism, which allows operationsoperating on different parts of an implemented data structure to proceed in parallel,except for accesses to a timestamp object. A timestamp object allows a process to know the“time” at which it accesses the object, relative to accesses by other processes (on the sametimestamp object); specifically, a process is able to determine…