A tight analysis and near-optimal instances of the algorithm of Anderson and Woll

DOI10.1016/J.TCS.2004.10.015zbMath1086.68152OpenAlexW2043191419MaRDI QIDQ706634

Grzegorz Malewicz

Publication date: 9 February 2005

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.015

zbMATH Keywords

Analysis of shared-memory algorithmsCertified Write-AllPRAM simulations

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complexity theory of efficient parallel algorithms
• Achieving optimal CRCW PRAM fault-tolerance
• Efficient parallel algorithms can be made robust
• Clock construction in fully asynchronous parallel systems and PRAM simulation
• Tentative and definite distributed computations: An optimistic approach to network synchronization
• Efficient execution of nondeterministic parallel programs on asynchronous systems
• The expected advantage of asynchrony
• Efficient PRAM simulation on a distributed memory machine
• Performing work with asynchronous processors
• Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers
• On the Complexity of Certified Write-All Algorithms
• Constructions of permutation arrays for certain scheduling cost measures
• Algorithms for the Certified Write-All Problem
• Parallel Algorithms with Processor Failures and Delays
• Writing-all deterministically and optimally using a nontrivial number of asynchronous processors
• An algorithm for the asynchronous Write-All problem based on process collision
• A Work-Optimal Deterministic Algorithm for the Certified Write-All Problem with a Nontrivial Number of Asynchronous Processors
• Parallelism in random access machines
• A Shared Memory Computer Display System

This page was built for publication: A tight analysis and near-optimal instances of the algorithm of Anderson and Woll