Participant: Alessia Milani
Home Institution: Laboratoire Bordelais de Recherche en Informatique, University of Bourdeaux
Home Country: France
Host: Prof. Panagiota Fatourou
Host Institution: Foundation for Research and Technology - Hellas (FORTH) Institute of Computer Science (ICS)
Host Country: Greece
Start Date: 2012-06-10
End Date: 2012-06-24
Description: Due to the recent proliferation of multicore machines, simplifying concurrent programming has become a necessity, to exploit their computational power. A universal construction is a methodology for automatically executing pieces of sequential code in a concurrent environment, while ensuring correctness. Universal constructions provide concurrent implementations of any sequential data structure: Each operation supported by the data structure is a piece of code that can be executed. Universal constructions provide functionality similar to Transactional Memory (TM).
We are interested in universal constructions that allow for increased parallelism by being disjoint-access parallel. Roughly speaking, an implementation is disjoint-access parallel if two processes that operate on disjoint parts of the simulated state do not interfere with each other, i.e., they do not access the same base objects. Therefore, disjoint-access parallelism allows unrelated operations to progress in parallel. We are also interested in ensuring strong progress guarantees : An implementation is wait-free if, in every execution, each (non-faulty) process completes its operation within a finite number of steps, even if other processes may fail (by crashing) or are very slow.
In a previous work we first proved that designing universal constructions which ensure both disjoint access parallelism and wait-freedom is not possible. We proved this impossibility result by considering a dynamic data structure that can grow arbitrarily large during an execution. Specifically, we considered a singly-linked unsorted list of integers that supports the operations Append(x), which appends x to the end of the list, and Search(x), which searches the list for x starting from the first element of the list. We showed that, in any implementation resulting from the application of a universal construction to this data structure, there is an execution of Search that never terminates.
Some impossibility results, related to ours, have been proved for transactional memory implementations. A discussion on these results is provided in. Universal constructions and transactional memory algorithms are closely related. They both have the same goal of simplifying parallel programming by providing mechanisms to efficiently execute sequential code in a concurrent environment. A transactional memory algorithm informs the external environment when a transaction is aborted, so it can choose whether or not to re-execute the transaction. A call to a universal construction returns only when the simulated code has been successfully applied to the simulated data structure. This is the main difference between these two paradigms. However, it is common behavior of an external environment to restart an aborted transaction until it eventually commits. Moreover, meaningful progress conditions in transactional memory require that the number of times each transaction aborts is finite. Our impossibility result applies to transactional memory algorithms that satisfy this progress property. Disjoint-access parallelism is defined for transactions in a similar way as for universal constructions.
In we also showed how this impossility result can be circumvented, by restricting attention to data structures whose operations can each only access a bounded number of different data items. Stacks and queues are examples of dynamic data structures that have this property. We present a universal construction that ensures wait-freedom and disjoint-access parallelism for such data structures. The resulting concurrent implementations are linearizable and satisfy a much stronger disjoint-access parallelism property than we used to prove the impossibility result. For other dynamic data structures, our universal construction still ensures linearizability and disjoint-access parallelism. However then, instead of wait-freedom, it only ensures lock-freedom which guarantees that, in every execution, some (non-faulty) process completes its
operation within a finite number of steps. An interesting question that is not answered is whether we can circumvent the impossibility result of by relaxing the notion of disjoint-access parallelism. An appealing way to do so is by allowing processes that execute operations to access a restricted set of common base object even in case they operate on disjoint parts of the data structure. In particular, we consider implementations where processes can access a shared timestamp object even if they do not conflict on some data item. Our goal is to study whether such implementations can be both wait-free and disjoint-access parallel in respect of the remaining set of base objects.