Skip navigation

Monthly Archives: July 2010

After reading a paper by Maurice Herlihy on transactional boosting, i wrote down the example mentioned in the paper.  The concept is quite simple, given a concurrent data structure and some “regularity” conditions (commutativity and inverses) you can create a high-level transactional data structure. The advantage is that instead of having crude read/write sets to do conflict checking, you have higher level “abstract locks” that can do the conflict detection/checking at the method invocation level.

You should go over the paper and the code to see what this means, but it should be easy to understand with the working example. The higher level idea is instead of saving a whole snapshot of the object and restoring it in case of an abort, you just specify “what” needs to done (hence the undo action) in case of an abort. So in the case of an insert, the appropriate undo is a remove.

Download the code for the example here LINK