Transcript Reading Consistent and Current Data “Off the Air”

An IEEE ICDE 2000 Tutorial on
Mobile and Wireless Database
Access for Pervasive Computing
Panos K. Chrysanthis
University of Pittsburgh & Carnegie Mellon University
Evaggelia Pitoura
University of Ioannina
[email protected]
7/21/2015 21:56
[email protected]
1
Outline










Motivating Example
Issues: Mobility, Wireless Communication, Portability
Adaptability and Mobile Client-Server Models
Location Management
Broadcast data dissemination
Disconnected database operations
Mobile Access to the Web
Mobility in Workflow Systems
State of Mobile DB Industry and Research Projects
Unsolved Problems
7/21/2015 21:56
2
Party on Friday





7/21/2015 21:56
Update Smart Phone’s calendar with guests
names.
Make a note to order food from Dinner-onWheels.
Update shopping list based on the guests
drinking preferences.
Don’t forget to swipe that last can of beer’s UPS
label.
The shopping list is always up-to-date.
3
Party on Friday

AutoPC detects a near Supermarket that advertises sales.

It accesses the shopping list and your calendar on the Smart Phone.
It informs you the soda and beer are on sale, and reminds you.
that your next appointment is in 1 hour.
There is enough time based on the latest traffic report.


7/21/2015 21:56
4
Party on Friday





TGIF…
Smart Phone reminds you that you need to order food by
noon.
It downloads the Dinner-on-Wheels menu from the Web
on your PC with the guests’ preferences marked.
It sends the shopping list to your
CO-OP’s PC.
Everything will be delivered by the time
you get home in the evening.
7/21/2015 21:56
5
Mobile Applications


Expected to create an entire new class of Applications
 new massive markets in conjunction with the Web
 Mobile Information Appliances - combining personal
computing and consumer electronics
Applications:
 Vertical: vehicle dispatching, tracking, point of sale
 Horizontal: mail enabled applications, filtered
information provision, collaborative computing…
7/21/2015 21:56
6
Mobile and Wireless Computing



Goal: Access Information Anywhere, Anytime,
and in Any Way.
Aliases: Mobile, Nomadic, Wireless, Pervasive,
Invisible, Ubiquitous Computing.
Distinction:
• Fixed wired network: Traditional distributed computing.
• Fixed wireless network: Wireless computing.
• Wireless network: Mobile Computing.

Key Issues: Wireless communication, Mobility, Portability.
7/21/2015 21:56
7
Wireless Communication

Cellular - GSM (Europe+), TDMA & CDMA (US)
– FM: 1.2-9.6 Kbps; Digital: 9.6-14.4 Kbps (ISDN-like services)

Public Packet Radio - Proprietary
– 19.2 Kbps (raw), 9.6 Kbps (effective)


Private and Share Mobile Radio
Wireless LAN - wireless LAN bridge (IEEE 802.11)
– Radio or Infrared frequencies: 1.2 Kbps-15 Mbps

Paging Networks – typically one-way communication
– low receiving power consumption

Satellites – wide-area coverage (GEOS, MEOS, LEOS)
– LEOS: 2.4 Kbps (uplink), 4.8Kbps (downlink)
7/21/2015 21:56
8
Mobile Network Architecture
7/21/2015 21:56
9
Wireless characteristics





Variant Connectivity
 Low bandwidth and reliability
Frequent disconnections
• predictable or sudden
Asymmetric Communication
 Broadcast medium
Monetarily expensive
 Charges per connection or per message/packet
Connectivity is weak, intermittent and expensive
7/21/2015 21:56
11
Portable Information Devices

PDAs, Personal Communicators
 Light, small and durable to be easily carried around
 dumb terminals [InfoPad, ParcTab projects],
palmtops, wristwatch PC/Phone, walkstations

will run on AA+ /Ni-Cd/Li-Ion batteries
may be diskless
I/O devices: Mouse is out, Pen is in
wireless connection to information networks
 either infrared or cellular phone
specialized HW (for compression/encryption)




7/21/2015 21:56
12
Portability Characteristics

Battery power restrictions
 transmit/receive, disk spinning, display, CPUs,
memory consume power
Battery lifetime will see very small increase
 need energy efficient hardware (CPUs, memory) and
system software
 planned disconnections - doze mode

Power consumption vs. resource utilization

7/21/2015 21:56
13
Portability Characteristics

Resource constraints
 Mobile computers are resource poor
 Reduce program size – interpret script languages
(Mobile Java?)
 Computation and communication load cannot be
distributed equally
Small screen sizes

Asymmetry between static and mobile computers

7/21/2015 21:56
14
Mobility Characteristics

