Distributed Algorithms (236357) Winter 2000
Home assignment # 4
Please note that you need to submit this assignment only if you want
to improve your home assignments grade.
Grades for assignment #3 will be published around 29.1.2001.
Question 1. CANCELLED
[Question 8.6 from the book.]
Prove that Algorithm 8.1 provides the causal ordering property,
if each point-to-point link delivers messages in FIFO order.
(Note that we do not assume single-source FIFO broadcast.)
Question 2.
[Question 8.9 from the book.]
Show that Algorithm 8.2 does not provide total ordering.
That is, construct an execution in which (concurrent) messages are
not received in the same order by all processors.
Question 3.
[Question 10.7 from the book.]
Prove Lemma 10.7.
That is, consider the timestamps generated by Algorithm 10.3 (multi-writer
registers from single-writer registers), and show that the lexicographic
order on them is a total order which extends the partial order in which
they were generated.
Question 4.
Fill-in the details of the atomic snapshots algorithm using unbounded
sequence number: Specify the algorithm and prove its correctness and complexity.
This is based on material in Section 10.3 of the
book.
The answer appears in reference [3]:
@Article{AfekADGMS93,
author = "Yehuda Afek and
Hagit Attiya and Danny Dolev and Eli Gafni and Michael Merritt and Nir
Shavit",
title = "Atomic Snapshots
of Shared Memory",
journal = jacm,
volume = "40",
number = "4",
month = sep,
year = "1993",
pages = "873--890",
}
Submission date: 7.2.2001