Computer Science Technical Report 95-03

Contention-Free Scalable Parallel Batch Processing:
Exploiting Separability and Independence

Barry Dwyer
Department of Computer Science
University of Adelaide
G.P.O. Box 498, Adelaide
South Australia 5005

October 30, 1995.

Abstract

This report describes how a very high throughput of transactions can be supported on a parallel processor architecture by processing batches of transactions. The resulting speed-up is strictly proportional to the number of processors, and is obtained because access to the database is contention free. The possibility of contention is eliminated by factorising the system specification into independent parts. Each part has its own database, which is consistent with the others only before and after each batch of updates. The factorisation is not possible for an arbitrary system specification, and requires its structure to have the properties of `separability' and `independence'. The techniques used are directly analogous to those traditionally used in sequential file batch processing.

Keywords

Transaction processing, parallel algorithms, batch processing, speed up, contention-free, inconsistent databases, separability, independence, sequential access.

This page has been accessed times since 12th June 1997.

Up to Barry Dwyer's Home Page