Solving Distributed Dictionary Problem
In this research project we are supposed to solve the dynamic
version of the famous Dictionary Problem. The dictionary problem is explained in
detail by the paper 'Efficient Solutions to the Replicated Log and
Dictionary Problems' by Gene T.J. Wuu and Arthur J. Bernstein.
In essence you have many distributed systems sitting in different geographical areas and
they are communicating through a network.
Each system is capable of performing
operations on an imaginary 'centralized' database, and the only
requirement is that each system must hold consistent global view relative to one
Putting it in a simpler way, a system can add or delete a word from its
'dictionary' which is stored in its local storage. Once I do something
I need to inform everybody else so that they can do the same.
Each system is
multi-threaded to enable maximum efficiency and concurrency. However the systems
need to have concurrency control so that no system would have more than one
thread enter its critical section simultaneously.
Basically our job is to
implement a 'quorum' algorithm, many of which have been proposed by
many papers. We need to take care of deadlocks, a new node joining, an existing
node leaving, and mutual exclusion.
After extensive searching and evaluating, we
found that Maekawa's A N^(1/2) Algorithm for Mutual Exclusion in
is effective and relatively easy to implement. After
spending some time we correctly implemented the whole system: A node can join or
leave anytime it feels like without disrupting the updating of information at
How about a big hand for the brains!