A formal model for maximum concurrency in transaction systems with predeclared write sets

This paper presents a formal model for studying the computation complexity of scheduling a whole set of transactions simultaneously in a transaction system with predeclared write sets. The study clearly shows that there exists a fundamental tradeoff between the amount of concurrency achieved and the computation overhead necessary to achieve that amount of concurrency. However, it is suggested that based on variants of the model introduced here, schedulers which schedule a whole set of transactions simultaneously may still be able to achieve a higher level of concurrency than conventional schedulers within reasonable computation complexity constraints.Anglai