Tsinghua University

Introduction to Distributed Systems
Spring 2013

 
 
Overview  
Syllabus  
Schedule  
Labs  
Homework  
Final Project  

Homework

Requirement
After each lecture, there will be some homework assignments. You should finish the home assignments and submit before the next lecture. Provide written answers to the following questions. Try to be in detail but concise. You can discuss with your classmates but you have to answer these questions by yourself.
Homework 1 : Overview and Google File System
  1. Read the paper of Google File System and describe the mechanism for data recovery. Suppose that there about 1000 machines in the cluster and at about the same time, 10 of them crashed. What will the system do to recover the copy numbers back to 3. How long might this work take? (Hints: we have to first detect the failure of the crashed machines (master or chunkserver). Some recovery plan should be generated and then perform the plan.)
  2. I have given an example of relaxed consistency of GFS with the operation of append (the position of the data is not defined). Go back to read the paper again and give another example to show the consistency works for GFS but not for POSIX file system.(Hints: concurrent writes.)
Homework 2 : Distributed Building Blocks
  1. Write simple server and client programs to use the select API to implement a text based chat, support group chatting. (Using the multi-thread version).
  2. Implement the synchronous and asynchronous versions of RPC in a document. Try your best to implement the mechanism as detail as possible.
  3. There is another programming interface called epoll. Try to find the information by yourself and describe why epoll is better (or worse) than select or poll.
Homework 3 : Data Intensive Super Computing
  1. Suppose that 100 files are stored in the GFS of directory /input/ and you want to execute the mapreduce program of wordcount. Try your best to describe the steps until the final results are gotten. (How can your program be loaded to each machine in the cluster? How to divide the data? How to feed your program with data? How to schedule the map tasks and reduce tasks in the cluster? I have given you some information in the lecture. If you find it difficult, you can refer to the implementation of Hadoop.)
  2. How can a platform such as MapReduce to support the SQL structural query language. If you are the architecture designer, how can you achieve this goal? (We have describe the mechanism of Dryad, you can replace the engine with MapReduce.)
Homework 4 : DSM and Sequential Consistency
  1. Why IVY does sort poorly? Analyze the procedures as detail as possible. Hints: suppose that you put the data in the distributed shared memory and go through the sorting phases.
  2. We have discussed the fixed manager way to implement the sequential consistency. Can you find a way to eliminate the fixed manager? (two fixed managers? broadcast? or dynamic manager? or even no manager?) Try to design your own way or read the paper and try to express the mechanism in your own language. Use figures and maybe animations if possible.
Homework 5 : Relaxed Consistency
  1. Design the vector clock part of TreadMarks in detail and implement the LRC model using the vector clock. (on your submitted doc file)
Homework 6 : Time in distributed systems
  1. In the class, I labelled the synchronization time and modification time for some figures. Please label the vector times for other figures by yourself and understand why the algorithm proposed is correct (why two vectors instead of one).
Homework 10 : Replicated State Machine and Paxos
  1. Think about you want to build a distributed replicated file system e.g. the file system will be kept the same among 5 nodes. Design your system with Paxos to achieve this goal. Describe how the read and write operations are applied to the replicated file system
  2. Suppose there are 7 accepters in a group. Someone check the accepted list in each accepter but only partial information is released. In one situation, 7 accepters accept the proposals of < n1, V>, < n2, V>, < n3, V>, < n4, V>, < n5, V>, < n6, V>, < n7, V> respectively, which means V is the same among all the proposals but nx might be different. Is this the state that a value is decided? If so, try to prove, otherwise, give a contradictory example.
  3. In another situation, we get 4 proposals accepted by the accepters. They are <5, V>, <6, V>, <7, V>, <8,V> respectively for each accepter. Is this the state that a value is decided?
  4. Why Paxos needs the prepare phase? Can we just use accept phase to send accept messages to acceptors as it can be rejected?
 
2013 High Performance Computing Institute, DCST, Tsinghua