DOC PREVIEW
Pitt CS 2510 - Replicas why and why not

This preview shows page 1-2-3-4 out of 12 pages.

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

Unformatted text preview:

1Replicas: why and why not?•Reliability–Tolerance to component failures–Tolerance to corrupted data•Performance–Benefits scalability–Allows for concurrent access to resources (data/objects/processors)–Reduces the delay for geographically dispersed resources•Disadvantages–Cost of replications is high–Maintaining consistency of multiple copies is tough–Implementation is harder (e.g., different users have different needs of number of replicas and more or less accurate consistency models)Object ReplicationProblem: If objects (or data) are shared, we need to do something about concurrent accesses to guarantee state consistency.2Object Replication solutionsA remote object capable of handling concurrent invocations on its own.A remote object for which an object adapter is required to handle concurrent invocationsWhere in the world is…Object ReplicationA distributed system for replication-aware distributed objects is more customizableA distributed system responsible for replica management is more general and easier to implement3Performance, replication, scalability•Main issue: To keep replicas consistent, we generally need to ensure that all conflicting operations are done in the the same order everywhere•Conflicting operations (example from transactions):–Read–write conflict: a read operation and a write operation act concurrently–Write–write conflicts: two concurrent write operations•Tradeoff: guaranteeing global ordering on conflicting operations may be a costly operation, downgrading scalability•Solution: weaken consistency requirements so that hopefully global synchronization can be avoided•This solution only lends itself to some applications, not all.Data-Centric Consistency Models (1)•The general organization of a logical data store, physically distributed and replicated across multiple resources.•Consistency model: a contract between a (distributed) data store and processes, in which the data store specifies preciselywhat the results of read and write operations are in the presence of concurrency. Processes agree or don’t use it.4Data-Centric Consistency Models (2)•Strong consistency models: Operations on shared data are synchronized:–Strict consistency (related to “absolute global” time)–Sequential consistency (what we are used to)–Causal consistency (maintains only causal relations)–FIFO consistency (maintains only individual ordering)•Weak consistency models: Synchronization occurs only when shared data is locked and unlocked:–General weak consistency–Release consistency–Entry consistency•Observation: The weaker the consistency model, the easier it is to build a scalable solution.Strict ConsistencyAny read to a shared data item X returns the value stored by the most recent write operation on X.•It may be expensive to maintain strict consistency•Does everyone need it? Who does?•How can it be better/easier/less costly?•Note: Strict consistency is what you get in the “normal”uniprocessor, sequential case, where your program does not interfere with any other program.A strictly consistent store. A store that is not strictly consistent.5Sequential ConsistencyThe result of any execution is the same as if the operations of all processes were executed in some sequential order, and the operations of each individual process appear in this sequence in the order specified by its program.•This is for interleavedexecutions: there is ONE total ordering for all operationsA strictly consistent store. A store that is not strictly consistent. LinearizabilitySequential consistency + operations are orderedaccording to a global time.•This may be more practical, since it assumes loosely synchronized clocks (Lamport clocks? NTP?)•Since the definition of “global time” is loose, so is the consistency model.•Therefore, linearizability is weaker than strict consistency, but stronger than sequential consistency. Happy medium.6Casual Consistency (1)•Events a and b are causally related if a causes or influences b.•Events that are not causally-related are concurrent.•Causal consistency: Writes that are potentially causally related must be seen by all processes in the same order. Concurrent writes may be seen in a different order on different machines.This sequence is allowed with a casually-consistent store, but not with sequentially or strictly consistency (what writes are concurrent?)Casual Consistency (2)A correct sequence of events in a casually-consistent store. WHY?A violation of a casually-consistent store. WHY?7FIFO ConsistencyWrites done by a single process are seen by all other processes in the order in which they were issued, but writes from different processes may be seen in a different order by different processes.A valid sequence of events of FIFO consistencyIs it valid for causal consistency?What about sequential consistency?FIFO ConsistencyTwo concurrent processes.What’s the beef?y = 1;if (x == 0) kill (P1);x = 1;if (y == 0) kill (P2);Process P2Process P1•Implementation is simple: •Attach a PID+sequence# to each event•Perform writes according to the this ordering8Summary of Consistency Modelsnot using synchronization operationsAll processes see writes from each other in the order they were used. Writes from different processes may not always be seen inthat orderFIFOAll processes see causally-related shared accesses in the same order.CausalAll processes see all shared accesses in the same order. Accesses are not ordered in timeSequentialAll processes must see all shared accesses in the same order. Accesses are furthermore ordered according to a (nonunique) global timestampLinearizabilityAbsolute time ordering of all shared accesses matters.StrictDescriptionConsistencyWeak Consistency (1)Properties:•Accesses to synchronization variables associated with a data store are sequentially consistent•No operation on a synchronization variable is allowed to be performed until all previous writes have been completed everywhere•No read or write operation on data items are allowed to be performed until all previous operations to synchronization variables have been performed.Implementation: use a synchronization phaseBasic idea: You don’t care that reads and writes of a series of operations are immediately known to other processes. You just want the effect of the series itself to be known.9Weak Consistency (2)An invalid sequence for weak consistency.A valid sequence


View Full Document

Pitt CS 2510 - Replicas why and why not

Download Replicas why and why not
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 Replicas why and why not 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 Replicas why and why not 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?