Tutorial 3: Logical clocks

Question 1

Consider the time-event diagram depicted in Figure 1.1 and accomplish the following tasks. Each arrow in the diagram represents a message transmission. For example, a is the sending event and b is the receiving event for a message that is sent by process A to process B.

Answer 1

Timestamp each event based on the Logical Clock algorithm introduced by Lamport.

Question 2

Timestamp each event based on the Vector Clock algorithm.

Answer 2

Question 3

Using only the Vector Clock timestamps calculated in subtask (b) show whether, for each of the below event pairs, the happened-before relation (→) holds or not. Two events that are not in happened-before relation are also called concurrent (∥) events.

Answer 3

Question 4

Can we certainly determine the existence of either happened-before or concurrency relation between a pair of events only by knowing logical clock timestamps?

Answer 4

Only by knowing logical clock timestamps, we cannot determine the existence of either happened-before or concur- rency relation between a pair of events. In the depicted diagram L(a) < L(c), which would lead us to the following happened-before relation a → c. However, as previously showed, a concurrency relation (a || c) was demonstrated using vector clocks.

Question 5

Assume an asynchronous distributed system without failures that is comprised of n processes: P = { p1 , p2 , . . . , pn }. The only available communication mechanism in this system is broadcast, i.e., if a process sends a messages, this message is delivered to all processes in the system including the sender itself. Now, this system should be provided with a new feature referred to as atomic total-order broadcast (ATO-broadcast). In ATO-broadcast each process pi (1 ≤ i ≤ n) receives massages in the same order as every other process.

For example, if process pi receives messages in the order [m2,m1,m6 …,mk], then all other processes must receive mes- sages in this order. We assume that processes are aware of their processIds (i.e., {p1,p2,…,pn}) and that no message gets lost in the communication between processes. Also, messages from the same sender are received in the order that they were sent (i.e., FIFO channel).

Design an algorithm to provide the system with this feature using Lamport clocks and process IDs. Hint: Write two pseudo code snippets. One describes the algorithm on the sender side (i.e., function broadcastATO(msg)), the other describes the algorithm on the receiver side (i.e., function onReceiveATO(msg)). In the pseudo code, you are allowed to use basic data structures like arrays, lists, queues, etc. with a simplified syntax.

Answer 5

Assume that each process in the system has a logical clock, which is updated every time a message is sent or received, respectively. Further assume that each process maintains an ordered message queue that caches messages ordered by the tuple (timestamp, processId), i.e., totally ordered. The following explains how ATO-broadcast is realized.

Question 6

Given the following definition and the logical clock algorithms discussed in the lecture, provide an algorithm to implement Causally-ordered broadcast (CO-broadcast). CO-broadcast extends the usual broadcast semantics with the following properties: (Note: → is the happens-before relation).

(i) Let m and m′ be two broadcast messages such that broadcast(m) → broadcast(m′), then each process must receive m before m′;
(ii) Let m and m′ be two broadcast messages such that broadcast(m) ∥ broadcast(m′), then m and m′ can be received in different orders by different processes;

Answer 6