Towards a fully distributed queue (a new idea is born) - Revisited

Not so long ago I have posted a blog in which I talked about my thesis, more precisely about its beginning. My original idea to study and hopefully come up with a reasonable implementation of a fully distributed queue has taken a slight detour (as these things sometimes do). Instead of studying only distributed queues I ended up looking at the relationship between mutual exclusion algorithms or as they are sometimes called, locking algorithms, and various distributed data structures such as queues, stacks, linked lists and even shared counters. Some types of data structures, such as the shared counters, had more than one implementation, and some of the more complex data structures made use of lower data structures as their building blocks. For example a distributed queue made use of a shared counter.

My thesis work consisted of both theoretical and practical aspects. My analysis of the data structures’ behavior and relationships was based on a complex testing framework which I have developed. The framework, which made use of various open source projects and in particular MantaRay, allowed me to test the performance of various distributed data structures using any of the locking algorithms I implemented.

My supervisor, Prof. Gadi Taubenfeld, suggested that I start with implementing known / existing locking algorithms in order to get some preliminary numbers. Having thoroughly read and researched papers which dealt with distributed mutual exclusion, I have decided to stick to the basics and implement 3 of the more well known and respected algorithms in the field. The algorithms I implemented were Suzuki-Kasami’s Token-based Algorithm, Ricart-Agrawala Permission-based Algorithm and Maekawa’s Permission-based Algorithm.

One of the most challenging aspects of designing and implementing a locking algorithm or a distributed data structure is making sure that the implementation is ‘correct’ and scales well under load. In my next blog I will shade some light on this simple statement which turns out to be a hell of a lot harder than one might expect.