DSA Fall 2024 Homework 2

Homework/Project 2 - Replicated Key-Value Store with Causal Consistency

CSCI-4510/6510 – Fall 2024

Assigned: September 26, 2024

Project due: Wednesday, October 16, 2024 at 11:59pm in Submitty and Gradescope

Teams formed in Submitty by: October 9, 2024

You may work in groups of one or two for the coding portion.

The problem set is to be done individually.

1. Overview

For this homework, you will implement a replicated key-value store using the Wuu-Bernstein dictionary algorithm. Your system will implement causal consistency: if event e happens before event f, then no site will observe the effects of event f without previously observing the effects of event e.

The distributed system consists of a set of sites. Each site is identified by a site ID, a short alphanumeric string. Each site stores a copy of the key-value store (full replication), and each site accepts commands from standard in to execute operations on the key-value store. When a user enters a put, get, remove, or append command at a site, the operation is only performed on the site’s local copy of the key-value store. Operations are replicated to other sites only when the site is instructed to send messages.

As in Homework 1, each key is a string of at most 32 alphanumeric characters. Each value is a non-empty list of strings, where each string has at most 32 alphanumeric characters.

2. Key-Value Store UI

As in Homework 1, each site will accept user input from standard in. Your program should support the following commands:

(a) To execute a put operation, the user enters:

put <key> <value>

for example:

put hello world

The site should execute the operation on the local copy of the key-value store. If the operation is successful, the site should print out:

put completed

If the operation cannot be completed, for example, because the key already exists in the key-value store, the site should print out:

unable to execute put

(b) To execute a get operation, the user enters:

get <key>

For example,

get hello

If the site’s local copy of the key-value store contains the key, the site should print out:

get <key> returned <value>

For example, for a one-element list:

get hello returned world

And for a two element list:

get hello returned one, two

If the site does not have the key in its key-value store, it should print out:

get <key> returned null

append <key> <value>

For example, if the key hello already stores a single value world, after the command

append hello goodbye

the value associated with the key hello should be [world, goodbye]. If there is no value for the associated key, the append operation should act as a put operation.

Once the site completes the append operation, it should print out:

append completed

(d) To remove an entry from the key-value store, the client enters

remove <key>

For example,

remove hello

If the operation is executed successfully, the client should print out:

remove completed

If the key-value store does not contain the key, the site should print out:

unable to execute remove

3. Log and Dictionary Specification

Your key-value store acts as the dictionary in the Wuu-Bernstein algorithm. You can use a different data structure to implement the dictionary, for example, a map, but whichever implementation you choose must support the insert and delete operations from the Wuu-Bernstein algorithm.

Each entry in the dictionary is a pair (key, value_list). The dictionary is a set of entries.
The sites should maintain the replicated dictionary using a replicated log (partial log) that stores event records for insert and delete operations.
In response to a put command, the site should insert the appropriate entry into its local copy of the dictionary
In response to a remove command, the site should delete the corresponding entry from its copy of the dictionary.
In response to an append command, the site should first execute a delete of the existing (key, value_list) entry and then execute an insert of the updated (key, value_list) pair with the new value appended on the list.
For each insert or delete operation, the site should create the corresponding event record and add it to its log.
get operations should not be logged.

To sync up the copies of the key-value store, your site should provide two commands that send messages to other sites. These messages should contain only those log entries that are identified as necessary by the Wuu-Bernstein algorithm. The sites should only send messages in response to these commands.

(a) To send a message to a single site, the following command is entered:

send <site_id>

(b) To send a message to all other sites, the following command is entered:

sendall

In the Wuu-Bernstein algorithm, a site may not always have the most up-to-date information about the other sites’ logs and dictionaries. Therefore, the specification described above may result in conflicting operations such as multiple appends to the same key, or a remove and append for the same key.

To deal with potential conflicts, operations should be executed in “happens before” order. Ties (for concurrent operations) should be broken in lexicographical order of site ID and should preserve the order of operations at each site. It is up to you to determine how to implement this operation ordering.

Your application should truncate logs and reduce message sizes as specified by the Wuu-Bernstein algorithm. It should not send any additional messages other than those described in this specification.

Commands for Introspection

(a) To allow us to introspect the contents of the key-value store, when the commend kv is entered, the site should print out the content of the key-value store using the same format as for Homework 1.

(b) The site should support the following command to display the contents of the log:

log

In response to this command, the system should list the log contents, sorted in the same order as the operations are applied to the key-value store. For example, if the commands applied, in order, are

put lucky charms

put froot loops

append lucky cereal

The output of the log command should be:

insert lucky [charms]

insert froot [loops]

delete lucky [charms]

insert lucky [charms, cereal]

clock

In response to this command, the site should print out the matrix clock entries, as integers, in the following format (e.g., for N = 3):

1 0 0

0 1 2

0 0 2

To order the sites for the matrix clock, sort by site ID in lexicographical order.

4. Implementation Details

The language requirements are the same as for Homework 1.
The networking requirements are the same as for Homework 1. You should not assume that messaging is reliable, FIFO, or synchronous.
As in Homework 1, your submission must contain a build.sh file that compiles your code (if necessary) and copies all runnable code and libraries into a directory named bin.
Each site runs a single program. Your submission must contain a run.sh file that starts the site program. The site ID from the knownhosts.json file will be passed as the first argument to this script.
Sites may crash and recover. You should implement stable storage as required for the Wuu-Bernstein algorithm.

5. Submission and Grading

The problem set is worth 25% of the grade, and the coding portion is worth 75% of the grade. Solutions to the problem set must be submitted in Gradescope.

To submit your homework source code, you must follow the submission steps in Submitty. This will check out the project files from your git repository and copy them to Submitty for grading. The project grades will be based on both public and hidden autograding tests.

35% public tests. Details of the test cases will be posted on the course website.
65% hidden tests. Additional tests will be run after the project deadline.

Note that to run the hidden tests, I need to regrade all project submissions, so the public tests will be rerun. Because of this, you should make sure that your code gives repeatable results.

6. Late Policy

Submissions will be accepted up to 24 hours late for a 20% grade penalty.