Specialeforsvar af Michael Budde

Onsdag den 25. november kl. 14.00 forsvarer Michael Budde sit speciale i datalogi.

Title

Synchronization of Mobile Database Systems using Operational Transformation

Abstract

The use of mobile devices is becoming increasingly widespread and it is common for people to have more than one device. Users want their data to be available on all their devices and at the same time the data should be avilable even when the user does not have internet connection.

Commonly used storage systems on mobile devices such as SQLite and CoreData does not provide any synchronization mechanisms and it is up the the application developer to implement such features.

The main contributions of this thesis is a synchronization algorithm for a replicated data store, aimed for use in a mobile environment, that supports offline modification of data and both automatic and application-defined resolution of conflicts, and prototype implementation of the algorithm showing that the approach is viable.

The theory of operational transformation is introduced and some of the existing algorithms based on the operational transformation method are examined. We present the design of a synchorization algorithm that is based on operational transformation and discuss the tradeoffs made. The algorithm assumes a client-server architecture, where each client has a replica of the database, which is necessary to support offline modification of the database. The topic of consistency guarantees is examined and we show that in a mobile environment the algorithm can at most provide causal consistency. We show how the algorithm can be modified to support both automatic and application-defined conflict resolution.

A prototype implementation of the algorithm based on a simplified model of a database system is presented. We evaluate the prototype in various scenarios and conclude that the time it takes for the system to synchronize 100 operations to 20 devices is about 0.2 second and scales linearly with the number of clients. Based on the evaluation, we consider the limitations of the algorithm and which tasks it may not be well-suited for.

External Examiner

Philippe Bonnet, ITU

Supervisor

Ken Friis Larsen, DIKU