So, uh, here's how to implement causal ordering.

Uh, each receiver, again, maintains a vector

of per-sender sequence numbers.

Uh, these are integers.

This is sort of like FIFO multicast, uh, but the meanings

of, uh, the, uh, um, sequence numbers are different,

and updating rules are slightly different.

Once again we have processes P1 through PN.

Uh, Pi maintains a vector, eh, of N elements, uh, Pi[1...N].

Initially, all the elements in the vector are zeroes.

The jth element of Pi's vector is the latest sequence number

that Pi has received from Pj.

This is very similar, again,

to the FIFO example you have seen in the previous lecture,

but again, the interpretations

and the updating rules are going to be different.

So here are the rules, in all their gory detail,

and then we'll see an example that discusses these rules.

So when you want to send a multicast message,

uh, at process Pj,

uh, Pj looks at the jth element of its vector

and increments it by one,

then it sends out the multicast message.

However, unlike FIFO it includes the entire vector

in the multicast message as a sequence number.

The entire vector is important because we want to check

for causality.

We wanna make sure that all the receivers are in fact

obeying causality.

So what do receivers do

when they receive a multicast message?

When Pi receives a multicast message from Pj,

and there is a vector M in, uh, the multicast message,

which is the timestamp of that multicast message itself

then, uh, you buffer that multicast message

until two conditions are true.

First, this is the next multicast message that Pi is

expecting from Pj.

In other words, the jth element of the message's vector

is in fact one more than the jth element of Pi's vector.

So that's the first condition.

Second, you wanna make sure

that the receiver satisfies causality.

All the multicasts anywhere in the group

which happen before this message M

have already been received at Pi, okay?

In other words, you want to make sure that for all k,

uh, not equal, uh, to j, the sender,

the kth element of the message's vector

is less than or equal to the kth element

of the receiver Pi's vector, okay?

This makes sure that the receiver has already seen

all the multicast messages on which Pi already depended,

or in other words,

all the multicast messages that happen before M's.

When these two conditions are true, then you can deliver

the multicast message M to the application,

and you can set the jth element of Pi's vector

to the jth element of M's vector,

showing that this message has been delivered.

You do not update any of the other elements

of the-of the- of Pi's vector,

because you don't necessarily know

of the other multicast messages that have been sent out

in the group.

So let's see an example again.

Here is a timeline with four processes, P1 through P4.

Time runs from left to right.

Each process maintains a vector.

The vector contains four elements,

because there are four processes in the group.

P1 sends out a multicast, uh, which is received

by all the other processes.

Notice that P2 receives P1's multicast first

and then sends out another multicast.

So P1's multicast here happens before;

causally happens before P2's multicast,

and so we want to make sure that these two multicasts

are delivered in the same order at all the recipients.

Similarly, P1's multicast is received at its P4, at P4,

and then P4 sends out a multicast, so again,

these two multicast sends from P1 and P4 are causally related.

However, P2's multicast send and P4's multicast send are

concurrent, and so they are not causally related.

So let's look at the vectors.

So P1 then sends out a multicast,

simply increments its sequence number,

which is the first sequence number,

and that entire vector 1 followed by three 0

is included as the sequence nu-

as the timestamp of the message when it is sent out.

When receivers receive this multicast message,

they use this to check whether or not to deliver the message.

P2, when it receives this message,

in fact checks that this is in fact the next, uh, vector

is-it is expecting from P1,

and it in fact satisfies causality

because all the vectors,

all the elements, all the other elements are 0,

and so it can deliver this multicast message from P1.

P4, uh, the rule is likewise, and can- it goes ahead

and delivers P1's multicast message.

Now, when P2 sends out its multicast,

it increments the second element of its vector,

so the vector for uh, the time stamped vector

for this multicast message from P2 is 1,1,0,0.

When P1 receives this multicast message from P2,

it sees that in fact

this is the next sequence number it is expecting from P2,

and that the receiver satisfies causality

because all the other elements are identical

to the incoming message,

and so it can deliver this multicast from P2.

However, when P3 receives this message from P2,

it sees that the first element in the incoming vector is one.

However, the first element in its local vector is 0.

In other words, P3 has not yet gone beyond the causality

and has not yet received some messages

on which P2's send is dependent upon.

So because it is missing the sequence number one from P1

uh, it buffers this multicast message from P2.

Subsequently, P4 sends out the multicast message,

which now has vector, uh, timestamp of 1,0,0,1.

P1 and P2 both receive this message,

and they are able to deliver it

because the receiver satisfies causality.

You can verify this for yourself.

However, when P3 receives this multicast message,

it sees that it is missing,

again uh, the message 1 from P1

which is included in the incoming multicast from P4

because P4's first element is 1.

However, P3's first element is a 0,

and so it buffers this multicast from P4 as well.

Uh, thereafter, when P1's multicast

is finally received at P3,

it sees that this is in fact

the next multicast message that it needs to deliver,

because causality is true,

and so it updates its timestamp

to be 1 followed by three 0,

and at this point it can deliver both P4's buffered multicast

as well as P2's buffered multicast.

It can deliver these two multicasts in any order,

because these are, uh, not causally dependent

on each other, otherwise the vectors would show it,

and so it goes ahead and delivers this,

and it updates its, uh, vector to be, uh, [1,1,0,1].

And finally of course P4 receives the multicast from P2

and it can go ahead and deliver this multicast message

and update its final vector to be 1, 1 and, ah, 0 and 1.