Byzantine Fault-Tolerant Key-Value Store
CSCI-4510/6510 – Fall 2024
Assigned: November.18, 2024
Project due: Sunday, December 8, 2024 at 11:59 PM in Submitty and Gradescope
Teams formed in Submitty by: December 1, 2024
You may work in groups of one or two for the coding portion.
The problem set is to be done individually.
1. Overview
In the homeworks so far, we have assumed that all sites follow the specified algorithm. In this project, you will implement a replicated key-value store using a Byzantine fault tolerant replication algorithm, namely the Dolev-Strong algorithm.
The distributed system consists of a set of n sites. Each site is identified by a site ID, a short alphanumeric string. A site can be honest or it can be a traitor. Honest sites maintain a replicated log, and they use this log to update local copies of the replicated key-value store. Traitors try to prevent agreement on log entries so that the key-value stores at the honest sites become inconsistent.
We will assume the system is synchronous and that there is a maximum message delay of 50ms. Each site will be started with three arguments: the site ID, the value of m, and whether the site is a traitor or honest, e.g.,
./run.sh apple 3 traitor
./run.sh banana 3 honest
Every site will be started with the same value for m.
The log slots are numbered starting with 0. Each log entry has a commander. We number the sites starting from 0 based on their position in the knownhosts.json file. The commander for a log slot k is site k mod n, where n is the total number of sites. Every site can compute which site is the commander for a given log slot using this formula.
When a user enters a command to update the key-value store, the site should check its log to figure out the number of the next available log slot. The site should then send its proposed log entry to the commander for that log slot. For simplicity, you can assume that only one site will try to submit a command for each log slot. The commander should then start the Dolev-Strong algorithm so that the honest sites reach agreement on what value to use for that log slot.
2. Byzantine Behavior
You must implement both the correct Dolev-Strong algorithm and the Byzantine behavior for treacherous sites. To simplify things, you only need to implement a restricted set of Byzantine actions (see below). Further, you do not need to implement signed messages. You can assume that sites will not alter messages, nor will they lie about what messages they’ve received from other sites.
Treacherous Commander: If the commander is a traitor, it will send the user’s true command to every odd numbered site, and it will send a false command ‘append sneak attack’ to all even numbered sites (you can assume that an honest site will not enter that command).
Treacherous Lieutenant: If a lieutenant is a traitor, it will not send any additional messages.
You can assume that commands will only be entered at honest sites.
3. Key-Value Store UI
Commands will only be entered at honest sites. Each site should accept user input from standard in. Your program should support the same commands as for Homework 3, with the same formatting for inputs and outputs. For the get, log, and kv, the site should print the results based on its local copy of the log and key-value store.
If an honest site enters a command to update the key-value store (put, append, or remove), the site should first check if the command is valid according to the site’s local key-value store. If not, the site should print out the appropriate error message.
If the command is valid, the site should send its proposed log entry for the next empty log slot to the commander. The commander should then start the Dolev-Strong algorithm. If after the Dolev-Strong algorithm completes, the append sneak attack command is executed instead (added to the log and applied to the key-value store), the site where the proposed command was entered should print out the appropriate error message. If the site’s proposed log entry is added to the log, the site should print out the appropriate success message.
4. Messaging Requirements
To verify that your program is sending and receiving the correct messages, each site should print which messages are sent and received to stderr. This output will be graded manually.
When a site sends a message, it should prepend its site ID. The site should print out the current log slot, the current round, and the contents of the message. For example, suppose site A is the commander. When it sends an order to site B in round 0, it should print:
log slot=3 R=0 sent A:put hello [world] to B
It should print this out regardless of whether it is honest or a traitor.
When an honest lieutenant B receives this message and then forwards the order to site C, it should print out:
log slot=3 round=1 received A:put hello [world]
log slot=3 round=1 sent B:A:hello [world] to C
If the lieutenant is a traitor, and it does not send any messages, it should not print anything out for either receiving or sending.
At the end of the algorithm execution, every honest lieutenant should print out the agreed upon log entry, e.g.,
the log entry is hello [world]
Please do not include extraneous debug information in your stderr output.
5. Implementation Details
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.
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.