Turning Nondeterminism into Parallelism

Nondeterminism is a useful and prevalent concept in the de-sign and implementation of software systems. An important property of nondeterminism is its latent parallelism: A non-deterministic action can evaluate to multiple behaviors. If at least one of these behaviors does not conflict with concur-rent tasks, then there is an admissible execution of the ac-tion in parallel with these tasks. Unfortunately, existing im-plementations of the atomic paradigm—optimistic as well as pessimistic—are unable to fully exhaust the parallelism potential of nondeterministic actions, lacking the means to guide concurrent tasks toward nondeterministic choices that minimize interference. This paper investigates the problem of utilizing paral-lelism due to nondeterminism. We observe that nondeter-minism occurs in many real-world codes. We motivate the need for devising coordination mechanisms that can utilize available nondeterminism. We have developed a system fea-turing such mechanisms, which leverages nondeterminism in a wide class of query operations, allowing a task to look into the future of concurrent tasks that mutate the shared state during query evaluation and reduce conflict accord-ingly. We evaluate our system on a suite of 12 algorithmic benchmarks of wide applicability, as well as an industrial application. The results are encouraging