Location changes
• location management - cost to locate is added to
communication

Heterogeneity in services
 bandwidth restrictions and variability

Dynamic replication of data
• data and services follow users



Querying data - location-based responses
Security and authentication
System configuration is no longer static
7/21/2015 21:56
15
What Needs to be Reexamined?









Operating systems
File systems
Data-based systems
Communication architecture and protocols
Hardware and architecture
Real-Time, multimedia, QoS
Security
Application requirements and design
PDA design: Interfaces, Languages
7/21/2015 21:56
16
Query/Transaction Processing


Concern moves from CPU time and network delays to battery
power and communication costs (including tariffs)
Updates may take the form of long-running transactions
 nodes may continue in disconnected mode
 need new transaction models [Chrysanthis 93, Satya 94]



Move data vs. move query/transaction
Context (location) based query responses
Consistency, autonomy, recovery
 Approximate answers
 Stable storage for logs, data -- stabilize at servers?



Providing uniform access in a heterogeneous environment
Design of human-computer interfaces (pen-based computing)
Updated system info: Location information, user profiles
7/21/2015 21:56
17
Recurrent Themes






Handling disconnections (planned failures?)
 caching strategies
 managing inconsistencies
Delayed write-back and prefetch: use network idle times
 increases memory requirements
Buffering/batching: allows bulk transfers
Partitioning and replication
 triggered by relocation
Compression: increase effective BW
 increases battery power requirements
Receiving needs less power than sending
7/21/2015 21:56
18
Outline










Motivating Example
Issues: Mobility, Wireless Communication, Portability
Adaptability and Mobile Client-Server Models
Location Management
Broadcast data dissemination
Disconnected database operations
Mobile Access to the Web
Mobility in Workflow Systems
State of Mobile DB Industry and Research Projects
Unsolved Problems
7/21/2015 21:56
20
Mobility in Db Applications
• Need to adapt to constantly changing environment:
• network connectivity
• available resources and services
• By varying and (re)negotiating:
• the partition of duties between the mobile and
static elements
• the quality of data available at the mobile host
Example: Fidelity (degree to which a copy of data matches
the reference copy at the server)
7/21/2015 21:56
21
Adaptability
Where should support for mobility and adaptability be placed?
Application-Aware
Laissez-Faire
Application Transparent
(-) applications must be re-written
which may be very complicated
(+) existing applications continue
to work unchanged
(-) no focal point of control to
resolve potentially incompatible
application demands or to enforce
limits on resource usage
(-) too general, cannot take
advantage application semantics
7/21/2015 21:56
(-) may not be attainable (e.g.,
during a long disconnection)
22
Adaptive Applications

Need:
 Measurement of QoS and communication with
application
– A mechanism to monitor the level and quality of information
and inform applications about changes.
 Programmer Interface for Application-Aware
Adaptation
– Applications must be agile: able to reveive events in an
asynchronous manner and react appropriately
 A central point for managing resources and authorizing
any application-initiated request.
7/21/2015 21:56
23
C-SA-C: Server-side Agent
Wireless Link
Client


Fixed Network
Agent
Server
C-SA-C: The Client/Server-side Agent/Server Model
Splits the interaction between the mobile client and
server: client-agent and agent-server
• different protocols for each part of the interaction
• each part may be executed independently of the other
7/21/2015 21:56
25
Responsibilities of the Agent


Messaging and queying
Manipulate data prior to their transmission to the
client:
 perform data specific compression
 batch together requests
 change the transmission order
7/21/2015 21:56
26
Role of the Agent

Surrogate or proxy of the client
 Any communication to/from the client goes through the agent
 Offload functionality from the client to the agent

Application (service) specific
 provides a mobile-aware layer to specifc services or
applications (e.g., web-browsing or database access)
 handles all requests from mobile clients

Filters
 provide agents that operate on protocols
 E.g., an MPEG-agent or a TCP-agent
7/21/2015 21:56
27
C-CA-S: Client-side Agent
Wireless Link
Fixed Network
Client
Agent
Server
Mobile Host

C-SA-S: The Client/Client-side Agent/Server Model
 caching
 background prefetching and hoarding
 various communication optimizations
7/21/2015 21:56
28
C-I-S: Client & Server Agents
Wireless Link
Fixed Network
Client
Agent
Agent
Mobile Host

C-I-S: Client/Intercept/Server Model
 Caching, prefetching etc
 various communication optimizations at both ends
– E.g., asynchronous queued RPC
 relocate computation between the agents
 Client interoperability
7/21/2015 21:56
29
Server
Mobile Agents


