M.Sc Thesis

M.Sc StudentBen-Chaim Yochai
SubjectMulti-Directional Asynchronous Updates of Replicas with
Auto-Counter Primary Key Attributes
DepartmentDepartment of Industrial Engineering and Management
Supervisor PROF. Avigdor Gal


This thesis proposes an efficient algorithm for a multi-directional asynchronous replication mechanism. Updates can occur at any site and are propagated asynchronously to other sites. The algorithm provides an enhancement to the uni-directional asynchronous update model, using the common snapshot replication method. It supports multi-directional updates and updates of replicas with an auto counter primary key attribute. Thus, it provides a solution for two desirable features when planning an information system database structure: 1) a replicated distributed system, and 2) local relations using efficient primary key access to relations.

Synchronous updates can be costly, as they require prolonged locking of data. Synchronous protocols are susceptible to network breakdowns, deadlocks and update inconsistencies. These problems are not present, when using an asynchronous model.

This algorithm, as opposed to previously proposed algorithms and methods for multi-directional asynchronous replication, is fully based on DBMS core tools. Therefore, it allows a natural extension for systems that already support the uni-directional asynchronous update model. The algorithm incurs some storage and CPU usage increase, yet it scales better and allows a continuous operative system in the face of site failures.

The proposed model is shown and proven to guarantee soundness, completeness, termination, and correctness. We also provide a complexity analysis of the algorithm.

Unlike previously proposed solutions, the algorithm was implemented, and tested, showing important results and terms of correctness, as well as specification of conditions for which the multi-directional model displays better performance over the uni-directional model.