New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Jonas Bartell


Marketplace > University of Pittsburgh > ComputerScienence > CS 2510 > COMPUTER OPERATING SYSTEMS
Jonas Bartell
GPA 3.77


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 11 page Class Notes was uploaded by Jonas Bartell on Monday October 26, 2015. The Class Notes belongs to CS 2510 at University of Pittsburgh taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/229375/cs-2510-university-of-pittsburgh in ComputerScienence at University of Pittsburgh.

Similar to CS 2510 at Pitt

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15
Replica Placement Model We consider objects and don t worry whether they contain just data or code or both Distinguish different processes A process is capable of hosting a replica of an object or data Permanent replicas Processmachine always having a replica Serverinitiated replica Process that can dynamically host a replica on request of another server in the data store Clientinitiated replica Process that can dynamically host a replica on request of a client client cache Replica Placement 1 x 9 Serverinitiated replication VA xx 7quot Clientinitiated replication Permanent Serverinitiated replicas The logical organization of different kinds of copies of a data store into three concentric rings Examples web servers file servers multicast trees ServerInitiated Replicas CZ Server without 9 copy of file F Server with P K copy of F Client c1 Q File F Server Q counts access from C1 and 02 as if they would come from Keep track of access counts per le aggregated by considering server closest to requesting clients Number of accesses drops below threshold D gtdrop le Number of accesses exceeds threshold R gtreplicate le Number of access between D and R gtmigrate le ClientInitiated Replicas More like a client cache 7 Keep it on disk 7 Keep it in memory 7 How much space to use 7 How long to keep copyreplica 7 How to detect data is stale Readonly les work best Sharing data among client processes may be good Sharing space is essential Update Propagation 13 Fmpagate umy nuh muunmwhdauun urupdate utten used fur mehes Transfer data r m Dpy m anumerdstnbuted databases FmpagzteLheupdateoptzvmtontu uthereupresa1su Elledacnv repllmuun ohsmm39nn Nu angle appmachls the best but depends hghly un amiable bandwidth and radrlurwnle mum at rephms Update Propagation 23 Fush ng updates sa39Va39rmmate d appruaeh m whmh update 15 pmpagated regardless whether target asked fur rt Puurng updates euen Hmuated appruaeh m wmeh euent requests tu be updated Nan se 1 Re pansetme anteater Update Propagation 33 Observation We can dynamically switch between pulling and pushing using leases A contract in which the server promises to push updates to the client until the lease expires Issue Make lease expiration time dependent on system s behavior adaptive leases Agebased leases An object that hasn t changed for a long time will not change in the near future so provide a longlasting lease Renewalfrequency based leases The more often a client requests a speci c object the longer the expiration time for that client for that object will be Statebased leases The more loaded a server is the shorter the expiration times become Question Why are we doing all this Epidemic Algorithms Basic idea Assume there are no writeiwrite con icts Update operations are initially performed at one or only a few replicas A replica passes its updated state to a limited number of neighbors Update propagation is lazy ie not immediate Eventually each update should reach every replica Anti entropy Each replica regularly chooses another replica at random and exchanges state differences leading to identical states at both afterwards Gossiping A replica which has just been updated ie has been contaminated tells a number of other replicas about its update contaminating them as well System Model We consider a collection servers each storing a number of objects Each object O has a primary server at which updates for O are always initiated avoiding writewrite con icts An update of object O at server S is always timestamped the value of O at S is denoted VALOS TOS denotes the timestamp of the value of object O at server S AntiEntropy Basic issue When a server S contacts another server S to exchange state information three different strategies can be followed Push S only forwards all its updates to S if TOS lt TOS then VALOS lt VALOS Pull S only fetched updates from S if TOS gt TOS then VALOS lt VALOS Push Pull S and S exchange their updates by pushing and pulling values Observation if each server periodically randomly chooses another server for exchanging updates an update is propagated in Olog 7 time units Question why is pushing alone not ef cient when many servers have already been updated G0331p1ng Basie model A server 5 havrng an update to report conLac other servers If a server rs contacted to whlch the update has already propagated 5 stops eontaetrng other server w th probabrlrty lk Ila rs the Eraetron of rgnorant servers r e whlch are unaware olthe update rt can be shown that vvrth rnany servers 5 gtwltle observatron Ifwe really have to ensure that all servers are eventually updated gosslplng alone rs not enougn Deleting Values em We aannatrernave an ald value fmm a 5m expert the renaval ta prap due trrne usrng eprdenra al e and agate lnstead rnere renaval wlll be undane rn g nthrns Solution Remaval has ta be regtsteed as a speclal update by rnsetrng a death cem mle Nextproblern When ta rernave a death aetr aate rtrs nat allawed ta stay fareve Run a glahal alganthrnta detect whether the rernaval rs kmwn eveyvvhee andthen aallett the death aertr aates laaks llke garbage sallettran Assume death cetr cates prap agate rn t rnrte trrne and ass crate a rnarnrnurnlrfeurne faraaetrt39raateaanhe dane atnsk afnatreaahrng all smels Nam rt rs neaessarythat a renaval attually reaches all servers Question What s the saalahrlrty pmblem heren Consistency Protocols Consistency protocol describes the implementation of a speci c consistency model We will concentrate only on sequential consistency Primarybased protocols Replicatedwrite protocols Cachecoherence protocols PrimaryBased Protocols 14 All read and write operations go to server Example used in traditional clientserver systems that do not support replication Client Client Single server for 39tem X Backup server W1 W4 R1 R4 Vl W2 d R2 L Ejantj lt7 W3 R3 Data store W1 Write request R1 Read request W2 Forward request to server for x R2 Forward request to server for x W3 Acknowledge write completed R3 Return response W4 Acknowledge write completed R4 Return response PrimaryBased Protocols 24 Primarybackup protocol writes are typically forwarded to server Client Client Primary server for item X Backup sener W1 Write request R1 Read request W2 Forward request to primary R2 Response to read W3 Tell backups to update W4 Acknowledge update W5 Acknowledge write completed Example Traditionally applied in distributed databases and le systems that require a high degree of fault tolerance Replicas are often placed on same LAN PrimaryBased Protocols 34 Primarybased localwrite protocol migrate the data do not replace it Client Current server New server for item x for item x B Eaj i 8 Data store 1 Read or write request 2 Forward request to current server for x 3 Move item x to client39s server 4 Return result of operation on client39s server Example Establishes only a fully distributed nonreplicated data store Useful when writes are expected to come in series from the same client eg mobile computing without replication PrimaryBased Protocols 44 Primarybackup protocol with local writes replicate data only for reading Client Client Old primary New primary for item x for item x Backup server R1 R2 W1 W3 A L lk W5 W5 W Al W4 Data store W5 W2 W4 W1 Write request R1 Read request W2 Move item x to new primary R2 Response to read W3 Acknowledge write completed W4 Tell backups to update W5 Acknowledge update Example Distributed shared memory systems but also mobile computing in disconnected mode ship all relevant les to user before disconnecting and update later on ReplicatedWrite Protocolsl2 0 Active replication Updates are forwarded to multiple replicas where they are carried out 0 One problem to deal with replicated invocations Client replicates 39 invocation request Object receives the same invocation three times 1 All replicas see the same invocation Replicated object ReplicatedWrite Protocols 22 Replicated invocations Centralized Solution Assign a coordinator on each side client and server which ensures that only one invocation a and one reply is send b Coordinator Coordinator of object B of object C Client replicates invocation request 1 Triple Modular Redundancy Simple to implement Vote on all three results Majority 50 1 wins Request is replicated to all servers Request Al A2 A3 QuorumBased Protocols Quorumbased protocols Ensure that each operation is carried out in such a way that a majority vote is established distinguish read quorum and write quorum Read quorum Example Lazy Replication Basic model number of replica servers jointly implement a causalconsistent data store 0 Clients normally talk to front ends which maintain data to ensure causal consistency Clients F W up Write queue Read queue iquot 3 EU UH Pending 1 D D D uij 1 Local serve request 1 E353 i k H 1 r l j I l l i i I Distributed data store


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.