DOC PREVIEW
CORNELL CS 514 - Lecture Slides

This preview shows page 1-2-3-4-5-38-39-40-41-42-43-76-77-78-79-80 out of 80 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 80 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS514 Intermediate Course in Operating Systems Professor Ken Birman Ben Atkin TA Lecture 21 Nov 7 Bimodal Multicast Work is joint Ken Birman Mark Hayden Oznur Ozkasap Zhen Xiao Mihai Budiu Yaron Minsky Paper appeared in ACM Transactions on Computer Systems May 1999 Reliable Multicast Family of protocols for 1 n communication Increasingly important in modern networks Reliability tends to be at one of two extremes on the spectrum Very strong guarantees for example to replicate a controller position in an ATC system Best effort guarantees for applications like Internet conferencing or radio Reliable Multicast Common to try and reduce problems such as this to theory Issue is to specify the goal of the multicast protocol and then demonstrate that a particular implementation satisfies its spec Each form of reliability has its down specification and its own pros and cons Classical multicast problems Related to coordinated attack consensus The two schools of reliable multicast Virtual synchrony model Isis Horus Ensemble All or nothing message delivery with ordering Membership managed on behalf of group State transfer to joining member Scalable reliable multicast Local repair of problems but no end to end guarantees Virtual Synchrony Model G0 p q G1 p q r s p G2 q r s G3 q r s t crash q r s t r s request to join r s added state xfer p fails t requests to join t added state xfer to date the only widely adopted model for consistency and fault tolerance in highly available networked applications Virtual Synchrony Tools Various forms of replication Replicated data replicate an object state transfer for starting new replicas 1 many event streams network news Load balanced and fault tolerant request execution Management of groups of nodes or machines in a network setting ATC system simplified Onboard Radar X 500 Directory Controllers Air Traffic Database flight plans etc Roles for reliable multicast Replicate the state of controller consoles so that a group of consoles can support a team of controllers fault tolerantly Roles for reliable multicast Distribute routine updates from the radar system every 3 5 seconds two kinds images and digital tracking info Roles for reliable multicast Distribute flight plan updates and decisions rarely very critical information Other settings that use reliable multicast Basis of several stock exchanges Could be used to implement enterprise database systems and wide area network services Could be the basis of web caching tools But vsync protocols don t scale well For small systems performance is great For large systems can demonstrate very good performance but only if applications cooperate In large systems under heavy load with applications that may act a little flakey performance is very hard to maintain Stock Exchange Problem Vsync multicast is too fragile Most members are healthy but one is slow Virtually synchronous Ensemble multicast protocols average throughput on nonperturbed members 250 group size 32 group size 64 group size 96 200 150 100 50 0 0 0 1 0 2 0 3 0 4 0 5 perturb rate 0 6 0 7 0 8 0 9 Throughput as one member of a multicast group is perturbed by forcing it to sleep for varying amounts of time Why does this happen Superficially because data for the slow process piles up in the sender s buffer causing flow control to kick in prematurely But why does the problem grow worse as a function of group size with just one red process Our theory is that small perturbations happen all the time but more study is needed Dilemma confronting developers Application is extremely critical stock market air traffic control medical system Hence need a strong model guarantees SRM RMTP etc model is too weak Anyhow we ve seen that they don t scale either But these applications often have a softrealtime subsystem Steady data generation May need to deliver over a large scale Today introduce a new design pt Bimodal multicast is reliable in a sense that can be formalized at least for some networks Generalization for larger class of networks should be possible but maybe not easy Protocol is also very stable under steady load even if 25 of processes are perturbed Scalable in much the same way as SRM Bimodal Attack Consensus is impossible Attack General commands soldiers If almost all attack victory is certain If very few attack they will perish but Empire survives If many attack Empire is lost Worse and worse General sends orders via couriers who might perish or get lost in the forest no spies or traitors Some of the armies are sick with flu They won t fight and may not even have healthy couriers to participate in protocol Message omission crash and timing faults Properties Desired Bimodal distribution of multicast delivery Ordering FIFO on sender basis Stability lets us garbage collect without violating bimodal distribution Detection of lost messages More desired properties Formal model allows us to reason about how the primitive will behave in real systems Scalable protocol costs background messages throughput do not degrade as a function of system size Extremely stable throughput Naming our new protocol Bimodal doesn t lend itself to traditional contractions bcast is taken bicast and bimcast sound pretty awful Focus on probabilistic nature of guarantees Call it pbcast for sure Historical footnote these are multicast protocols but everyone uses bcast in names Environment Will assume that most links have known throughput and loss properties Also assume that most processes are responsive to messages in bounded time But can tolerate some flakey links and some crashed or slow processes Start by using unreliable multicast to rapidly distribute the message But some messages may not get through and some processes may be faulty So initial state involves partial distribution of multicast s Periodically e g every 100ms each process sends a digest describing its state to some randomly selected group member The digest identifies messages It doesn t include them Recipient checks the gossip digest against its own history and solicits a copy of any missing message from the process that sent the gossip Processes respond to solicitations received during a round of gossip by retransmitting the requested message The round lasts much longer than a typical RPC time Delivery Garbage Collection Deliver a message when it is in FIFO order Garbage collect a message when you believe that no healthy process could still need a copy we used to wait 10 rounds but now are using gossip to detect this


View Full Document

CORNELL CS 514 - Lecture Slides

Documents in this Course
LECTURE

LECTURE

29 pages

LECTURE

LECTURE

28 pages

Load more
Download Lecture Slides
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Slides and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Slides 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?