Nonblocking data structures based on message-passing concurrency
|
Supervisor |
|
|
Suitable for |
MSc in Computer Science
|
Abstract
Developing efficient concurrent data structures is nontrivial, and requires several interesting new programming techniques. In the context of shared-variable concurrency, researchers developed such data structures, often called nonblocking algorithms, which avoid using locks (expressed by the synchronized keyword in Java) and perform well even when many threads attempt to use the data structures at the same time. The goal of this project is to revisit these data structures designed for shared-variable concurrency, especially those found in Herlihy and Shavit's book "The art of multiprocessor programming", and to build corresponding data structures based on asynchronous message-passing passing or Actor model, which is supported by Erlang or Scala. The built data structures will be analysed theoretically (by proving their linearizability) or empirically (by measuring their performance) or both.
Prerequisites:
Although it is not required, it is desirable that a student carrying out this project took the Concurrent Programming course before.