Synchronization and communication primitives for Kotlin Coroutines
Traditional concurrent programming involves manipulating a shared mutable state. An alternative to this programming style is the communicating sequential processes (CSP) model, which share data via explicit communication. Kotlin Coroutines is a library that brings this model into the Kotlin language, where processes are represented via coroutines (they are light-weight threads). This way, there are several abstractions required for communication and synchronization between the coroutines, starting from the well-known locks and semaphores, and ending with channels — special producer-consumer structure to transfer the data among coroutines. This project is devoted to developing efficient primitives and adopting them for Kotlin Coroutines.
Lincheck: testing concurrency on the JVM
Lincheck is a practical tool for testing concurrent algorithms in JVM-based languages, which supports both stress-testing and bounded model checking. One of the main advantages of Lincheck relative to popular testing tools such as JCStress is that it provides a declarative way of writing concurrent tests, by specifying all the operations to be examined, their correctness properties, and the number of invocations to be used for each scenario. Roughly, Lincheck generates a series of concurrent scenarios, executes them in either stress-testing or model-checking mode, and checks whether there exists some sequential execution that can explain the results satisfying the specified correctness property. In addition to the above features, Lincheck is the first testing tool to support relaxed data structure semantics, dual data structure designs popular in producer-consumer and coroutine implementations, as well as durable data structures, designed for NVRAM.
Concurrent graph algorithms
Parallel graph processing is a fundamental and well-studied topic in academia in both theoretical and practical aspects. However, some applications, such as social networks analysis and compilers, require these algorithms to be online, thus, to be concurrent. This project aims to build practically efficient concurrent algorithms for different aspects of graph processing, including using multi-queues as priority schedulers for some of the algorithms, or on-line dynamic connectivity problems under edge insertion and deletions. Nowadays, most of the hardware platforms have several NUMA sockets, so it is essential to make all these algorithms NUMA-friendly.