Distributed Systems: Course schedule 2016-2017 Tue September 27 Introduction to this course. Processes, failure models, network models. Cuts, global states, and consistent cuts. Logical clock. Sections 1-8 of Babaoglu-Marzullo-TR93.pdf. Exercise 1: Let C1 and C2 be two consistent cuts. Show that the intersection of C1 and C2 is consistent. Exercise 2: Let C1 and C2 be two consistent cuts. Show that the union of C1 and C2 is consistent. Exercise 3: Show that every consistent global state can be reached by some run. Exercise 4: Label with proper vector clock all the events of this distributed computation. Tue October 4 Monitoring a distributed computation. Vector clocks. Sections 3-8 of Babaoglu-Marzullo-TR93.pdf. Exercise 5: Label with proper vector clock all the events of this distributed computation. Wed October 5 Monitoring a distributed computation. Vector clocks. The Chandy-Lamport snapshot protocol. Lattice of a distributed computation (not covered in class, but you have to know it anyway). Sections 9-13 of Babaoglu-Marzullo-TR93.pdf. Exercise 6: Show that the Chandy-Lamport Snapshot Protocol builds a consistent global state. Exercise 7: What good is a distributed snapshot when the system was never in the state represented by the distributed snapshot? Give an application of distributed snapshots. Exercise 8: Consider a distributed system where every node has its physical clock and all physical clocks are perfectly synchronized. Give an algorithm to record global state assuming the communication network is reliable. (Note that your algorithm should be simpler than the Chandy–Lamport algorithm.) Exercise 9: What modifications should be done to the Chandy–Lamport snapshot protocol so that it records a strongly consistent snapshot (i.e., all channel states are recorded empty). Exercise 10: Show that, if channels are not FIFO, then Chandy–Lamport snapshot algorithm does not work. Exercise 11: Let S0 be the global state when the Chandy-Lamport snapshot protocol start, S the global state build by the protocol, and S1 the global state when the protocol ends. Show that S is reachable from S0 and S1 is reachable from S. Tue October 11 2-phase commit. Sections 7.1-7.4 of atomic_commit.pdf. Exercise 12: Exercise 7.2 in file atomic_commit.pdf. Exercise 13: Exercise 7.3 in file atomic_commit.pdf. Wed October 12 Paxos. Read "The Part-Time Parliament", L. Lamport, that describes Paxos. Overwhelmed by depression, try "Paxos Made Simple", again of L. Lamport. After this paper you believe that you have understood Paxos. Unfortunately, this is not true. Now you are ready to read "A Simpler Proof for Paxos and Fast Paxos", manuscript written by Keith Marzullo, Alessandro Mei, and Hein Meling. This last writing can be useful, finally, to see the light. Exercise 14: Show that Paxos is not live. Exercise 15: Assume that acceptors do not change their vote. In other words, if they vote for value v in round i, they will not send learn messages with value different from v in larger rounds. Show that Paxos does not work any more (it can reach a livelock). Exercise 16: How many messages are used in Paxos if no message is lost and in the best case? Is it possible to reduce the number of messages without losing tolerance to failures and without changing the number of proposers, acceptors, and learners? Exercise 17: Assume that you remove the property that every round is associate to a unique proposer. After collecting a quorum of n-f promises (where n is the number of acceptors and f is such that n=2f+1), the proposer chooses one of the values voted in max round in the promises (of course it is not unique, the proposer chooses just one in an arbitrary way). Show that Paxos is not safe any more.