Both analysis and simulations of concurrency control methods for transaction processing are presented in this paper. Given p, the pairwise probability that two transactions conflict, and n, the total number of concurrent transactions, E ( n , p ) is defined to be the expected number of transactions that can run concurrently and do useful work (i.e., work that is not subsequently wasted by the transaction being aborted). The analysis shows that, for fixed p:
(1) E ( n , p ) → 0 as n → ∞ for standard locking,
(2) E ( n , p ) ≤ 1 &slash; p as n → ∞ for strict priority scheduling, and
(3) E ( n , p ) → ∞ as n → ∞ for optimistic methods, but grows at a rate of O ( log ( n ) ).
These results are validated by the simulation results, which also lead to the consideration of new concurrency control methods which have a smaller cost in terms of wasted work. This paper is easy to read. The mathematical results are easy to follow. The simulations carried out are described in great detail. The ways in which the assumptions present an idealized model of real systems and how these assumptions are nevertheless valid are discussed thoroughly. Figure 1 is misleading in that it does not carry the X-axis out far enough to show the curves approaching zero. This paper would be of interest to researchers in concurrency control methods and to implementors of transaction processing systems where a high level of concurrency is expected.
