McGill University
School of Computer Science

Computer Science 308-575A
Fundamentals of Distributed Algorithms Assignment #2

Description: Problem set in Distributed Algorithms

Please do the following problems. They are due on December 10. Please put a hard copy of the solutions in my mailbox or give them to the TA. As they are due by 5PM, please have Lucy stamp them with the date. I will not accept any late submissions under any circumstances.

1. For the Lamport, Shostak and Pease Oral Message algorithm , write out all of the message exchanges in detail for the case of two faulty processors. You might wish to make use of a tree diagram in order to simplify the explanation. Each level in the tree corresponds to the order of the exchange.

2. Consider the solution to the Byzantine General's problem using signed messages. Make the following simplification. A process retransmits a message it has received if and only if it has not previously transmitted the value contained in the message. Give pseudocode for the algorithm, and prove that the algorithm is correct. What is the message complexity of the resulting algorithm?

3. For the Mattern's termination detection algorithm (p.207), derive a concurrent garbage collection algorithm. To do this problem, you should try to imitate what was done for the two termination detection algorithms in the section. The final result should be a message passing version of the algorithm. I expect you to refine the algorithm as far as possible. GOOD LUCK.

[ Academic Programs ] [ SOCS HOME ]