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”,
}