Theory VS. Practice

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….

One of the first distributed mutual exclusion algorithms I worked on was proposed by Glenn Ricart and Ashok K. Agralawa. In their paper, “An optimal algorithm for mutual exclusion in computer networks”, they proposed an algorithm which has been around for more than a decade and many modern algorithms were built based on it.

Imagine my surprise when I found a flaw in the algorithm! I was able to show that under certain conditions the algorithm deadlocks. When the algorithms deadlocked it was not possible to acquire mutual exclusion. Fixing the algorithm involved strategically using a semaphore to prevent 2 lines of code from happening at the same time. This sounds simple enough but locating the problem which only happened under heavy load (more than 20 processes using the algorithm at the same time) took time and patience. Anyhow, I am planning on releasing my test-bed and all of my implementations in the near future. When that happens, I will make sure to point out the modifications I made to the algorithm.