Computer Science 425 Distributed SystemsReplicationBasic Mode of ReplicationReplication ManagementSlide 5Group CommunicationViewsSlide 8View Synchronous CommunicationExample: View Synchronous CommunicationView SynchronyBack to ReplicationLinearizabilitySequential ConsistencyPassive (Primary-Backup) ReplicationFault Tolerance in Passive ReplicationActive ReplicationFault Tolerance in Active ReplicationSummary 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-1Lecture 23-1Computer Science 425Distributed SystemsComputer Science 425Distributed SystemsLecture 23Replication ControlReading: Section 15.1-15.3 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-2Lecture 23-2Replication Replication 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 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-3Lecture 23-3Basic Mode of ReplicationBasic Mode of Replication Replication Transparency 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)ClientFront EndRMRMRMClientFront EndClientFront EndServiceserverserverserverReplica Manager` 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-4Lecture 23-4Replication Management Replication Management Request Communication Requests can be made to a single RM or to multiple RMs Coordination: The RMs decide whether the request is to be applied the order of requestsFIFO 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. 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-5Lecture 23-5Replication Management Replication Management Agreement: The RMs attempt to reach consensus on the effect of the request. E.g., Two phase commit through a coordinatorIf 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 FE returns the first response to arrive. 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-6Lecture 23-6Group Communication Group Communication “Member”= process (e.g., RM) Static Groups: group membership is pre-defined Dynamic Groups: Members may join and leave, as necessaryGroup SendAddress ExpansionMulticast Comm.Membership ManagementLeaveFailJoinGroup 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-7Lecture 23-7Views Views A group membership service maintains group views, which are lists of current group members. This is NOT a list maintained by a one member, but…Each member maintains its own local viewA 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) 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-8Lecture 23-8Views Views 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 delivered at p.Exception: partitioning of group. Solutions to partitioning:Primary partition: allow only majority partition to proceedAllow any and all partitions to proceed Choice depends on consistency requirements.Ignore partitions for the rest of the lecture. 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-9Lecture 23-9View Synchronous CommunicationView Synchronous CommunicationView 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 VAll View Delivery conditions (Order, Integrity and Non-triviality conditions, from last slide) are satisfied“What happens in the View, stays in the View” 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-10Lecture 23-10Example: View Synchronous CommunicationExample: View Synchronous Communication pqrV(p,q,r)pqrV(p,q,r)pqrV(p,q,r)pqrV(p,q,r)XXXV(q,r)V(q,r)V(q,r)V(q,r)XXXNot AllowedNot AllowedAllowedAllowed 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 23-11Lecture 23-11View SynchronyView Synchrony•When a new
View Full Document
Unlocking...