Academic

Last week in my blog I wrote a bit about the progress of my thesis. This week I want to share with you something interesting I found. As I have mentioned before, a large portion of my thesis was practical in the sense that it involved a lot of coding. I chose a more practical approach because I feel that it is much easier to validate claims made by other researchers that way.

I have studied and implemented quite a bit of existing mutual exclusion algorithms, and one of the things I came to realize is that a lot of them had flaws (at least in the original publication) despite a lot of effort to minimize mistakes. For example, a well known algorithm first proposed by Mamuro Maekawa stipulated that it is possible to achieve mutual exclusion using only C*SQRT(N) messages. Where N is the number of participating processes and C is a constant between 3 and 5. Later on this claim was disproved by Ye-In Chang . Chang showed that in some cases the algorithm only works with N messages. Oops….

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.