Study-exercises

Purpose

The purpose of the study-exercise is to provide the individual student with the opportunity of working on a problem that is larger, more complex, and that takes more time to solve than is normally possible within the normal exercise time associated with a lecture.  For this reason the study time of 2 "mini-modules" are allocated to the exercise. That is, two conventional lectures have been replaced by the study-exercise, and you are required to spend the time on that instead, i.e., you are supposed to work on the exercise for approximately 11 hours (corresponding to the study time of 2 times lecture time, normal exercise time and the preparation time).

In the study-exercise in the Distributed Systems course you are going to program a text-book distributed algorithm. The intention is that this should give you

• a solid and concrete understanding of distributed algorithms,
• an understanding of how to implement a distributed algorithm,
• get hands-on and tangible experience with distributed systems,
• obtain detailed insight into a single distributed algorithm.

In my experience such an exercise gives you a valuable learning experience. The exercise is mandatory in the same sense as any other teaching activity at the university. 

Rules

1. You are going to work on the exercise individually, i.e. no group work!
2. You are allowed to discuss your problem and solution in small teams, but sharing of code, design templates, code sketches etc. will be considered cheating
3. If you have the course as an SE-course the study-exercise will be on the exam (be aware of rule 2).
4. Do the best you can in the allocated time.
5. You can get help from the assistant teachers for solving the exercise in the normal course-hours (see lecture plan) only!
6. You are welcome to hand-in your solution or contact the assistant teachers and lecturer for feedback. 

Choices

You may in principle pick any non-trivial algorithm from the text-book. If you pick one that is not on the following list, please consult the lecturer for approval.

1. Implement the RRA client-server communication protocol on UDP. Demonstrate it with a simple (eg bank account) server and multiple clients. Do not spend time on serialization and external data-representation.
2. Implement a system of vector-clocks and use it to implement an algorithm that grants access to a shared resource in request order among a set of clients that communicate internally.
3. Implement Ricart and Agrawala's mutex algorithm.
4. Implement the bully election algorithm.
5. Implement a simple distributed flat file-system with some cache coherency-scheme
6. lmplement an algorithm for reliable multicast.
7. Implement an algorithm for ordered multicast (FIFO, total, or causal ordered multicast).
8. Implement the algorithm for consensus in a synchronous system.
9. Routing in a p2p system by the pastry routing algorithm.

If you have time add a simple application demonstrating the use of the algorithm. Some examples:

• distributed jukebox: A number of hosts wishes to have a common music play-back system such that all hosts plays the same songs (or voice announcements). Each host may add to (maybe modify) the playlist. The playback may be administered decentralized or by a coordinator (who must be re-elected in case of failure.) 
• shared whiteboard. A number of clients shares a virtual whiteboard. However, only one may write to the board at a time. Use a mutex algorithm. 
• chat application: Consider either a solution with a  coordinator+election, or one using some kind of multi-cast.
• chat with group management. The participating processes are notified whenever a client enters or leaves the chat room. Is ordering important?
• Alive manager: An alive manager keeps a list of process ID's that it consideres alive (eg. by pinging). Clients may ask the alive manager for the list of processes it considderes alive. Use an election algorithm to re-elect the manager in case of manager failure. 
• A general mutex coordinator: Centralized mutex+coordinator+election
• Info screen system: a number of secretaries posts announcements on a number of information screens (both represented by computers in a DS). Demonstrate reliable and/or ordered multicast.
• boiler nanny: A numbder of nodes coorporate in controlling a critical boiler system by opening and closing a valve based on temperature readings. Create consensus when nodes may crash (fail-stop). What if they may exhibit arbitrary failures?
• game consus. A number of processes cooperate in playing the computer part of a game. Each process evaluates a set of game moves and proposes the best to the others. They then have to agree on the best proposed move and update their private game state for the next round. Solve the problem in the case of crash failures. What if they may exhibit arbitrary failures?

You are advised to create your solution incrementally, ie. starting with the simplest possible setting and then gradually introduce features and generalize. Also, consider the following generic issues about your solution: How do you detect and handle failures? Are your implementation correct according to the correctness criteria and system assumptions of the algorithm?  What about performance both algorithmically and at the code-level?

The program must be executable as a set of processes using message passing (or RMI) only.  You may use any programming language you choose, but we recommend that you use one of the following:

• Java+Java Sockets API
• Java+JavaRMI
• .NET Remoting
• .Net + Sockets

Expectations and Deliverables

It is the expectation that the exercise results in a running program  that demonstrate the basic and central features of the algorithm. It is OK to only implement it it in a simplified setting such as e.g. by letting the processes run on the same host as long as they are in separate address spaces, or fixing number, configuration and topology of the processes etc. Do also not spend time on fancy user interfaces or GUIs - simple textual (input) output suffices.  Similarly you are not expected to write program documentation, but you should orally be able to explain the structure and solution strategy. The "deliverables" is a printout of the program and a print of the output of the program during a simple application run or test. You should be able to explain that the program correctly implements the algorithms or at least beware of the implementation limitation / bugs. I expect that the core part of most of the algorithms can be implemented in a few pages of source code (plus helper/container classes). The emphasis is on the required communication, synchronization, timer and fault handling, not on nice efficient sequential programming.

You may be given feedback to your solution from the lecturer and teaching assistants during the course time allocated to the exercise.   

Exam

If you have the course as an SE-course the study-exercise will be on the exam. Two of the exam questions will be labeled "study exercise".

You must bring two hardcopy print-out of the code and a sample run of your program. You are requested to prepare a presentation of the problem and your solution (you may bring slides - but blackboard drawings are perfect; we recommend printing the code snaps on slides so you can give a structured code walk-through of the IMPORTANT aspects of your solution).  

It is the expectation that an average student should be able to complete the exercise to a passing level in the allocated time. If you feel that your practical programming skills and computer systems understanding is below average or not in compliance with the required background of the course you may need to spend more time.

A non-correct working implementation does not necessarily equal a non-pass grade, but some reflection on the encountered problems are especially recommended in this case.

There will NOT be time for DEMO at the exam. The 15 minutes of examination time simply does not allow time for this.