Wednesday, July 28, 2010

A kind of roadmap

What is coming

I am currently trying to explain the workings of the non-blocking linked list as described by Timothy Harris using a state based approach. I have understood the algorithm and of course the problem is defining the correct state, but I am nearly there. From there on, I will move to doubly-linked lists with the complete set of operations (search, delete, insert).

Departing from the usual operations

From there I will try to trim down the doubly-linked structure to support only the following non-blocking operations: find, move from anywhere to the end and prepend. This is the main ingredient for constructing a non-blocking LRU structure that will make it easier to implement non-blocking variations of some popular cache-management algorithms. I am not totally convinced that such a concept is viable but even if I fail, at least I will have gained some wisdom out of it.

The end of the trail

I am really excited about lock-free data structures but there has to be an application domain in sight to give one the focus he needs for implementing something useful. In my case, graph databases are the stuff and I plan, if my work comes to fruition to offer any interesting solutions that crop up, as a library, to the public domain. I only hope that the guys over at neo4j or infogrid are interested in taking a look at my work.

No comments:

Post a Comment