Extra Credit Project - Byzantine Agreement                                                   

CSCI-4510/6510 – Spring 2024

Assigned: Apr. 8, 2024

Project due: April 18, 2024 at 11:59 PM - No late submission will be accepted.

This is an individual project. You can earn up to a 10% bonus on your course grade.

1.  Summary

In Projects 2 and 3, you implemented a distributed version control service using two different log replication algorithms, Wuu-Bernstein and the Synod algorithm. These algorithms were designed for asynchronous systems with message loss and site failures and recovery. However, neither of these algorithms could tolerate Byzantine failures.

In this project, you will implement a building block of a Byzantine-tolerant replicated log using the Dolev-Strong algorithm. You only need to implement code to execute a single instance of the Dolev-Strong algorithm in which one site is the commander (sender) who transmits an order, and all other correct sites reach agreement on this order.

The system consists of four sites: A, B, C, D. The value of m will be passed in as an argument to the program and will be the same for all sites. Site A is the commander. Site A should first prompt the user to enter an order, 0 or 1. Site A should then begin an instance of the Dolev-Strong algorithm. The algorithm instance should execute for m+1 rounds, and at the end of round m+1, each correct process should print out the commander’s order.

2. Implementation Details and Supported Commands

The Dolev-Strong algorithm uses signed messages to ensure that a process cannot “lie” about a message it received from another process. A process will ignore any message that does not have a valid signature. You do not need to implement signed messages, and so you do not need to support Byzantine behavior where a process sends invalid messages. Your implementation only needs to support two types of Byzantine behavior:

1. A treacherous commander may send different orders to different lieutenants.
2. A treacherous lieutenant may fail to send messages that are required by the algorithm.

When the application is started at the commander, the site should print out:

Enter your order:

The user can enter 0 or 1. On receiving this input, the commander should start the Dolev-Strong algorithm.

When a site sends a message, it should prepend its site ID. The site should also print out the current round and the contents of the message. For example, when the commander (site A) sends the order to site B in round 0, it should print:

R=0 sent A:0 to B

And when the lieutenant forwards the order to site C, it should print out:

R=1 sent B:A:0 to C

If the lieutenant is a traitor, and it does not send a message as required by the algorithm, it should print out:

R=1 did not send B:A:0 to C

At the end of the algorithm execution, every loyal lieutenant should print out the agreed upon order:

The order is 0.

For Submitty autograding, you must implement the correct behavior for all processes. For the project demonstration (see below), you must also implement Byzantine behavior. You can assume the physical clocks on Submitty are perfectly synchronized (since all containers run in one machine).

3. Code Requirements

• You must implement your project using either Java, Python, Rust, or Go.
• You may use UDP or TCP for network communication. Either way, you can assume that messaging is reliable and synchronous.
• Use the IP addresses and ports specified in the knownhosts.json file. Do not try to obtain the IP address or ports from the container directly.
• You may not use any libraries that provide “server” functionality, e.g., an HTTP server library.

4. Source Code Management and Build Requirements

The source code management and build requirements are the same as for Projects 2 and 3, with one exception. The run.sh script should accept an additional argument:

run.sh <site_id> <m>

To submit your project 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. Submitty will execute several auto-grading tests to verify that your application builds and runs in the Submitty environment and that your application meets the UI specification.

5. Deliverables and Grading

[20%] Submitty Autograding.  Submitty will run a single public test case, with N=4 and m=2, where all sites are correct (loyal). Submitty will also run a single hidden test case with N=4 (m will not be shared) where all sites are correct (loyal).

[45%] Project Demonstration. You must provide a video that shows your application running two tests. For both tests, use N=4 and m=2. In Test 1, the commander is a traitor and the three lieutenants are loyal. In Test 2, the commander and site B are traitors and sites C and D are loyal. For each test, please narrate the test execution. Explain how the Byzantine sites are behaving and show the output from all sites. You can use the software of your choice to make the video (Webex will work fine for this).  You should upload your video to Box and include a link to the video in your project report.

[35%] Project Report: The project report should explain how to create a Byzantine Fault-Tolerant distributed version control service. Specifically, you should explain how you would use the Dolev-Strong algorithm to implement the replicated log in the version control service from Projects 2 and 3. Your proposed solution must satisfy:

Safety: no two correct processes have different entries for the same log slot.

And should aim to satisfy:

Liveness: every value proposed by a correct process is replicated in the log of every correct process.

You can assume that your application runs in a synchronous system with reliable signed messages. Your report should include the following:

• How your system chooses a commander for each log slot
• How the commander determines what value to propose for a log slot
• How your application handles each type of Byzantine behavior
• Why your approach guarantees safety
•  Under what conditions your approach  guarantees liveness and why.

There are no page limit requirements for the report.