Solving Distributed Dictionary Problem
Amazon 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 another.
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 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 another.
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 Decentralized Systems 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 each node.
How about a big hand for the brains!