Mobile agents are migrating processes associated with an
itinerary
 dynamic code and state deployment
Implement the agents of the previous architectures as
mobile agents, E.g.,
 server-side agents can relocate during handoff
 client-side agent dynamically move on and off the client
– Relocatable dynamic objects (RDO) [Rover]

Implement the communication using mobile agents:
 clients submit/receive mobile agents to/from the server
 E.g., Compacts [Pro-Motion]
7/21/2015 21:56
30
A Taxonomy
S trategy
U n m od if ied S e rve r
M o dif ie d S erve r
C -I- M S
C -S A -M S
C -C A -M S
O dyssey
C -I- S
P ro-m otion
R over
W ebE xpress
P ro-m otion
O r acle m obile
agents
C -S A -S
W ireless
W eb B row ser
C -C A -S
C oda
A daptability
L a is s e z -Fa ire
7/21/2015 21:56
A p p lic a tio n
M o b ility
A w a re
31
A p p lic a tio n
Tra n s p a re n t
Outline










Motivating Example
Issues: Mobility, Wireless Communication, Portability
Adaptability and Mobile Client-Server Models
Location Management
Broadcast data dissemination
Disconnected database operations
Mobile Access to the Web
Mobility in Workflow Systems
State of Mobile DB Industry and Research Projects
Unsolved Problems
7/21/2015 21:56
32
Locating Moving Objects

Example of moving objects
 mobile devices (cars, cellular phones, palmtops, etc)
 mobile users (locate users independently of the device
they are currently using)
 mobile software (e.g., mobile agents)

How to find their location - Two extremes
 Search everywhere
 Store their current location everywhere
 Searching vs. Informing
7/21/2015 21:56
33
Locating Moving Objects
What (granularity), where (availability) and when
(currency) to store
at all sites
the whole
network
Exact
location
Availability

At selective sites (e.g., at
frequent callers)
nowhere
Never
update
7/21/2015 21:56
34
Always update (at each
movement)
Architectures of Location DBs


Two-tier Schemes (similar to cellular phones)
 Home Location Register (HLR): store the location of
each moving object at a pre-specified location for the
object
 Visitor Location Register (VLR): also store the location
of each moving object mo at a register at the current
region
Hierarchical Schemes
 Maintain multiple registries
7/21/2015 21:56
35
Two-tier Location DBs

Search
 Check the VLR at your current location
 If object not in, contact the object’s HLR

Update
 Update the old and new VLR
 Update the HLR
7/21/2015 21:56
36
Hierarchical Location DBs
Maintain a hierarchy of location registers (databases)
A location database at a higher level contains location information
for all objects below it
7/21/2015 21:56
37
Hierarchical Location DBs
Call
caller
7/21/2015 21:56
38
Hierarchical Location DBs
Move
new location
old location
7/21/2015 21:56
39
Hierarchical vs. Two-tier
(+) No pre-assigned HLR
(+) Support Locality
(-)
Increased number of operations (database
operations and communication messages)
(-)
Increased load and storage requirements at the
higher-levels
7/21/2015 21:56
40
Locating Moving Objects
Partitions
P3
P1
P4
P2
User x
7/21/2015 21:56
P5
User x
41
Locating Moving Objects

Caching
 cache the callee’s location at the caller
(large Call to Mobility Ratio)

Replication
 replicate the location of a moving object at its frequent callers
(large CMR)

Forwarding Pointers
 do not update the VLR and the HLR, leave a forwarding pointer
from the old to the new VLR (small CMR)
 When and how forwarding pointers are purged?

Concurrency, coherency and recovery/checkpointing of location DBs
7/21/2015 21:56
42
Querying Moving Objects
• Besides locating moving objects, answer more
advanced queries, e.g.,
• find the nearest service
• send a message to all mobile objects in a specific
geographical reafion
• Location queries: spatial, temporal or continuous
•Issues: representation, evaluation and imprecision
Most current research assumes a centralized location
database
7/21/2015 21:56
43
Querying Moving Objects
How to model the location of moving objects?
Dynamic attribute (its value change with time without an
explicit update) [e.g., in MOST]
For example, dynamic attribute A with three sub-attributes:
A.value, A.updatetime and A.function
(function of a single variable t that has value 0 at time t=0)
• The value of A at A.updatetime is A.value
• at time A.updatetime + t0 is A.value + A.function(t0)
7/21/2015 21:56
44
Querying Moving Objects
How to represent and index moving objects?
 Spatial indexes do not work well with dynamically
changing values
 Value-time representation
• An object is mapped to a trajectory [Kollios 99]
7/21/2015 21:56
45
Outline










