Project 3 - Distributed Version Control Service                                                   

CSCI-4510/6510 – Spring 2024  

Assigned: March 18 2024

Teams formed in Submitty by: Wednesday, March 27, 2024 (10% penalty for missing this deadline).

Anyone who earned < 90% on Project 2 must work in a team of two.

Anyone who earned  90% on Project 2 may work alone or in a team of two.

Teams must consist of students in the same section.  

Any exception to this policy must be approved by the instructor by the team formation deadline.

Project due: Wednesday, April 10, 2024 at 11:59pm in Submitty

1.  Summary

In Project 3, you implemented a distributed version control service using the replicated log and dictionary algorithm by Wuu and Bernstein. This replication algorithm has the benefits of simplicity and low message overhead, but because the logs were not closely synchronized, it was complicated to identify and reconcile conflicting updates. Thus, you needed to implement mechanisms at the application level to determine which operations should be executed and in what order.

In this project, you will implement the distributed version control service using the Synod Algorithm to maintain a replicated log of the “insert_file”, “delete_file”, “insert_line”, and “delete_line” events. The log replicas will be maintained in a way so that it is not possible to execute conflicting updates, and so it is not necessary to keep track of the statuses of lines and files. To simplify things, we will also add a “replace_line” operation that replaces the specified line in the file. Thus, replacing line is a single operation, rather than a “delete_line” followed by an “insert_line”.

The system consists of N sites. Each site plays the role of a Proposer, issuing proposals for file operations. It also plays the role of an Acceptor, helping to determine which proposal should be accepted for each log slot. And, it plays the role of a Learner; it stores a replica of the log in stable storage and updates this log with committed log entries. The Learner can also store data structures in memory that contain the file system (files and lines), but these data structures should not be stored in stable storage.

2. Implementation Details

When a user enters a command at a site, the site’s Proposer should execute the following steps:

1. If there are any holes in the site’s log, execute the Synod algorithm for those log slots to learn the missing values. Update the copy of the repository with any missing information if necessary.
2. Check whether the command can be executed based on the local state of the updated repository.  If the command can be executed, then execute the Synod algorithm as the Proposer to propose the new operation event for its first empty log slot.
3. When a Learner learns about a new log entry, it updates its copy of the repository accordingly.

Since each command is applied and replicated when it is entered, there is no need for the “commit” command.

In the case of timeouts when waiting for “promise” or “ack” messages, the Proposer should retry the proposal a maximum of two times (three tries total) for the same log slot. The Proposer should increment its proposal number in between each try, as specified in the Synod algorithm. Even if there is no timeout, due to concurrent proposals, the site’s proposal may not be committed to the log. If the site’s proposal is not added to the log, the application should notify the user according to the UI specification (see Section 3). The Proposer should not try to propose the operation for any other log slot.

Note 1: You will need to use multiple threads or asynchronous IO for proposals. A Proposer should not try to contact the Acceptors one at a time, but rather it should send messages to all Acceptors at once and wait for responses only from a majority.

Note 2: Your site should be able to act as a Proposer, an Acceptor, and a Learner simultaneously.

Learning Committed Values (all teams): You can use either of the two strategies discussed in class to inform the Learners of committed values. If you use a “Distinguished Learner”, the site that is the Proposer for the committed value can also be the “Distinguished Learner”.

Stable Storage (all teams): The log should be stored in stable storage. Your application should also store the Acceptor state variables in stable storage as specified in the Synod Algorithm. Do not store any other information in stable storage.

Site Failures and Recovery (all teams): Your application should follow the Synod algorithm, meaning it should tolerate message loss, site failures, and recovery. The application should be able to create new log entries (under the liveness conditions) so long as a majority of sites are active. 

A site may miss commit messages for some log entries due to failure. When the site recovers, it should learn the values for these missed log entries. You must design and implement a recovery algorithm to do this. Your algorithm should ensure the safety and liveness guarantees described in the Paxos paper.

After a site recovers and learns the missing log entries, it should recreate its in-memory data structures for the files and lines by “replaying” the log, i.e., applying the operation in each log entry in order.

Note 3: A site may also miss log entries that are committed when it is active, since messages may be lost. When a site learns a committed value for log slot 5, for example, it should fill in any holes (missing entries) in log slots 1 - 4 by running an instance of the Synod algorithm for each missing entry. It should issue at most three proposals to fill any hole.

Paxos Optimization (CSCI 4510):  Your application does not need to use a Distinguished Proposer, so you do not need leader election. You will still implement a small optimization to the Paxos algorithm. When a site “wins” a log slot k, meaning the site’s proposed value is the one that is committed to log slot k, this site can skip the “prepare-promise” phase for its first proposal for log entry k+1 (if it has a proposal for this log slot). In essence, this site’s Proposer has implicit promises from all Acceptors for its first proposal for log entry k+1. This first proposal should have proposal number 0. Note that Acceptors should check that the proposal that skips the “prepare-promise” phase has permission to do so.

