We will build upon the system designed in Assignment 2.

In  this  assignment,  we  will  assume  any  replica  can  commit  updates.  A  client  can  send  an add_update(key,value) request to any replica and the replica will update its local data store only when it achieves a quorum. We define a quorum as the majority of members within a set of nodes. For a size of N nodes, a quorum requires votes from at least Nw members, where Nw >= (N/2)+1.

Upon receiving an add_update request, a replica initiates the process by requesting permission to commit the changes from at least Nw replicas. It sends a permission request in the form of

r(key, v), which contains the key and the associated version number v of the data. When a

replica receives the permission request, it compares the version number. If the version number

matches its local copy, it approves the request. However, if the version number does not match, it sends a deny message along with the associated version number. Note that, for this assignment,    replicas do not need to synchronize their local copy if it is found to be stale (older version of the   data).

Once the replica achieves a quorum (e.g., majority vote), it will COMMIT the changes from the add_update request to its local  data  store. And,  send  COMMIT  changes  to  all  replicas.  On receiving the COMMIT message for that entry, all replicas commit the updates to their local data store.

If the replica fails to receive a quorum, it will report an error to the client. Note that you may use Zookeeper to query the set the active replicas.

Similarly, any read(key) will require a quorum before the value is sent to the client. A client can connect to any replica to read the value. The replica will randomly select NR replicas and request values along with version numbers. If there is no disagreement in value and version number among the replicas, it will send the value to the client. However, if there is any disagreement, it will randomly select NR  replicas and repeat until replicas reach an agreement. You should select NR such that NR + NW > N.

Extra credit

Given the possibility of replica crashes and the resulting potential for inconsistent states, we will also implement a restore protocol. This protocol ensures that replicas can recover to a known consistent state agreed upon by other replicas within the system.

To initiate the restoration process, when a crashed replica is restarted, it will randomly select another replica. It will then compare its own state with that of the selected replica. Following this comparison, the crashed replica will duplicate the state of the selected replica by copying the differences, thus bringing itself back to a consistent and agreed-upon state within the system.