Motivating Example
Issues: Mobility, Wireless Communication, Portability
Adaptability and Mobile Client-Server Models
Location Management
Broadcast data dissemination
Disconnected database operations
Mobile Access to the Web
Mobility in Workflow Systems
State of Mobile DB Industry and Research Projects
Unsolved Problems
7/21/2015 21:56
46
Information Dissemination
Goal : Maximize query capacity of servers,
minimize energy per query at the client.
Focus: Read-only transactions (queries).
– Clients send update data to server
– Server resolves update conflicts, commits updates
1. Pull: PDAs demand, servers respond.


7/21/2015 21:56
backchannel (uplink) is used to request data and provide
feedback.
poor match for asymmetric communication.
47
Information Dissemination…
2. Push: Network servers broadcast data, PDA's listen.
 PDA energy saved by needing receive mode only.
 scales to any number of clients.
 data are selected based on profiles and registration in each
cell.
F
G
A
C
B
..
Server
7/21/2015 21:56
E
48
D
Clients
Information Dissemination…
F
G
A
B
E
C
..
Server
D
Clients
14.4 Kbps
3. Combinations Push and Pull (Sharing the channel).


Selective Broadcast: Servers broadcast "hot" information only.
 "publication group" and "on-demand" group.
On-demand Broadcast: Servers choose the next item based on
requests.
 FCFS or page with maximum # of pending requests.
7/21/2015 21:56
49
Broadcast Data Dissemination





business data, e.g., Vitria, Tibco
election coverage data
stock related data
traffic information
sportscasts, e.g., Praja
 Datatacycle [Herman]
 Broadcast disks
7/21/2015 21:56
50
Data Server
Organization of Broadcast data

Flat: broadcast the union of the requested data cyclic.
A B C

Skewed (Random):
 broadcast different items with different frequencies.
 goal is that the inter-arrival time between two
instances of the same item matches the clients'
needs.
A A B C
7/21/2015 21:56
51
Broadcast Disks

Multi-Disks Organization [Acharya et. al, SIGMOD95]
 The frequency of broadcasting each item
depends on its access probability.
 Data broadcast with the same frequency are
viewed as belonging to the same disk.
 Multiple disks of different sizes and speeds are
superimposed on the broadcast medium.
 No variant in the inter-arrival time of each item.
Disk1
Disk2
7/21/2015 21:56
A
B
A B A C
C
52
Selective Tuning





Basic broadcast access is sequential
Want to minimize client's access time and tuning time.
 active mode power is 250mW, in doze mode 50μW
What about using database access methods?
Hashing: broadcast hashing parameters h(K)
Indexing: index needs to be broadcast too
 "self-addressable cache on the air"
(+) "listening/tuning time" decreases
(-) "access time" increases
7/21/2015 21:56
53
Access Protocols

Two important factors affect access time:
1. Size of the broadcast
2. Directory miss factor - you tune in before your
data but after your directory to the data!
Trade-Off:  Size means  Miss factor
Trade-Off:  Size means  Miss factor
7/21/2015 21:56
54
Indexing

(1,M) Indexing:
 We broadcast the index M times during one version of the data.
 All buckets have the offset to the beginning of the next index
segment.

Distributed Indexing
 Cuts down on the replication of index material
 Divides the index into:
– replicated top L levels, non-replicated bottom 4-L levels

Flexible Indexing
 Broadcast divided into p data segments with sorted data.
 A binary control index is used to determine the data segment
 A local index to locate the specific item within the segment
7/21/2015 21:56
55
Caching in Broadcasting






Data are cache to improve access time
Lessen the dependency on the server's choice of broadcast priority
Traditionally, clients cache their "hottest" data to improve hit ratio
Cache data based on PIX:
Probability of access (P)/Broadcast frequency (X).
Cost-based data replacement is not practical:
 requires perfect knowledge of access probabilities
 comparison of PIX values with all resident pages
Alternative: LIX, LRU with broadcast frequency
 pages are placed on lists based on their frequency (X)
 lists are ordered based on L, the running avg. of interaccess times
 page with lowest LIX = L/X is replaced
7/21/2015 21:56
56
Prefetching in Broadcasting





Client prefetch page in anticipation of future accesses
No additional load to the server and network
Prefetching instead of waiting for page miss can reduce the cost of a
miss
PT prefetching heuristic [Archarya et al. 96]
- pt: Access Probability (P) * period (T) before page appears next
- A broadcast page b replaces the cached page c with lowest pt
value
Team tag - Teletext approach [Ammar 87]
 Each page is associated with a set of pages most likely to be
requested next
 When p is requested, D (D:cache size) associated pages are
