Today on Twitter, an informal survey is making the rounds on the experiences of software developers who came to the field from “non-traditional”, that is, non-CS backgrounds. I’m not sure if I should consider myself the target audience for the survey: on one hand, I do have a couple of “traditional” CS degrees by now, and I’m in mainstream CS academia; on the other hand, I didn’t set out to study computer science when I started college (and certainly didn’t consider doing so prior to college, either), and I was a music major for two years before I added a second undergrad major in CS. I did go ahead and fill out the survey, and I thought I’d also share my answers here. I’m curious to hear from others whose experiences are like mine.
Suppose we want to write a program in which two threads, say, t1 and t2, each contribute a Boolean value, either
False, to a shared result. If both threads write
True, we want the result to be
True; if either writes
False (or if both do), then we want the result to be
False. That is, we want the shared result to be the outcome of a logical “and” operation.
Let’s further suppose that we want the threads to be able to run in parallel, with their writes arriving in arbitrary order, and we want to be able to guarantee a deterministic result in spite of parallel execution. Sounds like a job for LVars!
Update (February 19, 2014): I’ve updated the links in this post to point to code that runs against the 1.1.2 release of LVish.
I’ve just posted a draft of my thesis proposal, which, barring disaster, I’ll be presenting to my research committee next Friday. To spill the beans, here’s my thesis statement:
Lattice-based data structures are a general and practical foundation for deterministic and quasi-deterministic parallel and distributed programming.
Update (November 30, 2013): I updated this post to reflect some of my current thinking on threshold reads for CRDTs and why I think high-water-mark reads aren’t necessarily the way to go.
One way in which CRDTs differ from LVars is that some CRDTs support non-monotonic operations. For instance, OR-Sets and 2P-Sets support removal of elements, while PN-Counters can count down as well as up. Combining threshold reads with non-monotonic operations like removal of elements from a set would seem to pose a problem for determinism. If only monotonic operations are allowed, as is the case for LVars, then the answer to the question of whether or not a given threshold read will unblock is the same from run to run (although it may unblock at different times, depending on scheduling). But if the state of the data structure being queried were allowed to move both up and down in a lattice, then that would no longer be the case. For instance, if a read were thresholded on an element that was added to and later removed from a set, then it might block forever, or not, depending on whether the read ran after or before that element’s removal. Hence some schedule nondeterminism would be exposed.
Earlier this week, I gave a talk on LVars at RICON West, a distributed systems industry conference. It covered a lot of the same material as my talk at FHPC last month, but since my speaking slot at RICON was a little longer, I used the extra time to try to explain why a programming languages academic was speaking at a distributed systems industry conference, anyway. This post covers some of the same material in written form.
The short version: The mathematical framework of conflict-free replicated data types that distributed systems researchers have developed for reasoning about and enforcing the eventual consistency of distributed replicas is almost exactly the framework that we use in our own work on LVars for reasoning about and enforcing the determinism of parallel computations.
Update (December 13, 2013): A video of my RICON talk is now available. Thanks to everyone at RICON for being an amazing audience for this talk!