Clock construction in fully asynchronous parallel systems and PRAM simulation

DOI10.1016/0304-3975(94)90162-7zbMath0810.68079OpenAlexW2022642396MaRDI QIDQ1330417

Yonatan Aumann, Michael O. Rabin

Publication date: 4 April 1995

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90162-7

zbMATH Keywords

adaptive adversary scheduleroverwhelming probabilitysynchronous computations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed algorithms (68W15)

Related Items (4)

Efficient execution of nondeterministic parallel programs on asynchronous systems ⋮ The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs ⋮ Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler ⋮ A tight analysis and near-optimal instances of the algorithm of Anderson and Woll

Cites Work

• On interprocess communication. I: Basic formalism
• On interprocess communication. II: Algorithms
• Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers
• On the Complexity of Certified Write-All Algorithms
• Efficient parallel algorithms on restartable fail-stop processors
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: Clock construction in fully asynchronous parallel systems and PRAM simulation