prefetched
 Prefetching stops when client submit a new request
7/21/2015 21:56
57
Cache Invalidation Techniques

When?
 Synchronous: send invalidation reports periodically
 Asynchronous: send invalidation information for an item as
soon as its value changes; E.g., Bit Sequences [Jing 95]

To whom?
 Stateful server: to affected clients
 Stateless server: broadcast to everyone

What?
 invalidation: only which items were updated
 propagation: the values of updated items are sent
 aggregated information/ materialized views
7/21/2015 21:56
58
Synchronous Invalidation



Stateless servers are assumed.
Types of client: Workalcholic and sleepers [Barbara Sigmod 94]
Strategies:
 Amnestic Terminals: broadcast only the identifiers of the items
that changed since the last invalidation report
abort T, if x є RS(T) appears in the invalidation report
 Timestamp Strategy: broadcast the timestamps of the latest
updates for items that have occurred in the last w seconds.
abort T, if ts(x) > tso(T)
 Signature Strategy: broadcast signatures.
A signature is a compressed checksum similar to the one used
for file comparison.
7/21/2015 21:56
59
Consistency and Currency





Only committed data are included in the broadcast
Does a client read current and consistent data?
Currency interval is the fraction of bcycle that
updates are reflected
Span(T) is the # of currency intervals from which T
read data
if Span(T) = 1, the T is correct (read consistent data)
else ?
... several consistency models
7/21/2015 21:56
60
Consistency Criteria




Latest value: clients read the most recent value of a data
item [Garcia-Molina TODS82, Acharya VLDB96]
Serializability: Certification reports [Barbara ICDCS97]
Update consistency: clients commit of their reads are not
invalidated – read mutually consistent data
 F-Matrix method [Shanmugasundaram SIGMOD99]
2-level serializability: Each client is serializable with
respect to the server
 SGT method [Pitoura&Chrysanthis ICDS99]
 Multiversion [Pitoura&Chrysanthis VLDB99]
7/21/2015 21:56
61
Currency in Multiversion Schemes
Versioning
Multiversioning
Multiversioning
with invalidation
begin (first read)
first invalidation
Invalidation
commit
T’s lifetime
10
7/21/2015 21:56
VLDB 1999
62
Adaptive Hybrid Broadcast


Cycle-based, bidirectional hybrid broadcast server
Issues:
 Dynamic computation of bandwidth
allocated to each broadcast mode
 Dynamic classification of data items
(periodic vs. on-demand)
 Scheduling periodic and on-demand
broadcasts
7/21/2015 21:56
63
An Approach

After each broadcast cycle, items classified as
periodic or on-demand, depending on bandwidth
savings expected

Periodic broadcast occupies up to BWThreshold
Periodic broadcast program is computed to satisfy all
deadlines of periodic data
On-demand broadcast uses on-line EDF
(Earliest Deadline First) algorithm + batching


7/21/2015 21:56
64
Outline










Motivating Example
Issues: Mobility, Wireless Communication, Portability
Adaptability and Mobile Client-Server Models
Location Management
Broadcast data dissemination
Disconnected database operations
Mobile Access to the Web
Mobility in Workflow Systems
State of Mobile DB Industry and Research Projects
Unsolved Problems
7/21/2015 21:56
65
Disconnected Operations

Issues:
 Cache misses are more expensive in mobile environments.
 Data availability for disconnected operation
 Data consistency given that global communication is costly
 Autonomy vs. Consistency

Solutions:
 Caching
 Prefetching
 Hoarding
 Eventual consistency
– Assumption: simultaneous sharing other than read is rare.
 Update conflict detection/resolution
7/21/2015 21:56
67
Caching


What to cache?
 Entire files, directories, tables, objects
 Portions of files, directories, tables, objects
When to cache? Is simple LRU sufficient?
 LRU captures an aspect of temporal locality
 Predictive/semantic caching: based on the
semantics distance between data/request
E.g., clustering of queries [Ren 99]
7/21/2015 21:56
68
Prefetching




Online strategy to improve performance
 prepaging
 prefetching of file
 prefetching of database objects
What to fetch?
 access tree (semantic structure)
 probabilistic modeling of user behavior
Old idea that can be used during network idle times
Combine delayed writeback and prefetch
7/21/2015 21:56
69
Hoarding


Planned and Accidental disconnections are not considered
failures.
New idea - Hoarding:
a technique to reduce the cost of cache misses during
disconnection.
That is, load before disconnect and be ready.

How to do hoarding?
 user-provided information (client-initiated disconnection)
– explicitly specify which data
– Implicitly based on the specified application
 access structured-based (use past history)
