OOPSLA Day 2: David Ungar — Everything You Know (About Parallel Programming) Is Wrong

I should hope so.

This was the afternoon’s first major talk. David Ungar from IBM Research first demonstrated that the tragedy of Romeo & Juliet comes from a race condition (if only he had waited for news from the Friar).

That was excellent, but the real premise of his talk was that there is a fundamental tension between correctness and synchronization in manycore and the scalable solution (he asserts) is to eliminate synchronization. He proposed a few names for this type of programming model : anti-lock or “race and repair.”

This reminds me (and at least one questioner in the audience) of the application- or web-level concept of “eventually consistent.”

The bulk of the talk was a discussion of his experiments with a programming problem (a slightly-more-complicated version of hash table insert) with various techniques that trade off correctness with performance. What he showed (at least in this one experiment) was that he could get better performance from a “race and repair” technique than he could get from compare-and-swap.

He tentatively proposes that probabilistic data structures and algorithms, in which correctness is a spectrum that can be traded with performance, is a new field of study.