{small lecturenumber - heblocknumber :} Previously on cs682: Causal deliveryaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Previously on cs682: Vector clocksaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Previously on cs682: Vector Clock exampleaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Previously on cs682: Consensusaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Why is replication useful?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Why is replication useful?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Client-side replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Fault toleranceaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Outlineaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Client Requirementsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} System Modeladdtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Fault tolerance exampleaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Correctnessaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Passive Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Passive Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Passive Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Group Communicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Group membershipaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} View-synchronous communicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} View-synchronous communicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Comments on passive replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Failuresaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Active Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Active Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Active Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Active replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Failuresaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Lazy Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Lazy Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Lazy Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Lazy Replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Coordinating with lazy replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Querying with lazy replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Updating with lazy replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Updating with lazy replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Gossipingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Gossipingaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Comments on lazy replicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Failuresaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Summaryaddtocounter {blocknumber}{1}Distributed Software DevelopmentReplicationChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p.1/??12-0: Previously on cs682: Causaldeliverycausal delivery says that if send(m1) → send(m2), thendeliver(m1) → (m2) when different processes are sendingm1and m2.Logical clocks aren’t enough to give us causal delivery.Department of Computer Science — University of San Francisco – p.2/??12-1: Previously on cs682: VectorclocksSolution: keep a “logical clock” for each process.these are stored in a vector V C.Assumes number of processes in known and fixed.Update rule:V C(e)[i] = V C[i] + 1 for send and internal.V C(e) = max(V C, T S(m)) for receive; thenV C(e)[i] = V C[i] + 1On receive, the vector clock takes the max on acomponent-by-component basis, then updates the localclock.Department of Computer Science — University of San Francisco – p.3/??12-2: Previously on cs682: VectorClock examplep1p2p3(1,0,0)(0,1,0)(0,0,1)(2,1,0)(1,0,2)(1,0,3)(1,0,4)(3,1,3)(1,2,4)(4,1,3)(4,3,4)(1,0,5) (5,1,6)(5,1,3) (6,1,3)Department of Computer Science — University of San Francisco – p.4/??12-3: Previously on cs682:ConsensusIf we don’t have reliable communication, consensus isimpossible, even without failures.With reliable communication, we can solve consensus forcrash failures.In asynchronous systems, it is impossible to guaranteethat we will reach consensus, even in the presence of asingle crash failure.This means that we can’t do:Asynchronous Byzantine generalsAsynchronous totally ordered multicastDepartment of Computer Science — University of San Francisco – p.5/??12-4: ReplicationReplication is the maintenance of copies of data atmultiple computers.Enhances a service by providing:Fault toleranceImproved performanceIncreased availabilityInformation redundanceDepartment of Computer Science — University of San Francisco – p.6/??12-5: Why is replication useful?Increased performance.By moving data closer to a client, latency is reduced.Web caching, proxy servers are an example of this.Performance is improved most effectively with immutabledata.If the client is going to change the data and send itback, performance gains are reduced.Department of Computer Science — University of San Francisco – p.7/??12-6: Why is replication useful?Increased availability.Many services need to be highly availableReplication provides a way of overcoming server failures.If a server will fail with probability p, then we candetermine how many servers are needed to provide agiven level of service:Avail = 1 − pnFor example, if a server has a 5% chance of failure over agiven time period, and we want 99.9% availability, weneed at least 4 replicas.Department of Computer Science — University of San Francisco –
View Full Document
Unlocking...