E.g., tree-based in file systems, access paths (joins) in DBs
7/21/2015 21:56
70
Hoarding in DB Systems


Granularity of Hoarding
 RDBMS: ranges from tables, set of tables, whole relations
 OO & OR DBMS: objects, set of objects or class
Hoard by issuing queries or materialized views
 User may explicit issue hoarding queries
E.g., Create View with Update-On clause [Lauzac 98]
OO query to describe hoarding profiles [Gruber 94]
 History of past references both queries and data objects
 Hoard Keys - an extended database organization [Badrinath 98]
– hoard keys are used to partition a relation in disjoint logical
horizontal fragments
7/21/2015 21:56
71
Processing the Log




What information to keep in the log for effective reintegration and
log optimization?
 Data values, timestamps, operations
Goal: Keep the log size small to
 Save memory
 Reduce cost for update propagation and reintegration
When to optimize the log
 Incrementally each time a new operation is added
 Before propagation or integration
Optimizations are system specific
 E.g., keep last write record, drop records of inverted operations
7/21/2015 21:56
72
Cache Coherence/Data Consistency



"Lazy" or weak consistency promises high availability
 Consider some conflicts (e.g., write-write conflicts)
 Read-any/Write-any
Other schemes are costly:
 Pessimistic replication schemes/Quorum schemes
 Server-initiated callbacks for cache invalidation
(e.g., Leases).
 Optimistic replication schemes
System support for
 detection of conflicts: version vector, timestamps
 automatic resolution or manual resolution (tools)
7/21/2015 21:56
73
Techniques to Increase Autonomy



Mobile Database Consistency
 When a mobile database M shares a data item with another
database D, it is involved in a global integrity constraint C.
 Transactions on both M and D may suffer unbounded and
unpredictable delays - No local commitment.
What about localizing the constraints – no global constraints?
Localization:
reformulates C so that M accepts a local constraint C’ instead
 Local transactions remain local.
 When C’ is violated at a node, it requests the others for
re-localization, i.e., a dynamic readjustment of C’.
– No need for a distributed transaction.
– No inconsistency from concurrent requests
7/21/2015 21:56
74
Localization of Constraints

Simple Example:
 Let x and y be two data items at two nodes.
 C = J.x + K.y > D is a global constraint.
 Localization yields two local constraints:
 x > L1 and y > L2
 where L1 and L2 are constants chosen such
that J.L1 + K.L2 > D
 Re-localization: L1, L2 can be changed: node y
increases L2 before node x decreases L1
7/21/2015 21:56
75
Localization Methods



Escrowing: Logically partitions aggregated items
 Escrow transactions [O’Neil 86]
 Demarkation protocol [Barbara 91]
Geormetric Method [Mazumdar 99]: Enhanced Escrowing
 It tackles quadratic inequalities
Fragmentation [Walborn 95]: Physically partitions item with
constraints localized within the individual fragments
 Fragmentable objects: fragments are merged to the
originating position
 Reorderable Objects: fragments can be re-organized during
the merging
7/21/2015 21:56
76
Two-tier Transaction Models

Tentatively Committed Transactions





Transactions tentatively commit on a mobile unit
Make their results locally visible leading to abort dependencies
Certification based on application or system defined criteria
invalidated trans. are aborted, reconcile, or compensated
Isolation-Only Transactions [Lu 94]
 First-class transactions for connected operations
– immediately commit at the server, globally serializable
 Second-class transactions for disconnected operations
– tentatively commit, locally serializable, no failure atomicity
– validation criteria: global serializability, global certifiability
– invalidated trans. are aborted, reexecuted, or compensated.
7/21/2015 21:56
77
Two-tier transaction Models

Two-tier Replication [Gray 95]
 Base transactions and Tentative transactions (disconnected)
 Upon reconnection, tentative transactions are reprocessed
as base transactions on master data version
 Application semantics are used to increase concurrency and
acceptance (e.g., commutative operations)

(Mobile) Escrow Transactions
 Transactions are validated locally by localizing constraints
 Local commitment ensures global commitment
7/21/2015 21:56
78
Mobile Transactions

Distributed transactions involving both mobile and fixed hosts.
Traditional approaches are too restrictive.

Mobile Open Nested Transactions [Chrysanthis 93]

Goals: sharing of partial results while in execution,
maintaining computation state on a fixed host,
moving transactions on/off a mobile host and across fixed hosts.
 Components: Atomic transactions, Compensatable transaction,
Reporting transactions and Co-transactions.
 Properties: Component isolation, semantic atomicity
Components may commit/abort independently
7/21/2015 21:56
79
Mobile Transactions

