vii
1. Introduction .......................................................................................................1
1.1 Historical Perspective .......................................................................................... 3
1.2 Lecture Organization ..........................................................................................
5
2. System Models ....................................................................................................7
2.1 Basic Components and Terminology ................................................................... 7
2.2 Remote Data Access ............................................................................................
9
2.3 Device–Master Replication ...............................................................................
10
2.4 Peer-to-Peer Replication ...................................................................................
13
2.5 Publish–Subscribe Systems
................................................................................ 15
2.6 Related Technologies and Models .....................................................................
16
2.6.1 Ad Hoc Wireless Sensors Networks ......................................................
16
2.6.2 Delay-Tolerant Networking ..................................................................
17
2.6.3 Infostations ............................................................................................
18
2.7 Replication Requirements .................................................................................
19
3. Data Consistency .............................................................................................. 23
3.1 Best Effort Consistency ..................................................................................... 23
3.2 Eventual Consistency ........................................................................................
24
3.3 Causal Consistency ............................................................................................
25
3.4 Session Consistency ...........................................................................................
25
3.5 Bounded Inconsistency ......................................................................................
26
3.6 Hybrid Consistency ...........................................................................................
26
4. Replicated Data Protocols ................................................................................. 27
4.1 Representing Updates ........................................................................................ 27
4.1.1 Operation-Sending Protocols ................................................................
28
Contents
viii REPLICATED DATA MANAGEMENT FOR MOBILE COMPUTING
4.1.2 Item-Sending Protocols ......................................................................... 28
4.1.3 Comparisons ..........................................................................................
28
4.2 Recording Updates ............................................................................................
29
4.2.1 Log-Based Systems ...............................................................................
29
4.2.2 State-Based Systems ..............................................................................
30
4.2.3 Comparisons ..........................................................................................
31
4.3 Sending Updates ................................................................................................
33
4.3.1 Direct Broadcast ....................................................................................
33
4.3.2 Full Replica or Log Exchange ...............................................................
33
4.3.3 Gossip Protocols ....................................................................................
34
4.3.4 Message Queue Protocols ......................................................................
35
4.3.5 Modified Bit Protocol ............................................................................
36
4.3.6 Device–Master Timestamp Protocols ....................................................
37
4.3.7 Device–Master Log-Based Protocol ......................................................
37
4.3.8 Anti-Entropy Protocols .........................................................................
38
4.3.9 Anti-Entropy With Checksums ............................................................
39
4.3.10 Knowledge-Driven Log-Based Protocols ..............................................
40
4.3.11 Knowledge-Driven State-Based Protocols ............................................
42
4.4 Ordering Updates ..............................................................................................
44
4.4.1 Ordered Delivery ...................................................................................
44
4.4.2 Sequencers .............................................................................................
44
4.4.3 Update Timestamps ...............................................................................
45
4.4.4 Update Counters ...................................................................................
45
4.4.5 Version Vectors ......................................................................................
46
4.4.6 Operation Transformation .....................................................................
46
4.4.7 Other Ordering Issues ...........................................................................
47
5. Partial Replication ............................................................................................ 49
5.1 Access-Based Caching ....................................................................................... 49
5.2 Policy-Based Hoarding ......................................................................................
51
5.3 Topic-Based Channels .......................................................................................
51
5.4 Hierarchical Subcollections ...............................................................................
52
5.5 Content-Based Filters .......................................................................................
53
5.6 Context-Based Filters ........................................................................................
55
6. Conflict Management ........................................................................................ 57
6.1 What Is a Conflict? ........................................................................................... 57
CONTENTS ix
6.2 Conflict Detection ...............................................................................................58
6.2.1 No Conflict Detection ...........................................................................
58
6.2.2 Version Histories ...................................................................................
59
6.2.3 Previous Versions ...................................................................................
59
6.2.4 Version Vectors ......................................................................................
60
6.2.5 Made-With Knowledge ........................................................................
61
6.2.6 Read-Sets ..............................................................................................
61
6.2.7 Operation Conflict Tables .....................................................................
62
6.2.8 Integrity Constraints .............................................................................
62
6.2.9 Dependency Checks ..............................................................................
63
6.3 Conflict Resolution
............................................................................................ 63
6.3.1 How Are Conflicts Resolved? ................................................................
64
6.3.2 Where Are Conflicts Resolved? .............................................................
65
7. Case Studies ..................................................................................................... 69
7.1 Coda .................................................................................................................. 69
7.1.1 History and Background .......................................................................
69
7.1.2 Target Applications ...............................................................................
69
7.1.3 System Model ........................................................................................
69
7.1.4 Consistency ...........................................................................................
71
7.1.5 Replication Mechanisms .......................................................................
71
7.1.6 Conflict Handling .................................................................................
72
7.2 Ficus ..................................................................................................................
72
7.2.1 History and Background .......................................................................
72
7.2.2 Target Applications ...............................................................................
73
7.2.3 System Model ........................................................................................
73
7.2.4 Consistency ...........................................................................................
73
7.2.5 Replication Mechanisms .......................................................................
73
7.2.6 Conflict Handling .................................................................................
74
7.3 Bayou .................................................................................................................
75
7.3.1 History and Background .......................................................................
75
7.3.2 Target Applications ...............................................................................
75
7.3.3 System Model ........................................................................................
75
7.3.4 Consistency ...........................................................................................
75
7.3.5 Replication Mechanisms .......................................................................
75
7.3.6 Conflict Handling .................................................................................
76
x REPLICATED DATA MANAGEMENT FOR MOBILE COMPUTING
7.4 Sybase iAnywhere .............................................................................................. 76
7.4.1 History and Background .......................................................................
76
7.4.2 Target Applications ...............................................................................
77
7.4.3 System Model ........................................................................................
77
7.4.4 Consistency ...........................................................................................
77
7.4.5 Replication Mechanisms .......................................................................
77
7.4.6 Conflict Handling .................................................................................
78
7.5 Microsoft Sync Framework ...............................................................................
78
7.5.1 History and Background .......................................................................
78
7.5.2 Target Applications ...............................................................................
79
7.5.3 System Model ........................................................................................
79
7.5.4 Consistency ...........................................................................................
79
7.5.5 Replication Mechanisms .......................................................................
79
7.5.6 Conflict Handling .................................................................................
80
8. Conclusions ...................................................................................................... 81
Bibliography .............................................................................................................. 83
Author Biography ...................................................................................................... 93

Get Replicated Data Management for Mobile Computing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.