Hi there.
So, uh, in, um, uh, the next couple of lectures
we'll be seeing how to implement
the flavors of multicast ordering
which we saw in, uh, the previous lecture.
Uh, these flavors were FIFO, causal and total ordering.
In this lecture, uh, today we'll see, uh, how to implement FIFO
as well as, um, uh, total ordering,
and in the next lecture we'll see, uh, causal ordering.
So here's how to implement FIFO ordering.
Each receiver in the group
maintains a per-sender sequence number.
These sequence numbers are integers,
uh, starting from zero.
Uh, suppose we have N processes in the group, P1 through PN.
Uh, essentially, Pi, which is the ith process,
would maintain a vector of sequence numbers, uh, Pi[1...N].
Initially, all these, um, elements
in the vector are, uh, zeros.
Uh, Pi[j], which is the jth element in Pi's vector,
is the latest sequence number that Pi has received
from the process Pj.
If j=i, remember that Pi will have,
uh, its, uh, an, uh, a sequence number for itself.
This would be the latest sequence number
that Pi has sent out
to the, uh, other processes in the group.
So, uh, what do you do?
How do you update these vectors?
So, um, uh, when you want to, uh, uh, send
a, uh, multicast message, uh, from a process Pj,
uh, the first thing you do, uh, at process Pj
is that you set the jth element of Pj's vector,
uh, to be one more than itself,
so you increment the j's element,
j-j's element-jth element of P's vector.
Uh, then you include, uh, this, uh, jth element, the new Pj[j],
in a multicast message as the sequence number
of that multicast message.
You also say that of course Pj is the center of this multicast.
Now what does the process, uh, Pi do
when it receives this multicast message from Pj?
Uh, it looks at, uh, the sender, which is Pj,
it looks at the sequence number in the message,
which, say, is S, uh, it checks whether or not,
uh, S is, uh, equal to the jth, uh, element
of Pi's, uh, sequence number vector, plus 1, okay?
Essentially it checks whether or not, uh, the sequence number S
being received from Pj is the next sequence number
that Pi expects to receive from Pj.
If so, then it can deliver, uh, the, uh, multicast message
to the application,
and the m-and the application can do whatever it wants
with this particular multicast message,
and then it can-it can set, uh, the jth element
of its own, uh, vector, uh, to be, uh, 1 plus its old value.
However, if this condition is not true,
uh, if this is not, uh, the
next, uh, element in the vector, uh,
then it buffers this multicast, uh, message.
Now it buffers it, essentially we are assuming here
that, uh, the sequence number
is going to be later on, um, in the series.
So for instance, if the next sequence number
that Pi is expecting from Pj is 5,
and it receives, uh, the sequence number um-uh-uh, 7
then it needs to wait
until, uh, 5 has been received and delivered,
and then 6 has been received and delivered,
and only then can it deliver 7.
However, if duplication is possible in the network,
for instance, if the next, um-uh, message
that Pi is waiting from, uh, Pj
should have a sequence number 5,
but you receive, uh, um, uh, a multicast from Pj
with the sequence number 3,
then you can drop that multicast message,
uh, and, uh, safely, because you already know
that you have delivered that to the application.
Okay, uh, let's look at an example
of, uh, how the FIFO ordering algorithm works.
So here are four processes P1 through P4.
Time moves from left to right for each of the processes.
Each process maintains a vector.
The number of elements in the vector is 4
because there are four processes in the system.
Remember that the jth element at, say, process P1
corresponds to how many multicasts P1 has received
so far from, uh, Pj.
So here are all the multicasts that are sent out in the group.
P1 sends two multicasts, uh, one followed by another,
and then P3 later on sends another multicast.
So let's see what happens with the first multicast from P1.
P1's sequence number, uh, for this first multicast is 1
because it's sent no multicasts so far.
P1's first element of its vector is 0.
That's incremented to 1,
and that, uh, new value is assigned as a sequence number
to the multicast message.
When P2 receives this multicast message,
it checks its first element of the vector, which is zero,
and so in fact the sequence number
is the next sequence number it's expecting,
and the multicast is delivered,
and the vector- the vector is updated
to be 1 followed by three 0.
The same is true at, uh, P4,
which also delivers a multicast message
and updates its vector to be one followed by three zeros.
Uh, however, when P1's multicast is, uh, received at P3,
P1's second multicast has already been received,
and if P3 delivered these multicasts
in this order shown in the slide,
then you would violate FIFO ordering,
because, uh, P1's two multicasts
are delivered in the wrong order at P3.
So let's see what happens with the second multicast from P1.
When it's sent out it has a sequence number of 2,
because P1's first element is already one.
That's incremented to be two,
and that is included as sequence number.
When this multicast is received at, uh, P3 early,
uh, it sees-P3 sees that P1-its element for P1
is in fact 0, and the next sequence number it is expecting
is, uh, 1, and so the sequence number 2 message
that has just been received needs to be buffered.
However, later on at some point of time soon after, uh,
P3 receives a first multicast from P1.
This is in fact the next sequence number it is expecting.
It then delivers this second multicast message immediately,
and then after this,
the sequence number that it's expecting from P1 is now 2,
because P3 has updated its vector
to be one followed by three zeros.
And at this point immediately the sequence number 2 message
from P1 can be delivered right away.
After P1's sequence number 1 message,
the vector can be updated
to be 2 followed by three 0,
and we have satisfied FIFO ordering.
When, uh, P2 receives P1's multicast, second multicast,
delivers it
because that's the next sequence number 2 is expecting,
then, uh, P3 sends out its multicast message.
This is a sequence number of 1
because P3 has not sent any multicasts yet.
P3's third element, uh, is in fact 0.
That's incremented to 1, and that is included
as a sequence number in the multicast message.
P1 and P2, when they receive this multicast message from P3,
they check that their third elements of the vector are 0,
and so the sequence number 1 is in fact
what they're expecting from P3,
and they deliver the multicast message
and update their vectors accordingly.
However, P4, when it receives this, what does it do?
Well, when P4 receives the multicast message from P3,
first it can deliver it,
because it's the next sequence number it's expecting from P3,
and that's fine,
and then later on it, uh, receives the sequence num-
the sequence number 2 message from P1,
and it can deliver it right away
and update its vector to be 2,0,1,0.
This is fine; this satisfies FIFO ordering,
even though the P3 sequence number 1 message
was delivered first at P4
before P1's sequence number 2 message,
while this ordering of deliveries was reversed in P3.
But this is fine, because FIFO doesn't necessarily look
at the order-ordering of messages
sent by different sending processes.
So that was, uh, FIFO.
Next, uh, we'll look at total ordering
and how to implement it.
Once again, just to remind you, total ordering ensures that, uh,
uh, the, um, ordering of deliveries of messages
at all the processes are the same,
uh, somewhat independent of what order they were sent in.
