Tree Locking on Changing Trees
Vladimir Lanin, Dennis E. Shasha · 2011
: The tree locking protocol is a deadlock-free method of concurrency control defined and verified by Silberschatz and Kedem for data organized in a directed tree. Can the tree protocol work for applications that change the tree? We define a set of three operations capable of changing any tree to any other tree and show that the tree protocol continues to ensure serializability and deadlock-freedom in the presence of these operations. 1. Introduction A locking protocol is a set of rules for locking data items such that any concurrent computation following those rules is guaranteed to satisfy some set of conditions. Typically, these conditions may include serializability, deadlock freedom, or order preservation, which are all rigorously defined below. For example, the two-phase protocol guarantees serializability and order preservation, but not deadlock freedom, by forbidding an action (a term we use interchangeably with "transaction") to place a new lock after releasing a lock. In [SK8...