Deterministic Synchronization of Multi-Threaded Programs with Operational Transformation

Today's mainstream programming language concepts originate from a time when processes were executed in a single thread and the outcome of computation was deterministic. To deal with multi-threaded execution synchronization mechanisms have to be used to restrict parallel execution to a point where the program produces correct results for all possible interleaving executions. This is constantly leading to deadlocks and race conditions, i.e. undesired non-deterministic behavior. In this paper, we propose a new set of synchronization primitives, Spawn and Merge, that yield deterministic program execution for multi-threaded programs. This means that there are no race conditions when using this synchronization technique and deadlocks can be avoided right away. Concurrent access to data structures is resolved using operational transformation. Using two example scenarios we show how these synchronization primitives can be used and that they are equivalent to semaphores. Furthermore, we evaluate our framework by implementing a network simulator. We show that despite a constant overhead, the performance is comparable to using standard synchronization primitives while yielding deterministic results.