Comparison of algorithms controlling concurrent access to a database: A combinatorial approach

AbstractIn this paper we compare the performances of concurrency control algorithms using the combinatorics of words. We characterize such control algorithms (as timestamp ordering or two-phases locking) by a triple of values, respectively estimating the frequency of accepted executions of concurrent transactions, its degree of authorized parallelism, and its load factor (a value related to the average number of elementary operations needed for the serialization of an execution). We effectively compute these values for timestamp ordering and two-phases locking in the case of the concurrent execution of two transactions. In particular, we obtain the exact and asymptotic frequencies of deadlocked executions of two transactions, and compare these two algorithms in various asymptotic situations