Versatile Computing .


26 views
Uploaded on:
Description
Mobile Computing. Panos Papadimitratos Wireless Networks Lab Department of Electrical Engineering Cornell University. Problem Context. Mobile Computing Environment. Limited Bandwidth High Latency Intermittent Connectivity Lower Reliability Low Physical Security
Transcripts
Slide 1

Versatile Computing Panos Papadimitratos Wireless Networks Lab Department of Electrical Engineering Cornell University

Slide 2

Problem Context

Slide 3

Mobile Computing Environment Limited Bandwidth High Latency Intermittent Connectivity Lower Reliability Low Physical Security Lower Processing Capability Higher Degree of Heterogeneity

Slide 4

Despite the misfortune.. Run Distributed Applications Provide Distributed Services Share Data Remain Consistent Remain Efficient

Slide 5

Why are things more troublesome? Network is NOT persistent Topological Changes Less Resources Consequently: Lower Availability Potential Inconsistencies

Slide 6

Two viewpoints "… Replicated, Highly Available, Weakly Consistent Storage System … " Develop Mobile Applications … minimize the reliance upon ceaseless network… "

Slide 7

Bayou Distributed Data Storage System Designed for a Mobile Computing Environment Non-Transparent Weakly-Consistent Replication Application-Specific Mechanisms to Detect & Resolve Conflicts Low Usage of the Network

Slide 8

Previous Work Theory of Epidemics Eventual Consistency Coda Disconnected Operation Optimistic Replication Consistency Application-particular resolvers Conflicts determination in light of document sort Log uncertain clashes, make mistake message Ficus Notes, Oracle, MS Access

Slide 9

System Model Client/Server Architecture - Transactional System Data are repeated to an arrangement of servers Applications keep running as customers Two Basic Operations: Read and Write Replication is Weakly Consistent Read-Any-Write-Any Model

Slide 10

System Model Server State Storage System Storage System Server State Anti-Entropy Read or Write Application Bayou API Client Stub Server State Storage System Application Bayou API Client Stub

Slide 11

Conflict Detection & Resolution Application-Specific Notion of Conflict Semantics Granularity – case: Scheduling Application Resolution Policy Semantics Automated Mechanisms Dependency Checks Merge Procedures

Slide 12

Dependency Checks Application-Supplied Query & Expected Result Query is Run at the Server against its present information If Check Fails, conjure Merge methodology

Slide 13

Merge Procedures High-level projects with application-particular learning Run by the Server Performed Atomically as a major aspect of Writes Attempt to Resolve the Conflict Produce a Revised Update to Apply

Slide 14

Handling Conflicts – An Example

Slide 15

Basic Anti-Entropy Goal: the compromise of copies\' information Pair-wise way One-way Operation Propagate Write Operations Accept-Order Constraint Prefix Property Version Vectors

Slide 16

Basic Anti-Entropy (proceeded with) S R.V Version Vector All Writes obscure to R For every w in S.Write_log if (R.V(w.server_ID) < w.accept_stamp) SendWrite(R,w)

Slide 17

A More Reasonable Approach Without a regularly developing Write Log Need a strategy for Truncating the Write Log Idea: An Update that is gotten by all Replicas require not be logged any more. Take into consideration an autonomous, forceful pruning by every Replica The idea of Stable or Committed Write is vital in the pruning procedure

Slide 18

Write Stability Stable Write : iff it has been executed for the last time by a server. Instinctively identical to Confirmation or Commitment Primary Commit Scheme Designate a Replica as Primary decides the request (position) of a Write when it first gets it. Stable Order Any Non-Committed Write is called Tentative

Slide 19

R.CSN Highest Commit Sequence Number R.V Version Vector First , All Committed Writes obscure to R Second , All Tentative Writes obscure to R if R.CSN < S.CSN for every w in S.Write_log if (w.accept_stamp < R.V(w.server_ID)) SendCommitNotification(… ) else SendWrite(… ) For every w in S.Write_log if (R.V(w.server_ID) < w.accept_stamp) SendWrite(R,w) Anti-Entropy (Revisited) S R

Slide 20

