Synchronization based on data flow graphs for distributed and replicated databases

Abstract

In this study, we present concurrency control algorithms based on data flow graphs for newlinedistributed and replicated databases. newlineGraphical representations such as token models and structure models are widely applied newlineto represent data flow programs. Data flow programs are represented by directed graphs called newlinedata flow graphs where nodes represent the operations to be performed and arcs represent newlinethe data dependencies between them. The scheduling of operations is constrained by the data newlinedependencies identified by the graph. So, data flow scheduling mechanism could execute newlineoperations based upon the dependency constraints defined by the data flow graph. In this newlineway, concurrency is achieved through graphs. newlineIn this study we explore t~~ use of data flow graphs to design concurrency control newlinealgorithms. Precedence graphs are often used to determine serializability, and wait-for-graphs newlineare often used to detect deadlocks. Among these, acyclic precedence graphs indicate newlineserializability, and acyclic wait-for-graphs imply freedom from deadlocks. The tools for newlineserializability theory, and transaction management coupled with data flow graphs will provide newlinesolutions that are more efficient than conventional concurrency control techniques, such as, newlinetwo-phase locking. In the same light, we apply data flow graphs for concurrency control for newlinedistributed, and replicated databases. newlineAt first, we propose a concurrency control algorithm based on data flow graphs for a newlinedistributed database system. The concurrency control approaches based on locking, require newlineadditional efforts in deadlock detection and its elimination. The deadlock resolution protocols newlineassociated with deadlock detection algorithms abort (restart) some transactions in the deadlock newlinecycle. The restarted transaction must release all its locks and send out the requests again. The newlinepossibility of a deadlock is also connected to existence of unpredictable delays and repeated newlinerestarts of transactions in a deadlock cycle.