Due Date: Tuesday, February 29, 2000 at 11:59PM
- (20 points) Which of the following statements concerning the
total ordering relation => are true? Justify your answers.
- An event a that happened before event b in physical
time will always satisfy a => b.
- If every process increments its logical clock by a different number,
the total ordering relation => will not hold.
- If the delay of message transfer varies from time to time, the total
ordering relation => will not hold.
- If the total ordering of processes << changes during the operation
of the system, the total ordering relation => will not hold.
- (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.
- (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.
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 3/18/2000