Expected advantage of asynchrony

Richard Cole, Ofer Zajicek

Research output: Contribution to journalArticlepeer-review


This paper studies the implicit costs of synchronization and the possible gains arising from avoiding synchronization in asynchronous environments. An asynchronous generalization of the PRAM model called the APRAM model is used and appropriate complexity measures are defined. The advantage that asynchrony provides is illustrated by 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.

Original languageEnglish (US)
Pages (from-to)286-300
Number of pages15
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - Oct 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Expected advantage of asynchrony'. Together they form a unique fingerprint.

Cite this