Homework #2

Due Date: Tuesday, February 29, 2000 at 11:59PM
Points: 80

1. (20 points) Which of the following statements concerning the total ordering relation => are true? Justify your answers.
   1. An event a that happened before event b in physical time will always satisfy a => b.
   2. If every process increments its logical clock by a different number, the total ordering relation => will not hold.
   3. If the delay of message transfer varies from time to time, the total ordering relation => will not hold.
   4. If the total ordering of processes << changes during the operation of the system, the total ordering relation => will not hold.
2. (30 points) In class, someone suggested that Haung's termination detection algorithm could be done using a counter to avoid the need of breaking the weights up. Present a protocol for termination detection that uses counters instead of weights. Compare your protocol to Huangıs by looking at the number of messages sent during a distributed computation, and any assumptions about the lifetime of processes participating in the computation.
3. (30 points) If a site S has to broadcase a message m to a set of sites, will the Schiper-Eggli-Sandoz causal ordering protocol work properly without modification? If your answer is yes, justify it. If your answer is no, give an explicit example of the failure, and give the necessary modifications to the algorithm to correctly handle this case.