CSIE52400 Distributed Systems, Fall 2004
Term Project
A Distributed Shared Set System
A set is a collection of unordered data items. Sets are useful building blocks for shared information repository in distributed systems. The goal of this programming project is to understand the concepts related to the replicated shared data structures and their consistency, the quorum systems to implement such replicated systems, and the pros and cons regarding the performance in terms of the error rate (i.e., degree of consistency). To achieve the goal, we will implement a distributed shared set system that is replicated over several replica servers.
The main concern in a replicated system is to keep the replicas consistent. One approach to maintain the consistency is to use a quorum-based protocol. Let n be the size of the set of the system of replicas, i.e., there are n replica servers in the set S. A quorum system over S can be described as follows.
- Use voting among n servers.
- To read, a client must assemble a read quorum, an arbitrary collection of any Nr servers or more to proceed.
- To update, a write quorum of at least Nw servers is required.
- The read/write quorum must satisfy:
- Nr + Nw > n
- Nw > n/2
Read the lecture note on Consistency and Replication for more details.
The system will consist of a registrar (coordinator), a set of n >= 4 replica servers, and at least two client processes that want to access the shared data sets. The role of registrar is to keep the list of server processes (in the form of IP address and port number) and to distribute the list to the clients whenever it is requested. The registrar runs as a \well-known" server on a well-known port at a designated machine. Each client provides an interface to the user, such as getting an input data to add to the set and outputting to the user the values that are returned by reading the set. For simplicity, assume that there is only one shared set M. In the following, we elaborate on each of the three components.
Server Program
When a server process starts executing, it registers itself to the registrar server. This operation is called register of the server to the replica system. As the results of register operation, the replica server will receive from the registrar, a unique ID and the current value of the shared set M. Because we assume to have only one shared set, the replica server creates its local replica of the set M. And then waits for arrival of requests from a client process.
Client Program
When a client process starts executing, it requests the registrar the list of the replica servers. This operation is called getList. As the result of getList operation, the client will receive the entire list of replica servers and the system parameters Nr and Nw from the registrar. Then it starts performing a sequence of addElem, deleteElem, testElem and readSet operations. (You can write a simple interactive user interface in here.)
Registration Program
The client process needs to know of server processes in the replica system. This information is maintained and provided by the registrar server. Another important information provided by the registrar is the read and write quorum sizes.
Test your system by experimenting different quorum sizes for different runs of the programs.
Due date: Jan 19, 2005
Back to CSIE52400 homepage.