Kangaroo Transactions [Dunham 97]
 Transaction relocation is achieved by splitting the transaction
during hand-off. One Joey transaction per cell.

The Clustering Model [Pitoura 95]
 A distributed database is divided into weak and strict clusters
 Data in a cluster are mutually consistent
 Inconsistency between clusters is bounded and resolved by
merging them either
– during transaction commitments, or
– when connectivity improves
 A mobile transaction is decomposed into Strict and Weak
transactions based on consistency requirements
 Only strict transactions ensure durability and currency of reads
7/21/2015 21:56
80
Failure Recovery




Emphasis has been on recording global checkpoints
 Periodically store the state of a distributed application with
mobile components.
DB Failure Recovery: Logging and checkpointing
Failures can be soft or hard
 Soft failure can be recovered from the locally stored log and
checkpoint
 Hard failure require hard checkpoints stored in the fixed
network.
Issues:
 When to propagate the log and create a hard checkpoint?
 Where to store hard checkpoints to speed up recovery and
reduce its cost?
7/21/2015 21:56
81
Database Interface


Desirable features:
 Semantic simplicity: formulation of queries without
special knowledge
 Interaction with a pointing device
 Disconnected query specification
QBI (Query By Icons) [Massari-Chrysanthis 95]
 Iconic language requiring minimum typing
 Semantic data model that hides details
 Metaquery tools for query formulation during
disconnections
7/21/2015 21:56
82
Outline










Motivating Example
Issues: Mobility, Wireless Communication, Portability
Adaptability and Mobile Client-Server Models
Location Management
Broadcast data dissemination
Disconnected database operations
Mobile Access to the Web
Mobility in Workflow Systems
State of Mobile DB Industry and Research Projects
Unsolved Problems
7/21/2015 21:56
83
Mobile Access to the Web



Three-tier Architectures: Client - Web Server - Data Server
Web Server can act like a server-side agent
 Prefetching at its cache can hide some latency
 Scripts at the Web server can perform user-specified
filtering and processing.
Most solutions use a Web proxy to avoid any changes to the
browsers and servers.
 Pythia [Fox96]
 Mobile Browser (MOWSER) [Joshi 96]
– Distillation: highly lossy, real-time,datatype specific
compression that preserves semantic content
 WebExpress [Housel 97]
7/21/2015 21:56
84
WebExpress




Utilizes the C-I-S Model
Goals: reduce traffic volume and reduce latency
Intercept any http request and perform four optimizations:
 Caching at both CSA & SSA of graphics and html
objects
 Differencing: only changes are communicated
 Long-live TCP/IP Connection: CSA & SSA use a single
TCP connection
 Header reduction: SSA includes the required browser
capabilities. They are not sent by the CSA.
While disconnected (off-line mode) uses CSA cache
7/21/2015 21:56
85
Advances in Mobile Web Servers

W4 for Wireless WWW [bartlett 94]: Mosaic on PDA

Dynamic Documents: Tcl scripts that execute within
the mobile browser to customize the html documents

Dynamic URLs [Mobisaic 94]: They support mobile
web servers and work with active pages.

IPiC [Shrinivasan 99]: A match head sized web server
7/21/2015 21:56
86
Mobility in Workflows

Workflows are automated business processes.
 involve coordinated execution of multiple longrunning tasks or activities

Workflow system coordinates the workflow
execution.

Processing entities (clients) are where the activities
are executed and can be mobile.
• disconnections among procesing entities (clients)
7/21/2015 21:56
87
Workflow Disconnected Operations
A pessimistic approach: Exotica

Prior to disconnection, each client:
 reserves the activities it plans to work by locking
 hoards the relative to the activities data (requests from the
server the input containers of the activities)

During disconnection,
 stores results in its local stable memory

Upon reconnection,
 the results are reported back to the server
7/21/2015 21:56
88
Mobile Agents in Workflows

A Mobile Agent Workflow Model: INCAS

No centralized workflow server

Each workflow process is model as a mobile agent called
Information Carrier (INCA). Each INCA
 encapsulates the private data of the workflow
 carries a set of rules that control the flow between the
activities of the INCA computation
 maintains the history (log) of its execution

Each INCA is initially submitted to a procesisng entity (client)
and roams among processing entities to achieve its goal
7/21/2015 21:56
89
Outline










Motivating Example
Issues: Mobility, Wireless Communication, Portability
Adaptability and Mobile Client-Server Models
Location Management
Broadcast data dissemination
Disconnected database operations
Mobile Access to the Web
Mobility in Workflow Systems
State of Mobile DB Industry and Research Projects
Unsolved Problems
7/21/2015 21:56
90
Mobility Middleware in the Market





