Freelancer

Description

The objective of the project is to implement a simple replicated database management system (DBMS)
using C and one of the technologies (e.g. semaphores, fork, sockets and/or RPC).
The DBMS must be implemented as a collection of distributed processes.
Each process is assigned a unique numeric ID (not consecutive) and each process knows about the
existence of any other process. Let us assume that the processes IDs can be ordered in an array (pi) such
that pi < pi+1. You can hardcode this information in your implementation.
0 5 15
insert:
<key=2; value=5>
new data: <key=2; value=5>
query:
<key=2; value=?>
Figure 1: Insert and query for key 2.
Your DBMS must store mappings (key; value) where both elds are 32bits integers. The database acts
like a dictionary: a client searches using a numerical key and obtains as result the data that it wants.
Mappings can only be inserted, queried and deleted from the database

insert A client makes an insert operation for a pair (key; value) by contacting a process pi such that
pi key < pi+1. The data is then replicated on all other processes. A server must reject an insert
operation if the key does not correspond to its ID.
For instance, assume that you have three servers with IDs 0, 5, and 15. If a client wants to insert some
data with key 2, he will request this operation to server 0. Similarly, if a client wants to insert data
with key 6, this operation will be requested to server 5.
However, if the request with key 6 would have been addressed to server 0, this request must fail.
Moreover, the insert is idempotent, i.e., if there is already an entry (key; val1), and someone does
insert(key; val2), the previous entry is overwritten all over.
delete A client can delete a key from the database by making a request to a process pi such that pi key < pi+1. The delete operations must also be replicated on all processes.
Similarly to insert, the delete for key 2 will be requested to server 0, while the delete for key 6 will
be requested to server 5. If the delete for key 6 would have been addressed to server 0, this operation
must fail.
If delete(key; val) is issued and key does not exist, the operation succeeds.
1
query A client can query any process pi regarding the value mapped to a key. The DBMS is consistent if
all replicas return the same value for the same query.
For instance, a client can request replica 15 the value bound to key 2.
The system must keep a consistent view of the database, e.g. at any point in time the replicas must hold
the same data. To ensure this, it is acceptable that operations can fail due to con
icts among them (see tip
2 below). Moreover, you can assume that the data inserted in the database is put immediately on stable
storage: operations can simply fail if consistency cannot be ensured, so there is no need for recovery. Finally,
only crash failures can occur.


1. The insertion and delete operation are actually the atomic commit problem. Any of the algorithms for
two-phase or three-phase commit will work as a solution.
2. Make sure that if two (or more) operations on the same key originating from dierent clients are
concurrent, at most one is executed.
For instance, if one client issues \insert(key=2, value=5)" and at the same time another client issues
\delete(key=2)", at most one of these should be performed.
However, if a \insert(key=2, value=5)" and a \delete(key=3)" are concurrent, these can be safely
performed.

Technology: You are free to implement this project using either plain sockets or RPC. The use of RPC IS PREFERRED.