0:07

In this lecture, we'll see vector clocks,

which is another way of assigning timestamps to events in a distributed system.

Vector timestamps are used in cloud computing systems such as Riak,

which is a key-value store.

In this approach, each process uses a vector of integer clocks.

Think of this as an area of integer clocks.

This is as opposed to integer clocks by

themselves which were used in the Lamport timestamps approach.

Suppose there are N processes in the group numbered one through

N. Each vector at each process is going to have N elements.

So, process i would maintain the vector V sub i,

1 through N. This vector has N elements.

The jth element of the vector at process i,

V sub i of j,

is i's knowledge of the latest events that have happened at process j,

because of whenever an event happens at process j and some message gets sent over to i,

then Vi of j might get updated.

However, j might also send messages to other processes,

and this might get really transitively to i,

and this would result in Vi of j also getting incremented.

You would see as we discuss the rules.

So, how do you increment vector clocks?

We discussed the rules for incrementing Lamport clocks.

Rules for incrementing vector clocks are simple,

they are similar to the Lamport clock but they're slightly different.

Whenever a process executes an instruction or sends a message to say this is process i,

it only increments the ith element of its vector clock.

So, only V sub i of i incremented

whenever a process executes an instruction or sends a message.

When a message is sent, it carries a send-event's vector timestamp.

The entire vector here is assigned as a timestamp to that send-event,

and this entire vector is carried along with that particular message.

What does a process do when it receives a message?

Well, when it receives a message with a vector timestamp in there,

it uses it to update its own local vector clock.

The ith element of the vector clock at

the receiving process for i is simply incremented by one,

because it stands for the number of events that have happened at process i.

For each of the other elements in the vector,

it simply takes the maximum of the corresponding element

in the incoming message and in the local loop clock,

and it takes the maximum of those two and it sets it to

be the corresponding jth element in the local clock itself.

Again, there are two simple rules.

You simply increment your local ith element for every event,

and whenever you receive a message you take the max for

every other element in the vector.

So, let's see this for our earlier example.

Again, the same example as we saw previously.

So, all the clock values here are initialized to be all zeros at all the processes.

Again, these are local clocks,

only getting updated by those processes.

So, the process P1 executes an instruction.

It simply assigns it an event (1, 0,

0) because it increments the first element of the vector,

that's because process one is P1.

Similarly, when P3 sends a message to P2,

it increments the third element of the vector because it is P3,

and assigns this resulting vector as the timestamp to the send-event of this message.

The message also carries this timestamp (0,0,1),

so that when P2 receives it,

it can then use it to update its local clock.

Remember again, that when it receives this message,

P2 will simply update the second element of the vector by one and increments it by one.

And for every other element, it takes the max

from the corresponding elements in the local clock.

So, zero here and zero here, sorry.

Zero here and zero here result in zero for

the first element and one from the received messaged,

and zero in the local clock for the third element result in a max of one,

being set for the third element of the local clock.

So,(0,1,1) is assigned as the timestamp for the received event

of this particular message being received at P2 from P3.

Next, what happens in the system is that P1 sends a message to P2.

In order to do this,

it increments its first element from one to two,

(2,0,0) is assigned as the timestamp of the send-event here,

and that is carried with the message.

When the message is received at P2,

it increments its second element from one to two,

that's shown in blue here.

The other elements are all maxed.

So, the green element, the first element

is taken from the received message because that's

higher than the corresponding first element in the local clock.

And the third element is taken from the local clock,

that's highlighted in red, the one,

because that's higher than what is in the received message.

Okay, so (2,1,1) is the resulting timestamp of the received event over here,

and that is also updated to be P2's current clock.

So, if you play the rules forward,

you can see for yourself that

these timestamps are true and these follow the rules that is laid out earlier.

So, one of the reasons for preferring vector timestamp was that they obey causality.

So, let's see the rules for obeying causality.

Two vector timestamps, VT1 and VT2,

assigned to events E1 and E2 respectively,

are equal to each other if and only if the corresponding elements are all equal.

So, the ith element of VT1 equals the ith element of VT2,

for all i equaling one through

N. Vector timestamp VT1 is less than or equal to vector timestamp VT2,

if the ith element of VT1 is less than or equal to the corresponding ith element

of VT2, for all i.

Now, given this, we can say the two events E1 and E2,

with vector timestamps VT1 and VT2, are causally related.

That is, E1 happens before E2,

if and only if VT1 is strictly less than VT2.

Okay, this is different than less than or equal to.

VT1 is strictly less than VT2,

