Parallel programming is notoriously difficult. A fundamental reason for this difficulty is that programs can yield inconsistent answers, or even crash, due to unpredictable interactions between parallel tasks. But it doesn't have to be this way: deterministic-by-construction programming models offer the promise of freedom from subtle, hard-to-reproduce nondeterministic bugs in parallel code.
A common theme that emerges in the study of deterministic-by-construction systems --- from venerable models like Kahn process networks, to modern ones like the Intel Concurrent Collections system and Haskell's monad-par library --- is that the determinism of the system hinges on some notion of monotonicity. In fact, it's no coincidence that the same principle of monotonicity that CRDTs leverage to ensure eventual consistency in distributed systems can also be put to work in deterministic-by-construction parallel programming.
In this example-driven talk, I'll introduce LVars, which are data structures that enable deterministic parallel programming. LVars generalize the single-assignment variables often found in deterministic parallel languages to allow multiple assignments that are monotonically increasing with respect to a user-specified lattice of states. LVars maintain determinism by allowing only monotonic writes and "threshold" reads to and from shared data. We'll look at examples of programming in an LVar-based parallel language that is provably deterministic, and we'll explore the connection between LVars and CRDTs.
Lindsey Kuper is a Ph.D. candidate in the Programming Languages Group at Indiana University, where she studies the foundations of deterministic parallel programming. She's a recidivist Mozilla Research intern and contributor to the Rust programming language, and a summer 2013 Hacker School resident. She blogs at composition.al.