Project 1: A simple distributed system

Creating a simple distributed system and writing asynchronous network code

Introduction#

Implement an asynchronous program that implements the protocols below

Discovery Protocol#

Each peer implements this protocol:

1. Over a single UDP socket on the default port 50000: 

   1. Send an JSON-encoded HELLO message to all known peers (given on the command line) {"type": "HELLO"}\n
   2. Send an JSON-encoded ACK message back to the source of every HELLO message received {"type": "ACK"}\n

2. Once a peer has received an ACK from all known peers and sent an ACK message in response to the HELLO messages from all its peers, the peer can enter Leader Election.

Leader election#

    1.  If the node has the lowest IP address of all known peers, it becomes the **Leader**. 
    2.  Else, it is not the Leader.

Action and Response#

1. The Leader sends an JSON-encoded REQUEST message to all known peers. {"type": "REQUEST"}\n

2. Each peer upon receiving a REQUEST message, sends the following JSON-encoded message back to the Leader: {"type": "RESPONSE", "name": <domain_name>, "ipaddr": <string>}\n ** or {"type": "RESPONSE", "name": <domain_name>, "ipaddr": <integer>}\n** where <domain_name> is the receiving peer’s domain name assigned by Docker.

3. The Leader, upon receiving the RESPONSE message, replies to the sender with an ACK message.

4. Peers, upon receiving an ACK from the leader, exit.

Round and Consensus#

A round starts after the leader is elected. A round is time-bounded (timeout) by the leader to receive a response from all the peers. The system is in consensus when the leader receives the RESPONSE from all the peers within the round’s duration.

Simulate packet loss because of Network partition#

A peer should randomly decide to not send a RESPONSE to the REQUEST from the leader 10% of the time.

Expected output#

The Leader, after receiving a RESPONSE message from every peer and sending an ACK to every peer’s RESPONSE, prints to STDOUT the following in ascending IP address order for every member of the system: ipaddress, domain_name\n ipaddress is the IP address as a string in dotted quad format (nnn.nnn.nnn.nnn), domain_name is the domain name assigned by Docker.

There must be NO extra debugging output without the use of --verbose, or you will lose points. 

Your program should have a deterministic result, i.e., it should always find the correct solution and none of the peers should crash. 

Your program#

Your program, proj1, must execute on the command line using the following command.

$ ./proj1 [-h] --peers PEERS [--port PORT] [--timeout TIMEOUT] [--verbose]

--peers is required on the command line. It specifies the number of peers in the system. --timeout specifies a timeout value in seconds after which all PEERS must exit --verbose enables debug output --port, --timeout, and --verbose must be implemented, but are optional on the command line.  

Starter Code#

The starter code for this project is here. A Dockerfile and Docker Compose file, proj1-compose.yml, are supplied in the starter code.  While you may change either file, the evaluation will use the supplied Compose file.

• docker compose -f proj1-compose.yml up --build

• docker compose -f proj1-compose.yml up

Asynchronous communication#

We encourage you to write your code in an event-driven style, using select() or poll() on the datagram socket to which the peer is connected (see the starter code for an example). This will keep your code single-threaded, making debugging significantly easier. Alternatively, you can implement your router in a threaded model (with one thread handling each socket), but expect it to be substantially more challenging to debug.

Starting the project#

You must have a design review of your protocol with a TA no less than five (5) weekdays BEFORE submitting your project. A system to schedule reviews will be posted on Piazza. You design should address, at minimum, the following details:

1. Use UDP for the project and specify the port number used
2. A specification of all messages used in the protocol. What each message contains, its format, and the values of each field? Hint: use JSON.
3. The detailed protocol used to determine if all the nodes launched have been heard from and acknowledged
4. What is the situation that deterministically ends the run in your design, i.e., how does each peer know when to stop?
5. What is the design to capture the number of rounds each peer takes?

A template repository of fundamental starter code for the assignment in Python using Docker is available on the Khoury GitHub server. Provided is a simple implementation of a peer that opens a UDP socket, sends a HELLO message to its peers, and prints out every message it receives within a timeout. You may use this code as a basis for your project if you wish.

Runtime Analysis:#

Once your implementation is running, perform the following runtime analysis.  For 3-, 5-,and 11-node systems, determine the average number of rounds needed for the system to reach consensus and exit. For each value of n, the system should be run at minimum ceil(log1.5(n**2)) times. The number of runs must be documented in the written evaluation. 

Create a table with the header number of nodes in the system, number of runs, and average number of rounds. In your written analysis of the results, briefly explain the differences in the individual runs per system with different values of n.  What does this tell you about the complexity of starting and managing distriubted systems with large number of nodes Include it and your analysis in a file called, table.pdf and add that to your submission to Gradescope.

Submitting Your Project#

Your Dockerfile, proj1-compose.yml, source code, and table.pdf should all be placed in the root directory of a compressed archive (i.e., a .zip file) and then uploaded to Gradescope.  Alternatively, you can check all these items into Khoury’s GitHub, download a zip file from Khoury’s GitHub, and submit that to Gradescope, or any other upload/submission option Gradescope permits.  If your submission is missing any required file for evaluation, it will receive 0 points.

There is NO autograder for this project.  Your submission will be evaluated by hand.  

Grading#

The grading of this project will be broken down as follows:

Questions#

Ask on Piazza or come to office hours (the TA’s or Prof. Jackson’s).