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.