Limitations of concurrency in transaction processing

• Published in: ACM transactions on database systems 1985-03, Vol.10 (1), p.1-28
• Main Authors: Franaszek, Peter, Robinson, John T.
• Format: Article
• Language: English
• Subjects: Applied sciences; Arbitrary-precision arithmetic; Computations on matrices; Computer science; control theory; systems; Computing methodologies; Concurrency control; Concurrent computing methodologies; Concurrent programming languages; Contextual software domains; Data management systems; Database management system engines; Database transaction processing; Design and analysis of algorithms; Error-correcting codes; Exact sciences and technology; General programming languages; Information systems; Information systems. Data bases; Interval arithmetic; Language types; Linear algebra algorithms; Mathematical analysis; Mathematics of computing; Memory organisation. Data processing; Numerical analysis; Operating systems; Parallel and distributed DBMSs; Process management; Randomness, geometry and discrete structures; Software; Software and its engineering; Software notations and tools; Software organization and properties; Symbolic and algebraic algorithms; Symbolic and algebraic manipulation; Theory of computation
• ISSN: 0362-5915; 1557-4644
• DOI: 10.1145/3148.3160

Given the pairwise probability of conflict p among transactions in a transaction processing system, together with the total number of concurrent transactions n, the effective level of concurrency E(n,p) is defined as the expected number of the n transactions that can run concurrently and actually do useful work. Using a random graph model of concurrency, we show for three general classes of concurrency control methods, examples of which are (1) standard locking, (2) strict priority scheduling, and (3) optimistic methods, that (1) E(n, p) n(1 - p/2)n-1, (2) E(n, p) (1 - (1 - p)n)/p, and (3) 1 + ((1 - p)/p)ln(p(n - 1) + 1) E(n, p) 1 + (1/p)ln(p(n - 1) + 1). Thus, for fixed p, as n ∞), (1) E 0 for standard locking methods, (2) E 1/p for strict priority scheduling methods, and (3) E ∞ for optimistic methods. Also found are bounds on E in the case where conflicts are analyzed so as to maximize E. The predictions of the random graph model are confirmed by simulations of an abstract transaction processing system. In practice, though, there is a price to pay for the increased effective level of concurrency of methods (2) and (3): using these methods there is more wasted work (i.e., more steps executed by transactions that are later aborted). In response to this problem, three new concurrency control methods suggested by the random graph model analysis are developed. Two of these, called (a) running priority and (b) older or running priority, are shown by the simulation results to perform better than the previously known methods (l)-(3) for relatively large n or large p, in terms of achieving a high effective level of concurrency at a comparatively small cost in wasted work.