home Anil Madhavapeddy, Professor of Planetary Computing  

Concurrent revisions for OCaml

This is an idea proposed in 2013 as a Cambridge Computer Science Part II project, and has been completed by Dimitar Popov. It was supervised by Anil Madhavapeddy.

The biggest challenge when using parallel programming is typically how to keep track of the side effects of computations that are executed in parallel and that involve shared mutable state. Traditional methods for dealing with this issue often limit concurrency, do not provide sufficient determinism and are error prone. Ideally, we would like a concept where all conflicts between parallel tasks are resolved deterministically with minimized effort from the programmer. This project aims to design and build a library for OCaml that implements the concept of concurrent revisions.

Concurrent revisions as initially proposed highlight these design choices:

  1. Declarative data sharing: the user declares what data is to be shared between parallel tasks by the use of isolation types
  2. Automatic isolation: each task has its own private stable copy of the data that is taken at the time of the fork
  3. Deterministic conflict resolution: the user specifies a merge function that is used to resolve write-write conflicts that might arise when joining parallel tasks. Given that this function is deterministic, the conflict resolution is also deterministic.

In this framework the unit of concurrency are asynchronous tasks called revisions. They provide the typical functionality for asynchronous tasks - the user can create, fork and join them. This removes the complexity of synchronization out of the tasks themselves and gathers it into a single place; the merge function.

A key outcome is to improve our understanding of the tradeoffs both between the different paths that can be chosen during the implementation of this library and the more traditional means of concurrent programming. We will design an evaluation of the differences between the API of the original concurrent revisions limplementation written in C# and the more functional style of one built in OCaml.

The project was successfully completed, with the major decision being whether or not to switch to a monadic API vs a direct-style one with better lower-level control.

Related Reading

Links

The dissertation PDF is available publically along with the source code to the prototype library which implemented a logging and chat server to demonstrate the use of concurrent revisions.

# 1st Jan 2013   iconideas distributed fp idea-done idea-medium multicore ocaml

Related News