Distributed System : Clock

In a distributed system, there is no shared global clock that all process agreed on and can be used to order their operations.

Physical Clocks

Physical clock doesn’t give us the guarantee of the order of the operations between processes. We can’t simply depend on them.

Logical clocks

When a process sends a message to another process, a sol called synchronization point is created. The operation executed by the sender before the message was sent must have happened before the operation that the receiver executed after receiving it.

Lamport clock is a logical clock based on this idea. Every process has its own local logical clock with a numerical counter that follows specific rules,

1. The counter is initialized with 0
2. A process increments its counter before each local event (e.g., message sending event);
3. When a process sends a message, it includes its counter value with the message after executing step 2;
4. In receiving a message, the counter of the recipient is updated, if necessary, to the greater of its current counter and the timestamp in the received message. The counter is then incremented by 1 before the message is considered received.

Fig-1 : The processes using Lamport clock

In pseudocode, the algorithm for sending is:

# event is known
time = time + 1;
# event happens
send(message, time);

(message, time_stamp) = receive();
time = max(time_stamp, time) + 1;

Problems with Lamport clock:

The rules guarantee that if the operation O1 happens before operation O2, the logical timestamp of O1 is less that the of O2. But the vice versa is not true. If the logical timestamp of operation O3 is less than than O4, the Lamport clock doesn’t gurantee that O3 happened before O4.

For example, in the Figure 1, operation E didn’t happen before operation C even if their timestamp seems to imply it.

Vector clocks

Vector clocks guarantees that if two operations can be ordered by their logical timestamps, then one must have happened-before the other.

It’s implemebted with array of counters, one for each process in the system.

A process updates it’s local vector clock based on following rules

• Initially all clocks are zero.e
• Each time a process experiences an internal event, it increments its own logical in the vector by one.
• Each time a process sends a message, it increments its own logical clock in the vector by one then it pairs the message with a copy of its own vector and finally sends the pair.
• Each time a process receives a message-vector clock pair, it increments its own logical clock in the vector by one and updates each element in its vector by taking the maximum of the value in its own vector clock and the value in the vector in the received pair (for every element).

Fig-2: Each process has a vector clock represented with an array of three counter

References:

• Understaing distributed system by Roberto Vitillo
• https://en.wikipedia.org/wiki/Lamport_timestamp
• https://en.wikipedia.org/wiki/Vector_clock