Distributed Systems

3/K07, January 30-31, 2007
Tanenbaum Ch 2, 4, 5



1. Explain (to somebody who tries to understand what this is about) how
   Lamport clocks reflect "causal ordering" of events (i.e., if a -> b 
   then C(a)<C(b)). Give examples which clarify the concept (incl. one
   where C(a)<C(b) but a->b does not hold).
   Why is it not possible to use Lamport clocks to implement, for example,
   a distributed bulletin board (with a requirement for causality)?
   Where can the Lamport clocks be used, then? Give an example.

2. Describe in detail the decentralized implementation of total ordering
   (Tanenbaum: Section 5.2.1; lecture slide 16 of Chapter 5.1). 
   Show that it performs correctly:
   - in all hold-back queues the messages are in the same order
   - after having received all ack's the message at the head of the 
     hold-back queue can be sure that nobody will ever appear in front 
     of it.
   Is it strictly necessary that each message is acknowledged? 
   Total ordering is easy to implement as a centralized service. How?
   Give some examples where total ordering is needed.

3. A bulletin board has been replicated on three servers P1, P2, P3.
   Each member of the group has access to a local replicate of the board.
   The message passing system then forwards each message to all replicates.
   The transfer times vary considerably, and the messages do not necessar-
   ily arrive in the order they have been sent, but they have to fulfill
   the  "happened-before" relation ("causal ordering").
   a) Explain to the end user what "causal ordering" means.
   b) How can you implement "causal ordering" using vector timestamps?
      Describe the idea and explain why it works.
   c) The timestamps of the replicas happen to be (5,2,8), (4,5,6) and
      (4,5,8). Three users, each at his/her own bulletin board, decide
      to add a comment to the bulletin board. Simulate the subsequent
      behavior of the system.
   d) Give an algorithm which implements "causal ordering" for this case.
   (The crucial question: how does the message passing system know
   that a message can be delivered to the bulletin-board application,
   or, in other words, that all causal predecessors of this message
   have already arrived?)

4. The application is based on the cooperation of a fixed group of N
   processes; each of these is located on its own node, and the links
   between the nodes are rather slow. Available for interprocess communi-
   cation are send/receive operations with the syntax
     send <message> to <recipient>
     receive <message> from <sender>
   (you can freely choose any combination of the persistence /synchroni-
   zation alternatives, but always give the reasons for your choice).
   Using these operations, how would you implement a reliable multicast
   operation, intended for the application layer; the syntax of the
   operation is "multicast <message> to <list_of_recipients>" ?
   The operation should be as efficient as possible. Hence, compare
   alternative solutions, and give the reasons for your choice.