Project 1: HELLO-ACK Protocol

Get started writing asynchronous network code

Introduction#

Implement an asynchronous program that implements the Hello-Ack protocol.

Hello-Ack Protocol#

Each peer implements a protocol of your design to achieve the following:

Your program should print  exactly one line of output.

Either:
“DONE: number of rounds” or
“DONE: number of rounds [followed by a comma separated list of “(domain name, IP address)” of the source of each of the received ‘ACK’ message"].

The list must include the (domain name, IP address) for every process started. Only the node with the lowest IP address prints the longer message. There must be NO extra debugging output, 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 [PEERS ...] [--port PORT] [--timeout TIMEOUT] [--verbose]

--peers is required on the command line.
--port, --timeout, and --verbose must be implemented, but are optional on the command line.  

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. 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 5-, 11-, 21-, and 51-qnode 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 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).