Title :
A one-phase algorithm to detect distributed deadlocks in replicated databases
Author :
Kshemkalyani, Ajay D. ; Singhal, Mukesh
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Illinois Univ., Chicago, IL, USA
Abstract :
Replicated databases that use quorum-consensus algorithms to perform majority voting are prone to deadlocks. Due to the P-out-of-Q nature of quorum requests, deadlocks that arise are generalized deadlocks and are hard to detect. We present an efficient distributed algorithm to detect generalized deadlocks in replicated databases. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine the existence of a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst-case time complexity of 2d+2 hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform significantly better in both time and message complexity than the best known existing algorithms. We conjecture that this is an optimal algorithm, in time and message complexity, to detect generalized deadlocks if no transaction has complete knowledge of the topology of the WFG or the system and the deadlock detection is to be carried out in a distributed manner
Keywords :
communication complexity; computational complexity; concurrency control; database theory; distributed algorithms; graph theory; replicated databases; algorithm correctness; distributed algorithm; distributed deadlock detection; distributed wait-for-graph; majority voting; message complexity; node reducibility; one-phase algorithm; optimal algorithm; quorum-consensus algorithms; replicated databases; transaction; worst-case time complexity; Database systems; Delay; Distributed algorithms; Distributed databases; Fault tolerance; Senior members; System recovery; Topology; Transaction databases; Voting;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on