School of Computer Science
Computer Science 308575A
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 ]
