Modeling and Analysis of Distributed Database Concurrency Control Algorithms Using an Extended Petri Net Formalism

Abstract

Distributed database systems (DDBS) have received considerable attention in recent years. Being a relatively young research field, there are still many problems associated with DDB systems that need solution. Concurrency control is one of these problems and, probably, the most extensively studied. However, most of the work has concentrated on the development of alternative solutions and the field seems to be ready for some comparative analysis work. This paper reports the results of a performance evaluation study on distributed database concurrency control algorithms. The research has resulted in the development of a formalism, based on Petri nets, for modeling and analysis purposes. The formalism, called the Extended Place/Transition Nets (EPTN), is both descriptively powerful in that it can be used to model various algorithms precisely and succinctly and to communicate them in a clear manner, while at the same time lending itself to be used as a performance evaluation tool. An EPTN simulator is implemented and various algorithms are studied using this tool. This paper describes both the formalism and the performance results that have been obtained.