Replicated Data Management for Mobile Computing (Synthesis Lectures on Mobile and Pervasive Computing)

Managing data in a mobile computing environment invariably involves caching or replication. In many cases, a mobile device has access only to data that is stored locally, and much of that data arrives via replication from other devices, PCs, and services. Given portable devices with limited resources, weak or intermittent connectivity, and security vulnerabilities, data replication serves to increase availability, reduce communication costs, foster sharing, and enhance survivability of critical information. Mobile systems have employed a variety of distributed architectures from client–server caching to peer-to-peer replication. Such systems generally provide weak consistency models in which read and update operations can be performed at any replica without coordination with other devices. The design of a replication protocol then centers on issues of how to record, propagate, order, and filter updates. Some protocols utilize operation logs, whereas others replicate state. Systems might provide best-effort delivery, using gossip protocols or multicast, or guarantee eventual consistency for arbitrary communication patterns, using recently developed pairwise, knowledge-driven protocols. Additionally, systems must detect and resolve the conflicts that arise from concurrent updates using techniques ranging from version vectors to read–write dependency checks. This lecture explores the choices faced in designing a replication protocol, with particular emphasis on meeting the needs of mobile applications. It presents the inherent trade-offs and implicit assumptions in alternative designs. The discussion is grounded by including case studies of research and commercial systems including Coda, Ficus, Bayou, Sybase’s iAnywhere, and Microsoft’s Sync Framework. Table of Contents: Introduction / System Models / Data Consistency / Replicated Data Protocols / Partial Replication / Conflict Management / Case Studies / Conclusions / Bibliography Replicated Data Management for Mobile Computing Synthesis Lectures on Mobile and Pervasive Computing Abstract Keywords Contents List of Figures Chapter 1 Introduction Introduction 1.1 HISTORICAL PERSPECTIVE 1.2 LECTURE ORGANIZATION 1.1 HISTORICAL PERSPECTIVE Chapter 2 System Models System Models 2.1 BASIC COMPONENTS AND TERMINOLOGY 2.2 REMOTE DATA ACCESS 2.3 DEVICE-MASTER REPLICATION 2.4 PEER-TO-PEER REPLICATION 2.5 PUBLISH-SUBSCRIBE SYSTEMS 2.6 RELATED TECHNOLOGIES AND MODELS 2.6.1 Ad Hoc Wireless Sensors Networks 2.6.2 Delay-Tolerant Networking 2.6.3 Infostations 2.7 REPLICATION REQUIREMENTS System Models Chapter 3 Data Consistency Data Consistency 3.1 BEST EFFORT CONSISTENCY 3.2 EVENTUAL CONSISTENCY 3.3 CAUSAL CONSISTENCY 3.4 SESSION CONSISTENCY 3.5 BOUNDED INCONSISTENCY 3.6 HYBRID CONSISTENCY Chapter 4 Replicated Data Protocols Replicated Data Protocols 4.1 REPRESENTING UPDATES 4.1.1 Operation-Sending Protocols 4.1.2 Item-Sending Protocols 4.1.3 Comparisons 4.2 RECORDING UPDATES 4.2.1 Log-Based Systems 4.2.2 State-Based Systems 4.2.3 Comparisons 4.3 SENDING UPDATES 4.3.1 Direct Broadcast 4.3.2 Full Replica or Log Exchange 4.3.3 Gossip Protocols 4.3.4 Message Queue Protocols 4.3.5 Modified Bit Protocol 4.3.6 Device-Master Timestamp Protocols 4.3.7 Device-Master Log-Based Protocol 4.3.8 Anti-Entropy Protocols 4.3.9 Anti-entropy With Checksums 4.3.10 Knowledge-Driven Log-Based Protocols 4.3.11 Knowledge-Driven State-Based Protocols 4.4 ORDERING UPDATES 4.4.1 Ordered Delivery 4.4.2 Sequencers 4.4.3 Update Timestamps 4.4.4 Update Counters 4.4.5 Version Vectors 4.4.6 Operation Transformation 4.4.7 Other Ordering Issues Chapter 5 Partial Replication Partial Replication 5.1 ACCESS-BASED CACHING 5.2 POLICY-BASED HOARDING 5.3 TOPIC-BASED CHANNELS 5.4 HIERARCHICAL SUBCOLLECTIONS 5.5 CONTENT-BASED FILTERS 5.6 CONTEXT-BASED FILTERS Chapter 6 Conflict Management Conflict Management 6.1 WHAT IS A CONFLICT? 6.2 CONFLICT DETECTION 6.2.1 No Conflict Detection 6.2.2 Version Histories 6.2.3 Previous Versions 6.2.4 Version Vectors 6.2.5 Made-With Knowledge 6.2.6 Read-Sets 6.2.7 Operation Conflict Tables 6.2.8 Integrity Constraints 6.2.9 Dependency Checks 6.3 CONFLICT RESOLUTION 6.3.1 How Are Conflicts Resolved? 6.3.2 Where Are Conflicts Resolved? Chapter 7 Case Studies Case Studies 7.1 CODA 7.1.1 History and Background 7.1.2 Target Applications 7.1.3 System Model 7.1.4 Consistency 7.1.5 Replication Mechanisms 7.1.6 Conflict Handling 7.2 FICUS 7.2.1 History and Background 7.2.2 Target Applications 7.2.3 System Model 7.2.4 Consistency 7.2.5 Replication Mechanisms 7.2.6 Conflict Handling 7.3 BAYOU 7.3.1 History and Background 7.3.2 Target Applications 7.3.3 System Model 7.3.4 Consistency 7.3.5 Replication Mechanisms 7.3.6 Conflict Handling 7.4 SYBASE iANYWHERE 7.4.1 History and Background 7.4.2 Target Applications 7.4.3 System Model 7.4.4 Consistency 7.4.5 Replication Mechanisms 7.4.6 Conflict Handling 7.5 MICROSOFT SYNC FRAMEWORK 7.5.1 History and Background 7.5.2 Target Applications 7.5.3 System Model 7.5.4 Consistency 7.5.5 Replication Mechanisms 7.5.6 Conflict Handling Chapter 8 Conclusion Conclusions Bibliography Author Biography