Kyungoh Min

University of Illinois at Urbana-Champaign. Department of Computer Science

Distributed deadlock in a distributed database system is a system state in which a set of concurrently running transactions are circularly waiting for each other to release resources. Over the past decade a number of algorithms have been proposed in the literature to detect such a deadlock, but not much attention has been given to their performance. Lack of understanding of the workload for such distributed algorithms has made it difficult to predict their performance prior to actually implementing them on a distributed system. In this thesis, we present an approach to distributed workload analysis which can be used as a basis for the performance study of distributed deadlock detection algorithms. In particular, the expected number of times a deadlock detection algorithm is locally initiated and the subsequent number of remote invocations are derived. Simulation work was done to validate our approach. For the performance analysis of distributed deadlock detection algorithms, we introduce three performance measures and explain how we can analytically derive them for a given system configuration. Then, we discuss some limitations of our approach and present the alternatives we took to study the performance of distributed deadlock detection algorithms using the results of the workload analysis. Finally, results from the analysis are validated using the results from the simulations and we compare the performance of two representative algorithms.

Kyungoh Min

About

Books

Join the club