Write-Log Truncation Stable Order keeps up the Prefix Property Replicas can truncate any steady prefix from their Write Logs Incremental Reconciliation may not be conceivable Each Replica needs to recollect the overlooked Write Operations Full-Database Transfer

Slide 21

"Augmented" Anti-Entropy Session Guarantees Causal Order – Accept Stamp Reduce Client-Observed irregularities Eventual Consistency Define a Total Order utilizing the Server ID and the Causal Order Propagate Updates in this Total Order Provide Guarantees on the "quality" of the Replicas Data Content

Slide 22

Other issues Light-Weight Server Creation Security Update through transportable stockpiling media, i.e. floppy circles Link quality decides the recurrence of the performed against entropies

Slide 23

Experiments Measurements on a changed EXMH (e-mailer) that utilizations Bayou for putting away messages Only Committed Writes are proliferated Measure the execution time for an Anti-Entropy (100 Writes) over various system joins Network Transfer Inserting Newly Received Writes

Slide 24

Experiments - II

Slide 25

Bayou - Summary Support for Arbitrary Communication Topologies Operation over Low-Bandwidth Networks Incremental Progress Eventual Consistency Efficient Storage Management Propagation through Transportable Media Light-weight Management of Dynamic Replica Sets Arbitrary Policy Choices

Slide 26

Rover Toolkit Set of Software Tools for Development of Mobile Applications Two methodologies: Mobile-Transparent Applications Mobile-Aware Applications

Slide 27

Goals: Minimize Dependence on Continuous Connectivity Remotely Stored documents Optimize Utilization of Bandwidth Dynamic Division of Work

Slide 28

Previous Work Cedar Check-in Check-out Data Sharing Locus Type-particular Conflict Resolution Coda Optimistic Concurrency Control Pre-Fetching Bayou Tentative Data Session Guarantees

Slide 29

Toolkit Design Client-Server engineering Mobile Communication Support Re-locatable Dynamic Objects (RDO) Reduce Client/Server correspondence Update Shared Objects Code Shipping Queued Remote Procedure Call (QRPC) Non-Blocking Calls When Disconnected

Slide 30

Toolkit Design Application code & information are RDOs Rover-Applications Interface Primary Functions Create Session Import Invoke Export RDOs are cahced RDOs are languidly gotten

Slide 31

Toolkit Design Client-Side Application Modify/Resolve Object Conflict? Meanderer Library Import RDO Cache RDO Network Scheduler Export Log QRPC Log Mobile Host Server Resolved Log

Slide 32

Design Issues Communication Scheduling Computation Relocation Separate application from information Move calculation/information: customer s erver Object Replication – Pre-bringing Consistency Primary Copy, Tentative-Update Optimistic Concurrency Control Type-Specific Concurrency Control

Slide 33

Architecture App3 App 1 App 2 App3 App 1 App 2 Access Manager Operation Log Access Manager Operation Log Object Cache Object Cache Network Scheduler Network Scheduler Server Mobile Host Network

Slide 34

Implementation Issues Rover begins as a negligible piece Failure Recovery – Access Manager Log Size Batching of QPRCs Promises – Callback User Notification Application-Specific Conflict Resolution

Slide 35

Experiments Single Server, Multiple Clients Different Network Options TCP over remote connections Three setups: Compressed or Batched QRPCs Mobile-Transparent Application Mobile-Aware Applications

Slide 36

Experiments - II

Slide 37

Experiments - III

Slide 38

Experiments - IV

Slide 39

Rover - Summary QRPC benefits: RPCs are planned, bunched, packed Increased Network Performance RDOs move usefulness Minimize Data Transfer Porting of Applications to Rover is generally simple Measurements demonstrate huge change from both methodologies

Slide 40

Topics for Discussion Are there "missing" components? Consider the possibility that the semantics are not that \'solid. Then again, if the vulnerability about information qualities is not acknowledged? Ought to Rover bolster some replication benefit? Do we truly realize what ought to be a "fascinating" portable application ?

Slide 41

Topics for Discussion - II as it were, are the presumptions made sensible ? How secure are these designs ? What about the "versatile" information ? Migrant Computing: Can these plans bolster Nomads ? Other distributed models? E.g. Sensor Networks?

Recommended
View more...