Recommended Exercises

(1) Link reversal: Given a DAG (as in the slides used for Lecture 20) that is not destination-oriented, identify the nodes that perform link reversals in each step of the algorithm, and also show the link directions after each step. (The above slides show one such example.) The final graph after the nodes stop reversing links will be destination-oriented provided that the network is connected.

(2) Paxos algorithm: Consider a particular execution of Paxos. In this execution, a particular learner learns that value v is chosen. Is it possible for another learner to learn that a different value w is chosen? Explain your answer. Recall that a learner learns that a value v is chosen only after v is accepted by a majority (i.e., quorum) of acceptors.