About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIGMOD Record
Paper
Some Further Analysis of the Essential Blocking Recurrence
Abstract
In previous work,1 a random graph model of concurrency control was developed, in which there are n concurrent transactions 1991, and where for each pair of transactions (vertices), a conflict (edge between the vertices) initially occurs independently with probability p. Given such a graph, a scheduling function selects a subset of transactions to complete based on the conflicts and possibly on an ordering of the transactions. At the end of each unit of time, the transactions selected by the scheduling function to complete are removed from the graph, and are replaced by new transactions from a transaction sequence. For each pair of transactions in the new graph, if the transactions were both in the previous graph then a conflict occurs between them if and only if there was a conflict in the previous graph; otherwise one or both of the transactions are new and a conflict occurs independently with probability. © 1991, ACM. All rights reserved.