DOC PREVIEW
U of I CS 425 - LECTURE

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

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

Unformatted text preview:

Computer Science 425 Distributed Systems (Fall 2009)AcknowledgementAdministrative Plan for TodayA Gossip Replica ManagerUpdate OperationsUpdate Operation (Cont’d)Exchange of Gossiping MessagesQuery OperationsSelecting Gossip PartnersExamples of Highly Available ServicesTransactions on Replicated DataOne Copy SerializationCoordination in Primary-Backup Replication Service Two Phase Commit Protocol For Replicated ObjectsCommunication in Two-Phase Commit ProtocolPrimary Copy Replication (Approach 1)Read One/Write All Replication (Approach 2)Available Copies Replication (Approach 3)Available Copies ApproachThe Impact of RM FailureLocal Validation (using Our Example)Network PartitionDealing with Network PartitionsQuorum Approaches for Network PartitionsStatic Quorums Voting with Static Quorums Quorum Consensus ExamplesOptimistic Quorum Approaches View-based Quorum View-based Quorum - details Example: View-based Quorum Example: View-based Quorum (cont’d) SummaryComputer Science 425Distributed Systems(Fall 2009)Lecture 24Transactions with ReplicationReading: Section 15.5Klara NahrstedtAcknowledgement• 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 • 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 QualcommRepresentative will be on Tuesday, December 8 afternoon - details will be announced. • HW4 posted– Deadline December 1, 2009 (Tuesday)Plan for Today• Gossiping Architecture – Review• Transactions on replicated objects• Communication via 2PC Protocol for Replicated objects (no failures)– Primary copy replication approach – Read one/write all replication approach– Available copies replication approach • Replications under failures– RM failure– Network partition» Quorum-based approachesA Gossip Replica ManagerReplica timestampUpdate logValue timestampValueExecuted operation tableStableupdatesUpdatesGossipmessagesFEReplicatimestampReplica logOperationID Update PrevFEReplica managerOther replica managersTimestamp tableUpdate Operations• Each update request u contains– The update operation, u.op– The FE’s timestamp, u.prev– A unique id that the FE generates, u.id.• Upon receipt of an update request, the RM i– Check if u has been processed by looking up u.id in the executed operation table and in the update log and executed operation table.– If not, increment the i-th element in the replica timestamp by 1 to keep track of the number of updates directly received from FEs.– Place a record for the update in the RM’s log.logRecord := <i, ts, u.op, u.prev, u.id>where ts is derived from u.prev by replacing u.prev’s ith element by the ith element of its replica timestamp.– Return ts back to the FE, which merges it with its timestamp.Update Operation (Cont’d)• The stability condition for an update u is u.prev <= valueTSi.e., All the updates on which this update depends have already been applied to the value.• When the update operation u becomes stable, the RM does the following– value := apply(value, u.op)– valueTS := merge(valueTS, ts) (update the value timestamp)– executed := executed U {u.id} (update the executed operation table)Exchange of Gossiping Messages• A gossip message m consists of the log of the RM, m.log, and the replica timestamp, m.ts.– Replica timestamp contains info about non-stable updates• An RM that receives a gossip message has three tasks:– (1) Merge the arriving log with its own.» Let replicaTS denote the recipient RM’s replica timestamp. A record r in m.log is added to the recipient’s log unless r.ts <= replicaTS.» replicaTS merge(replicaTS, m.ts)– (2) Apply any updates that have become stable but not been executed (stable updates in the arrived log may cause some pending updates become stable)– (3) Garbage collect: Eliminate records from the log and the executed operation table when it is known that the updates have been applied everywhere.Query Operations• A query request q contains the operation, q.op, and the timestamp, q.prev, sent by the FE.• Let valueTS denote the RM’s value timestamp, then q can be applied ifq.prev <= valueTS• The RM keeps q on a hold back queue until the condition is fulfilled.– If valueTs is (2,5,5) and q.prev is (2,4,6), then one update from RM3is missing.• Once the query is applied, the RM returns new valueTS to the FE (along with the value), and the FE merges new with its timestamp.Selecting Gossip Partners• The frequency with which RMs send gossip messages depends on the application.• Policy for choosing a partner to exchange gossip with:– Random policies: choose a partner randomly (perhaps with weighted probabilities)– Deterministic policies: a RM can examine its timestamp table and choose the RM that is the furthest behind in the updates it has received.– Topological policies: arrange the RMs into an overlay graph. Choose graph edges based on small round-trip times (RTTs), e.g., ring or Chord.» Each has its own merits and drawbacks. The ring topology produces relatively little communication but is subject to high transmission latencies since gossip has to traverse several RMs.• Example: Network News Transport Protocol (NNTP) uses gossip communication. Your updates to class.cs425 are spread among News servers using the gossip protocol!• Gives probabilistically reliable and fast dissemination of data with very low background bandwidth– Analogous to the spread of gossip in society.Examples of Highly Available Services• Bayou– Replicated database with weaker guarantees than sequential consistency» Uses gossip, timestamps and concept of anti-entropy– Anti-Entropy - Anti-entropy protocols for repairing replicated data, which operate by comparing replicas and reconciling differences.– Complete anti-entropy (CAE)» Reconcile all inconsistent states– Selective anti-entropy (SAE)» Selectively reconcile inconsistent states• Coda– Provides high availability in spite of disconnected operation, e.g., roving and transiently-disconnected laptops– Based on AFS– Aims to provide Constant data


View Full Document

U of I CS 425 - LECTURE

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

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