539 The APRAM - THE ROUNDS COMPLEXITY MEASURE AND THE EXPLICIT COSTS OF
SYNCHRONIZATION R. Cole, O. Zajicek, January 1991
This paper studies the explicit costs of synchronization by examining an asynchronous generalization of the PRAM model called the APRAM model. The APRAM model and its associated complexity measure, the rounds complexity, are defined and then illustrated by designing and analyzing two algorithms: a parallel summation algorithm which proceeds along an implicit complete binary tree and a recursive doubling algorithm which proceeds along a linked list. In both cases replacing global synchronization with local synchronization yields algorithms with reduced complexity.