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]:

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