Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位
證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

2.5. Virtual Synchrony

Loading...

Cloud Computing Concepts, Part 1

伊利诺伊大学香槟分校

4.5（721 個評分） | 63K 名學生已註冊

課程 1（共 6 門，云计算專項課程）

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.

查看授課大綱

您將學習的技能

Distributed Algorithm, Distributed Computing, C++, Cloud Computing

審閱

4.5（721 個評分）

5 stars
487 ratings
4 stars
157 ratings
3 stars
38 ratings
2 stars
17 ratings
1 star
22 ratings

WK

Feb 27, 2018

This is a great course with a good balance of just theory and concepts, with practical ideas and exercises. The programming exercise can be a bit annoying, but was enjoyable nonetheless.

VR

Dec 31, 2017

very happy with the course. got to know new concepts. assignments are awesome. enjoyed working on them. enjoyed the course. it would be good if we get a color and original certificate.

從本節課中

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.

2.1. Multicast Ordering16:54

2.2. Implementing Multicast Ordering 19:36

2.3. Implementing Multicast Ordering 27:51

2.4. Reliable Multicast5:33

2.5. Virtual Synchrony11:46

教學方

Indranil Gupta
Professor

腳本

[MUSIC]

So in this lecture we're going to look at how to combine a membership protocol or

failure introduction along with a Multicast.

This is often and

very popularly implemented in an abstraction known as virtual synchrony.

Virtual synchrony also known as view synchrony attempts to preserve multicast

ordering and reliability in spite of failures of what happened in the system.

It combines a membership protocol with a multicast protocol.

Systems that implemented virtual synchrony or

view synchrony, such as Isis from Cornell University have been used in

many important scenarios including the New York Stock Exchange,

the French Air Traffic Control System, and the Swiss Stock Exchange.

Virtual synchrony or view synchrony has an important concept known as Views.

Each process maintains a membership list and

you've seen how membership protocols work earlier in the course.

This membership list is called a View.

An update to the membership list is called a View Change.

For instance, if a process joins, this may be reflected in the view and

that would be a View Change.

If a process leaves or

a process fails then those would be reflected in the view as well.

That would be a View Change.

Multiple changes may be made to a view and that would

just count as a single View Change if those changes are made simultaneously.

So for instance.

A process P1 might be added to the view and

simultaneously process P2 might be drop from the view.

That would just be a single view change where both those updates were done

simultaneously.

Virtual synchrony or views synchrony guarantees that all the view

changes are delivered in the same order at all the correct processes in the group.

So for instance if a correct process P1 receives views,

which are somewhat like the following.

The first view has only itself, P1.

The second view has itself along with two other processes, P1, P3.

The next view only has P1 or P2, P3 was dropped.

And the next view has P1, P2 and P4, where P4 was added.

Then any of the correct process also received the same sequence of view changes

after it joins the group.

So, for instance, if you construct P2 and the views it receives,

P2's first view would be P1, P2, P3, because that's when it joins the group.

But after that, its next view would be P1, P2.

It would have to be the same as the next view that P1 got.

And then the third view that P2 reviews would also be the same as

P1's next view which will be P1, P2, P4 over here.

That is the same as P1's, our next view as well.

In other words, as long as you can see only the correct process in the group

of the sequence of view changes that they receive is in fact

the same as all the other current processes in the group.

When the process fails, then you stop considering it.

But as long as the process is alive, all the views that it receives

are in fact in the same order as the other correct process in the system.

Now the times at which the views are delivered at the processes might be

different at different process, but the ordering is the same.

So again, here the insistence is on the ordering of them being the same.

In other words, the views being totally audited in all of the processes, but

they may of course be delivered at different physical times.

And this is why it is somewhat known as virtual synchrony, but

we'll come back to the name later on.

So that's about abuse.

What about the multicasts that are sent out among the processes in the group?

Now a multicast M is said to be delivered in a view V at a process Pi If and

only if Pi receives the view V.

And then before Pi delivers the next view after V, it delivers multicast M.

because in other words multicast M is delivered in between view V and

the next view that follows V.

Then M is said to be delivered in the view V.

In other words, what we are saying is that when M is delivered

view V was the membership list at the process Pi.

Now multisynchronicity requires that the set of multicasts delivered in

a given view is the same set of multicasts at all the correct processes that

are in that view.

This says that suppose the view consists of

to P3 then the set of multicasts received at P1 in that same view

is the same the set of multicasts received P2 in the same view.

In other words, what happens in a view stays in that view.

It does not go outside that view.

Okay, this is a good rule of thumb to remember virtual synchrony by.

He also required the sender of the mutlicast message to believe to that

view otherwise it would make sense for a multicast to be received.

Within a view when the sender is not a part of the view itself.

And what this means is that, if a process Pi does not deliver a multicast M in view

V, while other processes in the view V delivered multicast M in that same view,

V, then Pi will be forcibly removed from the next view delivered.

After we've add these other processes.

So, yo have to go with what he rest of the group is doing otherwise you might be

forcibly removed from that group if you don't satisfy group.

So, let's see a few examples that are both correct from the and also incorrect

form the viewpoint of So here's our first example with process P1, P2, P3, and P4.

