Metadata Space Complexity Problem

For more info about our services contact : help@bestpfe.com

Table of contents

List of Tables
List of Figures
I Preliminaries
1 Introduction
1.1 Contributions
1.1.1 Optimality of Replicated Data Types
1.1.2 Causally-Consistent Object Database for Client-Side Applications
1.2 Organization
1.3 Authorship and Published Results
2 Replicated Data Types
2.1 Motivation
2.2 System Model and Object Implementation
2.2.1 Object Implementation Model
2.2.2 Replication
2.2.3 Examples
2.2.3.1 Counter Implementations
2.2.3.2 Register Implementations
2.3 Specification of Intended Behavior
2.3.1 Specification Model
2.3.2 Examples
2.3.2.1 Counter Specification
2.3.2.2 Register Specifications
2.3.2.3 Set Specifications
2.4 Execution Model and Correctness
2.4.1 Execution Model
2.4.2 Implementation Correctness
2.4.3 Implementation Categories
2.4.3.1 Network Specifications
2.4.3.2 Visibility Witnesses
2.4.3.3 Main Categories
II Optimality of Replicated Data Types
3 Metadata Space Complexity Problem
3.1 Problem Statement
3.2 Optimizing Implementations
3.2.1 Successful Optimizations
3.2.1.1 Add-Wins Set
3.2.1.2 Multi-Value Register
3.2.2 Prior Implementations and Unsuccessful Optimizations
3.2.2.1 Last-Writer-Wins Register
3.2.2.2 Remove-Wins Set
3.2.2.3 Last-Writer-Wins Set
3.2.2.4 Counter
3.3 Summary
4 Lower Bounds on Complexity and Implementation Optimality
4.1 Proof Technique
4.1.1 Experiment Family
4.1.2 Driver Programs
4.2 Lower Bounds
4.2.1 Counter
4.2.2 Add-Wins Set
4.2.3 Remove-Wins Set
4.2.4 Last-Writer-Wins Set
4.2.5 Multi-Value Register
4.2.6 Last-Writer-Wins Register
4.3 Summary
5 Related Work and Discussion
5.1 Other Data Types
5.2 State-Based Optimizations Beyond Our Metric
5.2.1 Background Compaction of Stable Metadata
5.2.2 Finer-Grained Optimizations
5.2.3 Custom Timestamps
5.3 Other Implementation Categories
5.3.1 State-Based Implementations With Smaller Messages
5.3.2 Optimizations Based on Topology Restrictions and Delayed Visibility
5.3.3 Replicated File Systems
5.4 Lower Bound Proofs in Distributed Computing
III Causally-Consistent Object Database for Client-Side Applications
6 Problem Overview
6.1 System Model and Basic Requirements
6.2 Consistency with Convergence
6.2.1 Causal Consistency
6.2.2 Convergence with Replicated Data Types
6.3 Application Programming Interface
6.4 Challenge
6.4.1 Metadata Design
6.4.2 Causal Consistency with Partial Replication is Hard
7 The SwiftCloud Approach
7.1 Design
7.1.1 Causal Consistency at Full Data Center Replicas
7.1.2 Causal Consistency at Partial Client Replicas
7.1.3 Failing Over: The Issue with Transitive Causal Dependency
7.1.3.1 Conservative Read: Possibly Stale, But Safe
7.1.3.2 Discussion
7.2 Implementation
7.2.1 Timestamps, Vectors and Log Merge
7.2.2 Protocols
7.2.2.1 State
7.2.2.2 Client-Side Execution
7.2.2.3 Transfer Protocol: Client to Data Center
7.2.2.4 Geo-replication Protocol: Data Center to Data Center
7.2.2.5 Notification Protocol: Data Center to Client
7.2.3 Object Checkpoints and Log Pruning
7.2.3.1 Log Pruning in the Data Center
7.2.3.2 Pruning the Client’s Log
8 Experimental Evaluation
8.1 Prototype and Applications
8.2 Experimental Setup
8.3 Experimental Results
8.3.1 Response Time and Throughput
8.3.2 Scalability
8.3.3 Tolerating Client Churn
8.3.4 Tolerating Data Center Failures
8.3.5 Staleness Cost
9 Related Work
9.1 Consistency Models for High Availability
9.2 Relevant Systems
9.2.1 Replicated Databases for Client-Side Applications
9.2.1.1 Systems that Support Inter-Object Consistency
9.2.1.2 Systems that Support Intra-Object Consistency Only
9.2.1.3 Session Guarantees
9.2.2 Geo-replicated Databases for Server-Side Applications
9.2.2.1 Approaches
9.2.2.2 Comparison and Applicability to Client-Side Replication
10 Conclusion
10.1 Summary
10.2 Limitations and Perspectives
IV Appendix
A Additional Material on Replicated Data Types
A.1 Formal Network Layer Specifications
A.2 Optimized Op-Based Implementations
B Metadata Overhead Proofs
B.1 Standard Encoding
B.2 Metadata Overhead of Specific Implementations
B.3 Lower Bound Proofs
B.3.1 Add-Wins Set
B.3.2 Remove-Wins Set
B.3.3 Last-Writer-Wins Set
B.3.4 Multi-Value Register
B.3.5 Last-Writer-Wins Register
C Résumé de la thèse
C.1 L’optimalité des types les données répliquées
C.2 Une base de données causalement cohérente pour les applications coté client
C.2.1 Présentation du problème
C.2.1.1 La cohérence et la convergence
C.2.1.2 La conception des métadonnées
C.2.1.3 La cohérence causale avec une réplication partielle est dur
C.2.2 L’approche SwiftCloud
C.2.2.1 Cohèrence causale dans les répliques complètes des Centre de Données
C.2.2.2 Cohèrence causale dans les répliques client partielles
C.2.2.3 Le basculement sur erreur: Le problème avec la dépendance causale transitive
C.2.2.4 Protocoles avec les métadonnées découplées et délimitées .
C.2.3 La mise en oeuvre et l’évaluation
Bibliography