Cloud computing systems today, whether open-source or used inside companies, are built using a common set of core techniques, algorithms, and design philosophies – all centered around distributed systems. Learn about such fundamental distributed computing "concepts" for cloud computing. Some of these concepts include: clouds, MapReduce, key-value/NoSQL stores, classical distributed algorithms, widely-used distributed algorithms, scalability, trending areas, and much, much more! Know how these systems work from the inside out. Get your hands dirty using these concepts with provided homework exercises. In the programming assignments, implement some of these concepts in template code (programs) provided in the C++ programming language. Prior experience with C++ is required. The course also features interviews with leading researchers and managers, from both industry and academia.
2.2. Implementing Multicast Ordering 1
Loading...
來自 University of Illinois at Urbana-Champaign 的課程
Cloud Computing Concepts, Part 1
547 個評分
從本節課中
Week 5: Classical Distributed Algorithms
Lesson 1: This module covers how to calculate a distributed snapshot, leveraging causality again to circumvent the synchronization problem. Lesson 2: This lecture teaches how to order multicasts in any distributed system. Algorithms for assigning timestamp tags to multicasts using various flavors of ordering – FIFO, Causal, and Total – are covered. The module also covers virtual synchrony, a paradigm that combines reliable multicasts with membership views. Lesson 3: Consensus is one of the most important problems in a distributed system, enabling multiple machines to agree. This module uses Paxos, one of the most popular consensus solutions used in the industry today. Paxos is not perfect because consensus cannot be solved completely – an optional lecture presents the famous FLP proof of impossibility of consensus.
與講師見面
Indranil GuptaProfessor
Department of Computer Science
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.
So a-a popular approach to implement total ordering
is to use sequencer- uh, is to use a sequencer.
Uh, a special process is elected as a leader or a sequencer.
Uh, you will, uh, have seen leader election elsewhere
in this course,
um, and essentially in order to send a multicast message,
there's what the process Pi does.
It simply sends a multicast message M to the group,
along, uh, with sending it to the sequencer as well.
The sequencer in turn maintains a global sequence number S,
which initially has a value of 0.
When the sequencer receives the multicast message M
from any process,
it increments S and then it multicasts M
along with the sequence number S.
Okay, and this is multicast to the entire group again.
What does the process Pi do when it receives a multicast message?
Well Pi maintains
a local received global sequence number, Si, okay?
This is only one integer, not a vector, just a single integer.
This, um-uh, represents the next, uh, globally ordered
or totally ordered multicast that Pi is expecting to receive.
If Pi receives a multicast M, uh, message M from Pj,
it buffers that multicast message M
until it receives the sequence number message
for that same message M from the sequencer,
so until it receives,
um, a message from the sequencer that says
"Hey, for the multicast message M, the sequencer i
-the sequence number is S(M),"
and, um, but receiving this mult-this, uh,
sequencer message doesn't necessarily entail
that the multicast can be delivered right away.
The sequence numbers have to match up.
In other words, it has to wait until the S(M) value in, uh,
the message from the sequencer is one more than, uh,
the global sequence number Si that Pi is waiting for, okay?
So this ensures that in fact, uh, the multicast message, uh,
that Pi delivers next is in fact the next one
that Pi is waiting for.
Once it, uh, once this is true, it can then deliver the message,
this multicast, to the application,
and then it can increment Si, and then at this point of time,
if any buffered messages, uh, satisfy,
uh, these two conditions here,
then in fact they can be delivered as well,
and Si can be incremented.
So next, uh, lecture we'll see how to implement, uh,
causal ordering for multicasts.
