Indiana University Bloomington

School of Informatics and Computing

Technical Report TR702:
A Lattice-Theoretical Approach to Deterministic Parallelism with Shared State

Lindsey Kuper, Ryan Newton
Unknown Date, Pages 60
Abstract:
We present a new model for deterministic-by-construction parallel programming that generalizes existing single-assignment models to allow multiple assignments that are monotonically increasing with respect to a user-specified partial order. Our model achieves determinism by using a novel shared data structure with an API that allows only monotonic writes and "threshold" reads that block until a lower bound is reached. We give a proof of determinism for our model, discuss ways to express existing deterministic parallel models using it, and describe how to extend it to support a limited form of nondeterminism that admits failures but never wrong answers.

Available as: