McGill University
School of Computer Science

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

Description: Problem set in Distributed Algorithms

Please do the following problems. They are due on December 16. Please put a hard copy of the solutions in my mailbox. As they are due by 5PM, please have Lucy stamp them with the date.

1. For the Lamport, Shostak and Pease algorithm, write out all of the message exchanges in detail. You might wish to make use of a tree diagram in order to explain the exchanges. Each level in the tree corresponds to the order of the exchange. However, any coherent explanation will be acceptable. You should consider the case of two faulty processors.

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. What is the message complexity of the resulting algorithm? Consider the cases in which the issuing process is fault free and in which it is not fault free.


[ Academic Programs ] [ SOCS HOME ]