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 ]