The expected advantage of asynchrony

This paper expands on the APRAM model introduced in [CZ89]. It introduces a model under which processes may proceed at different and varying speeds. Using this model the implicit costs of synchronization can be studied. The merit of the model is exhibited by analyzing two key algorithms, parallel summation along an implicit binary tree and recursive doubling, and demonstrating that both asynchronous algorithms perform better then their synchronous counterparts in asynchronous settings.