Distributed systems
Fall 2008
Exercise 3


Topic: Clocks, synchronization, elections

1. Describe how NTP clock synchronization works. 

2. 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)?
   How close to the "causal ordering" can we get using Lamport's 
   (scalar) clock?
   Where can the Lamport clocks be used, then? Give an example.


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) The timestamps of the replicas happen to be (6,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.
   c) Give an algorithm which implements "causal ordering" for this case.
      (The message passing subsystem receives messages from a local user
      and from the network, takes care of the "clocks" and timestamps,
      and implements all needed queueing.
      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. a) Suppose that two members of a group detect the demise of the
      coordinator simultaneuously and both decide to hold an election
      using the bully algorithm. What happens?
   b) Does the bully algorithm work properly even if during the election
      the state of some member changes (present <=> absent) ?