Assignment 2: Totally Ordered Broadcast
1. Summary
The totally ordered multicast algorithm is the "hero" of this course, and we will use it in many different contexts. To make sure that you really understand it, this assignment asks you to understand and implement it. There are three main parts:
- Write the pseudo-code for the Totally Ordered Broadcast.
- Write a proof of correctness, showing why the broadcast messages will be delivered in the same order on all processes.
- Implement the algorithm. Develop the "message middleware" which uses TCP sockets underneath and uses lamport timestamps for all incoming and outgoing messages, but provides a higher order API for broadcast.
434 students need to only do the first two parts, and the implementation is a bonus. For all other students, all parts are necessary.
2. Part 1: Pseudo-code for the Totally Ordered Broadcast
We have discussed two different variations in class. You can pick any one. Both are fairly "high level". You will need to fill in and provide all the missing small details, and write python-like pseudo-code for the entire algorithm. Break it down into the key functions which react to different events such as:
- Sending a broadcast. Implement a function such as
total-broadcast(msg). - Receiving a broadcast message over a TCP socket.
- Delivering a message to the application.
The more details you provide, the closer it will be to actual code. Think of this part as an "almost runnable" implementation required for part 3. That is, with a few additional lines of code, your pseudo-code should be able to actually run.
3. Part 2: Correctness Proof
You will next prove your pseudo-code correct. The property we are interested in, is showing that all proceses will deliver the broadcast messages in the same order. This has been covered in class, but you will need to write it in your own words, and provide additional details missing from the high-level proof-sketch we covered in class.
4. Part 3: Implementation
You need to implement the totally ordered multicast "on top" of a lower-layer messaging interface such as sockets. You can assume that your layer intercepts all incoming and outgoing network traffic.
The "application" needs to communicate with the middleware somehow. How? You can again use sockets for this, or any other inter-process-communication mechanism (such as pipes). However, this is the "front end" of the whole implementation and the least important part.
The mod important component is naturally the broadcast algorithm middleware implementation. It receives broadcast commands from the application and does its magic. You will effectively be designing and implementing an application layer protocol. So think carefully about the message format.
If a broadcast is ready to be delivered to the application, it communicates the message to the application. Again, dont overthink this—it can be as simple as a print statement.
Advanced: By default you can assume all messages are broadcast messages. But optionally, you can also support point-to-point messages (also logically clock timestamped).
4.1. Testing
- Your code should have ample test cases with different numbers of processes and broadcast messages.
- You should show the total order being respected on all proceses.
- Advanced: You will need to run a test lots of times to validate the correctness, since message orders can be different on each run. To make the testing more rigorous, it is often useful to add artificial
sleepstatements in your code, to emulate the interesting edge cases (which we have also seen in class). One way is to add random delays in responding to messages (few 100s of milliseconds).
5. What to Submit
Submit code+report.
The final report should have all the necessary parts (including a list and output of all test-cases).
Breakdown for 434:
| Component | Weight |
|---|---|
| Pseudo-code | 70% |
| Proof | 30% |
| Bonus: Implementation | 50% |
Breakdown for Rest:
| Component | Weight |
|---|---|
| Pseudo-code | 30% |
| Proof | 30% |
| Bonus: Implementation | 40% |