DOC PREVIEW
U of I CS 425 - Replication Control

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 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 33 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 33 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 33 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 33 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 33 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 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Computer Computer Science Science 425 425 Distributed Distributed Systems Systems Fall Fall 2009 2009 Lecture 23 Replication Control Reading Section 15 1 15 4 1 Klara Nahrstedt Acknowledgement Acknowledgement The slides during this semester are based on ideas and material from the following sources Slides prepared by Professors M Harandi J Hou I Gupta N Vaidya Y Ch Hu S Mitra Slides from Professor S Gosh s course at University o Iowa Administrative Administrative MP3 posted Deadline December 7 Monday pre competition Top five groups will be selected for final demonstration on Tuuesday December 8 Demonstration Signup Sheets for Monday 12 7 will be made available Main Demonstration in front of the Qualcom Representative will be on Tuesday December 8 afternoon details will be announced HW4 posted November 10 2009 Deadline December 1 2009 Tuesday Plan Plan for for Today Today Replication Review of View Concept and Group Communication Passive Replication Active Replication Gossiping Architecture Replicatio Replicatio n n Enhancing Services by replicating data Load Balancing Example Workload is shared between the servers by binding all the server IP addresses to the service s DNS name A DNS lookup of the site results in one of the servers IP addresses being returned in a round robin fashion Fault Tolerance Under the fail stop model if up to f of f 1 servers crash at least one remains to supply the service Increased Availability Service may not be available when servers fail or when the network is partitioned P probability that one server fails 1 P availability of service e g P 5 service is available 95 of the time Pn probability that n servers fail 1 Pn availability of service e g P 5 n 3 service available 99 875 of the time Basic Basic Mode Mode of of Replication Replication Client Front End Client Front End Client Front End Replication Transparency Replica Manager RM RM RM server server server Service User client need not know that multiple physical copies of data exist Replication Consistency Data is consistent on all of the replicas or is in the process of becoming consistent Replication Replication Management Management 5 5 Steps Steps Request Communication Requests can be made to a single Replication Manager RM or to multiple RMs Coordination The RMs decide whether the request is to be applied the order of requests FIFO ordering If a FE issues r then r then any correct RM handles r and then r Causal ordering If the issue of r happened before the issue of r then any correct RM handles r and then r Total ordering If a correct RM handles r and then r then any correct RM handles r and then r Execution The RMs execute the request tentatively Replication Replication Management Management Agreement The RMs attempt to reach consensus on the effect of the request E g Two phase commit through a coordinator If this succeeds effect of request is made permanent Response One or more RMs responds to the front end In the case of fail stop model the Front End FE returns the first response to arrive Group Group Communication Communication Review Review Group Address Expansion Group Send Multicast Comm Leave Membership Management Fail Join Member process e g RM Static Groups group membership is pre defined Dynamic Groups Members may join and leave as necessary Group Group Views Views Review Review A group membership service maintains group views which are lists of current group members This is NOT a list maintained by one member but Each member maintains its own local view A view Vp g is process p s understanding of its group list of members Example V p 0 g p V p 1 g p q V p 2 g p q r V p 3 g p r A new group view is disseminated throughout the group whenever a member joins or leaves Member detecting failure of another member reliable multicasts a view change message requires causal total ordering for multicasts Group Group Views Views Review Review An event is said to occur in a view Vp i g if the event occurs at p and at the time of event occurrence p has delivered Vp i g but has not yet delivered Vp i 1 g Messages sent out in a view i need to be delivered in that view at all members in the group What happens in the View stays in the View Requirements for view delivery Order If p delivers Vi g and then Vi 1 g then no other process q delivers Vi 1 g before Vi g Integrity If p delivers Vi g then p is in Vi g Non triviality if process q joins a group and becomes reachable from process p then eventually q will always be present in the views that are delivered at p View View Synchronous Synchronous Communication Communication Review Review View Synchronous Communication Group Membership Service Reliable multicast The following guarantees are provided for multicast messages Integrity If p delivered message m p will not deliver m again Also p group m Validity Correct processes always deliver all messages That is if p delivers message m in view V g and some process q V g does not deliver m in view V g then the next view V g delivered at p will not include q Agreement Correct processes deliver the same set of messages in any view if p delivers m in V and then delivers V then all processes in V V deliver m in view V All View Delivery conditions Order Integrity and Non triviality conditions from last slide are satisfied What happens in the View stays in the View Example Example View View Synchronous Synchronous Communication Communication Allowed Allowed p q X p X X X q r r V q r V p q r p X p q q r r V p q r V q r Not Allowed V q r V p q r X V p q r V q r Not Allowed FAULT TOLERANT FAULT TOLERANT SERVICES SERVICES Back Back to to Replication Replication Client Front End Client Front End Client Front End RM RM RM server server server Service Need consistent updates to all copies of an object Linearizability Sequential Consistency Linearizabili Linearizabili ty ty Let the sequence of read and update operations that client i performs in some execution be oi1 oi2 Program order for the client A replicated shared object service is linearizable if for any execution real there is some interleaving of operations virtual issued by all clients that meets the specification of a single correct copy of objects is consistent with the real times at which each operation occurred during the execution Main goal any client will see at any point of time a copy of the object that is correct and consistent Sequential Sequential Consistency Consistency The real time requirement of linearizability is hard if not impossible to


View Full Document

U of I CS 425 - Replication Control

Documents in this Course
Lecture 8

Lecture 8

23 pages

TIPS

TIPS

3 pages

The Grid

The Grid

41 pages

Lecture 4

Lecture 4

27 pages

Lecture 4

Lecture 4

20 pages

The Grid

The Grid

41 pages

LECTURE 5

LECTURE 5

25 pages

Multicast

Multicast

23 pages

LECTURE

LECTURE

34 pages

Load more
Download Replication Control
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 Replication Control 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 Replication Control 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?