LCL: A Lock Chain Length-based Distributed Algorithm for Deadlock Detection and Resolution

The problem of deadlock detection and resolution in database systems has been studied for decades. While it has long been a mature feature of classical centralized database systems for many years, its use in distributed database systems remains in its infancy. Don P. Mitchell and Michael J. Merritt (M&M) proposed a simple and fully distributed deadlock detection and resolution algorithm, but its assumption that each process waits on only one resource at a time prevents it from being generally applicable. Inspired by this algorithm, we design and implement LCL (Lock Chain Length), an elegant and generally applicable algorithm for resource deadlock detection and resolution in distributed environments without a restriction of the above kind. Our extensive emulation experiments show that the proposed approach LCL significantly outperforms the state-of-the-art competitor M&M. In addition, it has been applied to the OceanBase distributed relational database system, and our extensive experiments in OceanBase illustrate that LCL is also more efficient than M&M in deadlock detection and resolution.