Study-exercises (Iceland Edition)

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 lessons and additional exercise time 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 the that instead. In addition, as the examination and grading (0-10) for the course will be 100% based on the hand-in of this assignment, the time normally available for exam preparation should be spent on the study exercise.

In the study-exercise in the Distributed Systems course you are going to program a text-book distributed algorithm, and a simple example/application using it. 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.

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 with others, but sharing of code, design templates, code sketches etc. will be considered cheating. Beware of the usual rules regarding plagiarism.
3. Do the best you can in the allocated time.
4. You can get help from the teachers for solving the exercise in the normal course-hours (see lecture plan) only!

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. Other choices may be possible, but please consult me before starting.

1. Implement the RRA client-server communication protocol on UDP. Demonstrate it with a simple 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.

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 API
• C+Sockets API (unix/windows)

Expectations and Deliverables

You are going to write a small distributed application and report on it: It is the expectation that the exercise results in a running program  that demonstrate the basic and central features and use of the algorithm.

The deliverable will be a small report consisting of the following parts:

1. An explanation of the problem you try to solve (use scenario/application)
2. An explanation(presentation of the algorithm in your own words
3. The code of your implementation
4. A printout of the produced output of the program where the important steps of the algorithm appears or that enables the use scenario/application to be seen/verified
5. Some amount of discussion and reflection. E.g., solution/design alternatives. Known limitations/errors. How do you handle node crashes? How could it (alternatively) be handled? What have you learned? What was easy/difficult?

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. Of course it will be good to run the system truly distributed among several hosts. Do also not spend time on fancy user interfaces or GUIs - simple textual (input) output suffices. 

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  during the course time allocated to the exercise.  You are welcome (recommended) to hand-in your (intermediate) solution or contact the lecturer for feedback/discussions. 

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.