Date of Publication


Document Type

Master's Thesis

Degree Name

Master of Science in Computer Science

Subject Categories

Computer Sciences | Theory and Algorithms


College of Computer Studies


Computer Science

Thesis Adviser

Arturo I. Concepcion

Defense Panel Chair

Arturo I. Concepcion

Defense Panel Member

Renato Saquing
Marilou Jopillo


This paper presents an integrated concurrency and recovery algorithm. Strict timestamp ordering was used for concurrency control and incremental log with immediate updates for recovery. Strict timestamp ordering delays each write operation on a data item until there is no active transaction that issued a write on that file data. Reliability is achieved in the distributed database systems (DDBS) through replication and the recovery technique adopted. The algorithm allows a transaction to access any of the available copies of a data file. Since any copy of the data item can be accessed, data are available even in cases of site failures. The recovery technique ensures that each transaction would eventually terminate either by commiting or aborting. Moreover, it also takes care of restoring the database to a consistent state during recovery of a failed site. Consistency is achieved by controlling the accesses made to the database. This is solved by the concurrency control mechanism. Transaction restarts were minimized since strict timestamp ordering was used. The synchronization of the locals clocks was also included in the algorithm. The correctness of the algorithm was also proven and the message complexity of the algorithm was found to be of O (on), where a is a function of size of the queue used in the algorithm. A closed queueing network model was developed to evaluate the performance of the integrated algorithm. The performance measurements taken include response time, throughput and system utilization. The results indicate that the performance exhibited by the system is good even when subjected to heavy load.

Abstract Format






Accession Number


Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

111 p., 28 cm.


Distributed databases; Algorithms

Upload Full Text