The first view that all of them deliver consists of all four processes, so

that's our group.

Then P1 sends out a multicast message M1, P2 sends out a multicast message M2,

P4 sends out a multicast message M3, but P4 crashes after that.

Because P4 crashes, the next view that is delivered at P1, P2, P3, the remaining

members in the group Consists of only P1, P2, P3, and that's fine, okay?

Now the message M1 is delivered in the first view,

which causes all the four processes.

M2 is also delivered in the first view.

M2 is not delivered in P4, but that's fine because P4 crashed anyway.

Now the message M3 from P4 is also delivered at P1, P2, P3 as well as P4 and

it is delivered in the same view that consists of all the four processes.

Okay, so satisfies virtual synchrony.

This particular run over here.

However if I make a small change which is that a P3 delivers the second view

first and only then delivers the multicast n one from p one.

This would not satisfy virtual synchrony because what happens in the view

does not stay in the view.

In other words m1 is delivered by p2 in the earlier view but

delivered at p3 in the second view.

And that does not satisfy virtual synchrony.

This satisfies virtual synchrony, where P3 is forced out of the group, and

only P1 and P2 are left in the group.

And the set of multicast messages of P1 and

P2 received in the old first view are identical.

Okay, this satisfies virtual synchrony.

Here's another example of a route that does not satisfy virtual synchrony.

Why does it not satisfy virtual synchrony?

Well Notice here that we have the modech

as message m2 that is received at process p1 but is not received at process p3.

But p3 was is a part of the next view so

in other words this is a multi pass message m that is not

completely reliably delivered inside the group inside the old view.

Okay so this does not satisfy virtual synchrony.

This satisfies virtual synchrony here because M2 is in fact not delivered at any

of the members in the group in the old view.

It's not delivered at P2 either, and this has virtual synchrony because essentially

M2 as a multicast was never sent out, so never delivered at all in the group.

Does not satisfy what you need here you notice that the multi-cache text message,

m1 and m2 willing to the correct view, and the older view in all across but

m3 is delivered in the next view at process v1 and process v2.

And it's delivered in all view process p3,

because this does not satisfy virtual synchrony.

You might think that moving this view ahead now satisfied both virtual synchrony

because [INAUDIBLE] at all the other processes in the system and

all the current processes but

this [INAUDIBLE] because by the time the semantic [INAUDIBLE] is delivered.

The view does not include the sender p 4 of that multicast message anymore, and

so because p 4 is not part of the second view delivered at the correct processes,

the run that I'm showing here is also

not correct as far as virtual synchrony is concerned.

And finally here is an example where dropped by the system and

it's not able to tolerate any of the processes of the group and

this satisfies of course virtual synchrony because what happens in

the view stays in the view and before it has crashed.

So, virtual synchrony or virtual synchronous systems implement membership

protocols in the form of views, and also multicasts in terms of reliability, and

they want to ensure reliability within each view.

If you want to implement ordering in a virtual synchronous system you can do that

too because ordering is orthogonal to reliability, so

you can have a Virtually synchronous system that implements FIFO.

Or a virtually synchronous system that implements causal ordering, or

one that implements total ordering, or one that has a hybrid ordering scheme.

Now the name virtual synchrony comes about, or came about because it's part of

running on top of an asynchronous network with unpredictable delays and failures.

The order of membership changes and

multicasts that each process sees is the same at all the other processes.

If you use a total ordering protocol, even if it's a hybrid total ordering protocol,

then all the processes see the event in the system

happening in the same order as all the other processes in the system

as long as the processes that you're talking about are the correct processes.

Okay, so instead of landing on top of an asynchronous

network the view the processes behave are able to behave as if they're

running on top of a synchronous system where all the membership changes and

all the multi-cast messages are delivered in the same order.

But then actually the question should arise whether or not such an abstraction

could be used to implement a protocol that solves the consensus problem.

And the answer to this is no because virtually synchronous systems are still

susceptible to what is known as partitioning.

This may happen due to inaccurate failure detections because a process may be

mistakenly detected they will be removed from the group

Also processes may be forcibly removed from groups.

So an example of partitioning is shown on this slide, where initially,

all the four processes, P1, P2, P3, and P4 are a part of the view.

But subsequently, even though P4 is the only one that crashes, the view has become

partitioned where P1 considers only itself to be a part of the view.

And P2 and P3 are different view which consider only themselves to be a part

of the membership list.

So P1 is partitioned away from P23, and such partitions can happen in a virtually

synchronous system and this is the feature that prevents socially synchronous or

view synchronous systems from implementing consensus on top of them.

So, that wraps of our discussion of Multicast.

Multicast is an important building block for cloud computing systems that has been

so far many use to it systems for many decades.

Depending on the application need,

you can implement either a flavor of Multicast Ordering.

As far as your application requires level Multicast Ordering.

If you don't care about efficiency then you can implement

the Multicast Ordering Reliability.

Protocol that we saw or there are other radians of

multicache library protocols that we have discussed as well in this course.

And if you need something really,

really strong then you can implement virtual synchrony or real synchrony.

In fact there are many real systems out there that use these forms of multicast

in terms of their ordering that are and even a devotedly synchronize of framework.

[MUSIC]

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司