Indiana University Bloomington

School of Informatics and Computing

Computer Science Program










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

Lindsey Kuper, Ryan Newton
(Oct 2012), Pages 60
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:
  • PDF (551 KBytes)

There is help available if you want further information about the available file formats and software to display and print these files.

Return to the Technical Report Index

Valid HTML 4.01!