Two LVars papers

Greetings from surprisingly sunny Portland, Oregon:

The last time I was at Random Order, it was 2008 and I knew a lot less about lattices.

I have one new publication and one new draft paper to announce!

LVars, original flavor

First, I’m happy to announce that “LVars: Lattice-based Data Structures for Deterministic Parallelism” will appear at FHPC ‘13. (That’s a link to the most recent draft; I’ll replace it with a camera-ready version in the next few days.)

This paper marks a number of firsts for me. Aside from being my first primary-author publication and my first paper with my advisor, Ryan, it will be the first peer-reviewed published work on LVars. We’ve been working on getting this paper published for about a year, during which it’s been rejected three times.

Over that same time period, I’ve given talks about LVars in Denmark, Italy, Germany, and various places in the US; to programming languages people, compilers people, and distributed systems people; to Hacker School students and to academic researchers. But when I’ve gotten to the “where to find out more” bit at the end of all these talks, I’ve never had a proper publication to refer anyone to – just unpublished drafts and tech reports that haven’t undergone peer review. So it’s a great relief to finally get this first paper out there.

[“LVars: Lattice-based Data Structures for Deterministic Parallelism”]:

LVars, freezable

Second, I’m excited to announce a new draft, “Freeze After Writing: Quasi-Deterministic Parallel Programming with LVars and Handlers”, that Ryan and I co-authored with Aaron Turon and Neel Krishnaswami. I can’t say enough good things about working with Aaron and Neel – we started work on this paper around January, but their advice, feedback, and support have been of great help to the LVars project as a whole since well before that, so I’m especially happy to have joined forces for this stage of the work.

In this paper, we investigate loosening the usual determinism guarantee of LVars – which says that programs are guaranteed to produce the same result on every run – to a quasi-determinism guarantee, which says that programs are guaranteed to either produce the same result or raise an exception. In exchange for giving up full determinism, we gain the ability to make exact observations of the contents of an LVar, which involves freezing the LVar so that it can’t be updated again. It might just be that I’ve been reading a lot of Ted Chiang lately, but there seems to be a pretty cool uncertainty principle at work: we can trade certainty about the outcome of an LVar computation for certainty about the contents of an LVar at a point during the computation.

We also extend the LVars model by adding event handlers. Event handlers allow us to attach callback functions to an LVar that run whenever an update to the LVar occurs that we’ve marked as being an update of interest. Handlers and freezing can be used either apart or together (and only freezing weakens the determinism guarantee), but using them together enables a particularly useful style of programming with LVars. I’ll have more to say about this in a future post, but for now, the details are in the paper.

Comments welcome!

Update (October 3, 2013): “Freeze After Writing” was accepted at POPL 2014! I’ve written a bit more about it in a new post.