Reversible Concurrent and Distributed Algorithms

The aim of this PhD research is twofold. First, the DC will study what it means to reverse and how to reverse concurrent (e.g., non-blocking algorithms with compare-and-swap) and distributed algorithms (e.g., atomic commit and leader election). The DC will first work with DC 2 to develop a notation for reversible concurrent and distributed programs, and then focus on the algorithmic aspects. A toolbox of concurrent and distributed algorithms for both the message passing and shared memory approach will be assembled, and example algorithms will be implemented in the reversible language with concurrency and distribution developed by DC 2.

1) Notation for concurrency and distribution features of reversible algorithms; 2) Reversible versions of relevant concurrent and distributed algorithms; 3) Library of implemented concurrent and distributed algorithms.

M15, UNIBO, I. Lanese, language extension with shared memory concurrency; M22, AGH, I. Ulidowski, extend the algorithm notation of DC 4 with concurrency and distribution; M28, TOK, S. Yuen, concurrency and distribution support.