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

}