Full Paxos (CSCI 6510): Your application should use a leader election algorithm of your choice to elect a Distinguished Proposer. This leader election algorithm should detect the failure of a current leader and elect a new one. It should also allow recovered processes to learn the identity of the leader (and possibly elect a new leader on its recovery). The Distinguished Proposer should use the optimization for skipping the “prepare-promise” phase as described in the Paxos paper. Should the leader election algorithm elect more than one leader, the Distinguished Proposer will be the first of these leaders to “win” a log slot, meaning that site’s value is committed to the log. Every site will send its proposed operations to the Distinguished Proposer, and this site will execute the steps at the beginning of Section 2 for each proposed operation, in the order that it was received at the Distinguished Proposer.

2. UI Specification

(a) To create a file, the user enters the following command

add <filename> 

where <filename> is the unique name of the file to be created, for example,

add readme

If the operation for this command is added to the log, the site updates its local copy of the repository and prints out

File <filename> created.

If the command is not added to the log, the site prints out

File <filename> could not be created.

(b)  To append a line of text (80 characters max) to the a file, the user enters the following command

append <filename> (<text>)

for example,  

append readme (This is the first line of text)

If the command is successful , the site appends the line of text to the end of the file and then prints out

File <filename> updated.

If the command is not added to the log, the site prints out

File <filename> could not be updated.

(c)  To view the contents of a file, the user enters the following command

view <filename>

In response to this command, the site displays the file contents from the local copy of the repository. Each line of the file is displayed in the following format:

<line_number> <text>

For example, in response to the command

view readme

the site prints out

1 This is the first line of text

You should start the line numbering with 1.

If the file is empty, the site prints out

empty file

(d) To replace a line of text in a file, the user enters the following command

replace <filename> <line_number> (<text>)

for example,

replace readme 1 (This is an updated line of text)

If the command is successful , the site appends the line of text to the end of the file and then prints out

File <filename> updated.

If the command is not added to the log, the site prints out

File <filename> could not be updated.

(e) To delete a line of text from a file, the user enters the following command

delete <filename> <line_number>

If the command is successful , the site appends the line of text to the end of the file and then prints out

File <filename> updated.

If the command is not added to the log, the site prints out

File <filename> could not be updated.

For simplicity, we will implement line deletion by replacing the text with an empty string. The empty line will still be part of the file. So if the user deletes the first line of a two-line file, the output of the view command is:

1

2 This is another line of text

(f) To list the files in the repository, the user enters the command

list

In response to this command, the site prints out the list of files in the site’s copy of the repository, one file per line in lexicographical order, in the format

<filename>

(g) To remove a file from the repository, the user enters the command

remove <filename>

If the file is non-empty, the site first tries to create one log entry to delete each line, in descending order. If all line deletion commands are successfully added to the log, the site then tries to add a log entry to delete the file. If the file deletion operation is successfully added to the log, the site prints out

File <filename> removed.

If some lines are removed but the file could not deleted, the site prints out

File <filename> could not be removed. Some lines were deleted.

If no lines are deleted, the site prints out.

File <filename> could not be removed.

(h) The site should also 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 ascending order of log slot, in the following format:

insert_file readme

insert_line readme 1 (This is a line of text)

replace_line readme 1 (This is an updated line of text)

insert_file readmetoo

insert_line readmetoo 1 (Jack and Jill)

insert_line readmetoo 2 (Went up a hill)

delete_line readme 1

delete_file readme

(i) Messages: we would like to observe which messages are sent and received by your application. To enable this, please print a message to stderr every time a site sends or receives a message. The output should look something like (this will not be checked by the autograder):

sending prepare(100) to all sites

received promise(99, ‘insert_file readme ’) from <site_id>

Please do not include extraneous debug information in your stderr output.

4. Implementation Details, Source Code Management, and Build Requirements

• The language requirements are the same as for Project 2.
• The networking requirements are the same as for Project 1 and 2.
• The source code management and build requirements are the same as for Project 1 and 2.
• Your application should handle message loss, message reordering, site failures, and site recoveries.
• Your application should implement the quit command as specified in Project 1.

5. Deliverables and Grading

(a) To submit your project source code, you must follow the Submission steps in Submitty. Submitty will execute several simple auto-grading tests to verify that your application builds and runs in the Submitty environment and that your application meets the UI specification. These tests will be worth 25% of the project grade.

(b) Each team must also submit a 1.5-2 page project report in your Submitty git repository. This report must be single-spaced with 1 inch margins. Font size must be 12pt or smaller. The report can include diagrams. The report should provide the following information:

• Details of your project design and implementation. This includes descriptions of your data structures, stable storage implementation, use of sockets, and use of threads.
• A description of how you implemented the Learners and why you chose the particular method.
• A description of your recovery algorithm and a discussion of when/how it guarantees the Paxos safety and liveness properties.
• A description of how you tested your project (be sure to consider failures and message loss).
• A description of how the project work was divided among the team members.

A substandard report can result in up to a 10% point deduction on your project grade.

(c) 65% of the project grade will be based on a live evaluation, run in Docker, where we will execute several use cases and observe the results. In addition to the basic functionality, we will evaluate how your project responds to site crashes, site recoveries, and message loss.

If your project does not run on Submitty, you will receive a score of 0.

You can ask general questions about the project specification on the Submitty discussion forum, but please do not describe your proposed solution. Please save questions about your specific design or implementation for office hours or email.