if and only if the following conditions are true: VT1 is less than or equal to VT2,

so the corresponding elements of VT1

are less than or equal to the corresponding elements of VT2.

But also, there exists some value of j such that,

the jth element of VT1 is strictly less than the jth element of VT2.

Okay, so, if these two conditions are true,

then VT1 is said to be less than VT2,

and is also true that the event to which VT1 is assigned as

a timestamp happens before the event to which VT2 is assigned as a timestamp.

Now, we can also say that two events are concurrent, VT1 and VT2,

if and only if neither VT1 is less or equal to VT2,

nor is VT2 less than or equal to VT1.

Okay. This means that VT1 and VT2 are concurrent with each other.

We denote it using three vertical bars between VT1 and VT2.

So, let's see our example again and verify that these conditions are,

in fact, true for some of the events in this particular run.

So, A happens before B,

and you notice that the timestamps assigned to them obey a causality.

So, (1,0,0) is less than or equal to (2,0,0) because, for all the elements,

the ith element of the left vector is

less than or equal to the ith element of the right vector,

and there is some index in this case one,

where the first element of the left vector

is strictly less than the first element of this second vector.

Similarly, B happens before F is obeyed by the fact that (2,0,0) is less than (2,2,1),

you have less than or equal to obeyed here,

and several elements are smaller in the left vector compared to the right vector.

Similarly, A happens before F again is obeyed because (1,0,0) is less than (2,2,1).

Similarly, you can verify that for these other

happens before relationships outlined here,

the corresponding vectors obey the causalities.

So, let's look at an example. F happens before J,

F is assigned a timestamp of (2,2,1) and G is assigned a timestamp of (5,3,3).

It's clear that all the elements of F are

strictly less than all the elements of G. That's not required,

you just need one of the elements to be

smaller while all the other elements are less than or equal to,

but in any case here,

the left vector (2,2,1) is strictly less than the right vector (5,3,3).

Similarly, for H and G,

you see that (0,0,1) is less than (2,3,1),

for H happens before J,

you see that (0,0,1) is less than (5,3,3).

Similarly, C happens before J is obeyed,

because (3,0,0) which is assigned to C is less than J's timestamp which is (5,3,3).

What about those concurrent events?

Well, C and F are concurrent events,

and you see that they get timestamps (3,0,0) and (2,2,1) respectively.

These obey causality because they are not causally,

we cannot say that one of the vector timestamps is less than the other. Why is this?

Well, because each of the vectors has at least one element

that is greater than the corresponding element in the other vector.

C's vector has the first element, three,

which is greater than the corresponding element in the other vector, two.

And F's vector has the third element, one,

which is greater than the corresponding third element in the C's vector which is zero.

Neither of these two vectors is related to each other by less than or equal to,

and so, we can say that C and F are,

in fact, concurrent with respect to each other.

Similarly, H and C are two other concurrent events,

and H's third element, one,

is greater than the third element in C,

and C's first element, three,

is greater than the first element in H,

which is having a value of zero over here.

Okay. So, in this way you can use the vector timestamps to

verify that two events are either causally related if the vector timestamps are,

in fact, one of them is strictly less than the other.

And, on the other hand,

if you cannot find a strictly less than relationship between two vector timestamps,

then you know for sure that they are concurrent events.

So, in Lamport timestamps,

we assigned integer clocks to events in a way that the timestamps obey causality.

But the problem there was that we could not distinguish

concurrent events based on their Lamport timestamps.

Vector timestamps come to the rescue,

where you can clearly identify when a pair of

events either are concurrent or are causally related to each other.

Vector timestamps obviously take

much more space at each process and also within the messages,

but you have the added advantage,

that you can identify concurrent events.

So, that wraps up our discussion of time and ordering.

Time is an essential problem to solve in anything in the distributed system,

because the different processes

have clocks that are not synchronized with respect to each other,

and yet we would like to assign timestamps to

events that happen at different processes in the distributed system.

One way to do this is to use time synchronization

to keep the clocks and processes close to each other,

if not identical, and then use these clocks to assign timestamps to events.

We discussed several algorithms for this including

the Cristian's algorithm, the NTP algorithm.

The Berkeley algorithm is essentially using synchronization only within the group,

but in all of these cases,

when you have a non-zero latencies in the underlying network,

you're going to have an error in the clock that you set.

So, the error is a function of the round-trip time.

You can avoid time synchronization issues all together

by instead assigning causal timestamps to events,

either Lamport timestamps or vector timestamps to events.