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.
Fri October 25
BitCoin. The paper of Satoshi Nakamoto pdf. The slides by Gabriele Palozzi pdf.
Wed October 26
Paxos. The proof from “A Simpler Proof for Paxos and Fast Paxos”.
Wed Nov 2
Fast Paxos. Looking at Fast Paxos, you realize that Paxos is actually easy (when compared to Fast Paxos).
Exercise 18: Assume that all proposers are learners as well. Let even rounds be assigned to proposers with the rules that we know. If round 2i is assigned to proposer p, then also round 2i+1 is assigned to proposer p. Odd rounds are “recovery” rounds. If round 2i is a fast round and if the proposer of round 2i sees a conflict (it is also a learner), then the proposer immediately sends an accept for round 2i+1 with the value that has been most voted in round 2i, without any prepare and any promise. Is safety violated? If yes, show an example. If not, demonstrate safety.
Exercise 19: You are an optimization freak. You realize that, in some cases, it is not necessary that the proposer collects n-f’ (the Fast Paxos quorum) promises to take a decision. Which is the minimum quorum and under what hypothesis this minimum quorum is enough to take a decision?
Tue November 8
Tor: The second generation onion router.
Wed November 9
Preparation to the midterm.
Tue November 22
Midterm.
Wed November 23
Byzantine agreement, consensus, and interactive consistency. File consensus.pdf.
Exercise 20: For each of the six ordered pairs of problems among: the Byzantine agreement problem, the Consensus problem, and the Interactive consistency problem, demonstrate a reduction from the former to the latter.
Exercise 21: Modify Algorithm 14.1 (from file consensus.pdf) to design an early-stopping algorithm for consensus under failstop failures (that is, crash failures), that terminates within f ′ + 1 rounds, where f ′ , the actual number of stop-failures, is less than f. Prove the correctness of your algorithm. (Hint: A process can be required to send a message in each round, even if the value was sent in the earlier round. Processes should also track the other processes that failed, which is detectable by identifying the processes from which no message was received.)
Exercise 22: Prove that the leader election problem is not solvable under a crash failure. (You can use the FLP result without proving it.)
Wed November 29
Wed November 30
Tue December 6
Exercise 23: Make Paxos live with a failure detector ◊S.