Division de Informatica

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-dened structure of this model enabled us to evaluate their performance by using an implementation independent and yet em-pirical approach which includes the eects 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.