Most middleware market are based on TCP/IP and socketoriented connections
Wireless-friendly TCP versions have been proposed but no
major products adopted it
Microsoft’s Remote Access supports cellular communication by
integrating Shiva’s PPP suite
Shiva’s PPP (Point-to-Point protocol) suit provide a remote
access client to either wired or mobile servers
 E.g., mobile clients can access Tuxedo transaction services
MobileWare Office Server: An agent-based middleware that
supports Lotus Notes, Web access, database replication, etc.
 Connection profiles, checkpointing,compression, security
7/21/2015 21:56
91
State of Mobile DB Industry

Sybase SQL Remote (Sybase SQL AnyWhere)
 MobiLink: Centralized model to control replication
 Application-specific bi-directional synchronization using scripts
 UltraLite: in-memory dbms (50KB)

ORACLE
 Oracle Mobile Agents middleware
 Oracle 8 Lite: supports bi-directional replication between a client
and a server (50-750KB)
 Oracle Replication Manager: supports replication across
multiple servers based on the peer-to-peer model

MS SQLServer
 Merge replication and conflict resolution
 Alternative clients: Outlook and MS ACCESS

IBM DB2 Everywhere (100KB)
7/21/2015 21:56
92
Case Study: Coda





Client-Server System with two classes of replication w.r.t.
consistency
Disconnected vs. Weakly connected
 Hoarding, Caching/Server callback, No Prefetching
During connections: Allows AFS clients (Venus) to hoard files.
 hierarchical, prioritized cache management  equilibrium.
 track dependencies, bookmarks
During disconnections: Venus acts as (emulates) a server
 generates (temp) fids, services request to hoarded files.
On reconnection, Venus integrates locally changed files to servers.
 Considers only write-write conflicts - no notion of atomicity
 User conflict resolution/ Application-aware adaptation [Odyssey]
 Use optimistic replication technique
7/21/2015 21:56
93
Case Study: Consistency in Bayou



A bottom-up approach to specific design problems
 more distributed than coda, more emphasis on "small"
clients
Key features:
 read-any/write-any to enhance availability
 anti-entropy protocol for eventual consistency
 dependency checks on each write
– dependency set
– If queries (run at server) do return the expected results
– Application-specific resolution of update conflicts
 Primary server to commit writes and set order
 Session consistency guarantees
How effective is anti-entropy?
7/21/2015 21:56
95
Anti-entropy Protocol




Server propagates write among copies.
Eventual all copies "converge" towards the same state.
Eventual reach identical state if no new updates.
Pair-to-peer anti-entropy
 each server periodically selects another server
 exchange writes and agree on the performed order
 reach identical state after performing the same writes
in the same order.
7/21/2015 21:56
96
Case Study: Rover







Rover [Joseph 97] provides an environment for the development
of mobile applications
Applications are split into client and server part communicating
with Queued RPCs
Application code and data are encapsulated within Relocatable
Dynamic Objects (RDOs)
Access Managers at client and server handle RDOs
Client’s operational log is lazily transfer to the server
Disconnections are supported by the local cache
Some support for primary copy, optimistic consistency
7/21/2015 21:56
97
Case Study: Pro-Motion




Pro-Motion [Chrysanthis 97] is designed for the development of
mobile database applications.
It shares similar architecture as Rover with a multi-tier C-I-S model.
Compact is the unit of caching and hoarding
 It encapsulates cached data, methods, consistency rules and
obligations (e.g., deadlines).
Supports both tentatively committed transactions
and two-tier replication.
7/21/2015 21:56
98
Case Study: Rome





Rome [Fox 99] goals is the timely and in context delivery of
information
Information should be received when and where it is needed
Its fundamental building block are the triggers:
 pieces of data bundled with contextual information
 Condition: (location  R)  (time  t)  action
It is similar to active databases but with decentralized
management
It provides an extensible framework and building blocks
leveraging on internet service.
7/21/2015 21:56
99
Unsolved Problems






Integration and evaluation of algorithms with applications
Broadcast disks
 Information update/consistency and data temporal
coherence - meet time constraints of requests
 Relation between server broadcasting and client caching.
Multiple broadcast channels and multiple database access
Efficient, scalable, adaptive mechanisms
 Location handling
 Trigger management
Programmer Interface for Application-aware adaptation
 Data fidelity vs. consistency
 Semantic consistency needs metadata/requirements
Multimedia and QoS
7/21/2015 21:56
100
To Recap
Mobile and wireless computing attempts to
deliver today’s and tomorrow’s applications
on yesterday’s hardware and communication
infrastructure!
7/21/2015 21:56
101