Exercise 4: Monday 22.11. or Thursday 25.11.

1. Describe how NTP clock synchronization works
2. Which design ideas has NTP borrowed from
   1. Christian's algorithm?
   2. The Berkeley algorithm?
3. Lamport clocks can be used to agree on the global timing of a series of events. Simulate the algorithm given by Raynal and Signal in 1996 for three processes A, B, and C. Present each process' local clocks given the following order of events. In the shorthand, snd means "sends message to", rcv means "receives message from", and ticks n means "advances local clock by n". Initially, the local clocks read A=59, B=80, C=75.
   1. A snd B; B ticks 6; B rcv A; B send C; C ticks 8; C rcv B; C snd A; A ticks 31; A rcv C
4. An interesting dilemma regarding Vector Clocks concerns last year's Exercise 4, task 3, section b).  Please familiarize yourself with the task description before reading its model answer. Now,
   1. Describe the full state of the given Bulletin Board System: processes, channels, and messages
   2. Argue for or against the model answer. Is it correct? Under what circumstances should local events increment the vector clock, if any?
5.  The Bully Algorithm:
   1. 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?
   2. Does the bully algorithm work properly even if during the election the state of some member changes (present <=> absent) ?

Please note:

Task #4 (Vector Clocks) is worth 4 points, whereas the others are worth 1 p. If you only do one task for this exercise, do #4, but do it well.