On bulk-synchronous distributed-memory parallel processing of relational-database transactions

Abstract

This paper describes two parallel algorithms for the eÆcient processing of relational database transactions and presents a performance analysis of them. These algorithms are built upon the bulk-synchronous parallel model of computation. The well-de ned structure of this model enabled us to evaluate their performance by using an implementation independent and yet em- pirical approach which includes the e ects of synchronization, communication and computation. The analysis reveals that the algorithm which borrows ideas from optimistic parallel discrete event simulation achieves better performance than the classical approach for synchronizing con- current transactions on a distributed memory system.