Previous [1] [2] [3] [4] [5]

Journal of Inforamtion Science and Engineering, Vol.5 No.1, pp.73-101 (January 1989)
An Ordering Based Concurrency Control Protocol
and Its Mathematical Behavior*

Yin-Fu Huang and Yeh-Hao Chin
Institute of Computer Science
National Tsing Hua University
Hsinchu, Taiwan 30043, Republic of China

A non-2PL and deadlock-free concurrency control method, called the Ascending Order Locking Protocol (AOLP), is proposed. Based on AOLP, a serializable and deadlock-free scheduler can be built and its correctness is proved. To show the merit of AOLP, 2PL and AOLP are evaluated mathematically on a factor called the "Average Lock Range" (ALR). The mathematical results indicate that the ALR for 2PL is the worst case of AOLP regardless of the access sequence of a 2PL-based transaction.

Keywords: concurrency control, locking protocol, deadlock, mathematical analysis

Received May 20, 1988; revised March 6, 1989.
Communicated by Lin-Shan Lee.
*This work was supported by the National Science Council under Grant NSC75-0408-E007-11 and Grant NSC76-0408-E007-13.