Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers

DOI10.1137/0221063zbMath0759.68028OpenAlexW1994657234MaRDI QIDQ4027862

Arvin Park, Ramesh Subramonian, Charles U. Martel

Publication date: 9 March 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/4df81ec542a0f16467e8dcdd2536d5a0c6eb4dde

zbMATH Keywords

randomizationparallel computationsynchronizationfault-tolerancePRAMshared memory algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Distributed algorithms (68W15)

Related Items (9)

Clock construction in fully asynchronous parallel systems and PRAM simulation ⋮ Locality-preserving hash functions for general purpose parallel computation ⋮ The queue-read queue-write asynchronous PRAM model ⋮ Performing tasks on synchronous restartable message-passing processors ⋮ The complexity of synchronous iterative Do-All with crashes ⋮ An efficient write-all algorithm for fail-stop PRAM without initialized memory ⋮ A tight analysis and near-optimal instances of the algorithm of Anderson and Woll ⋮ The Do-All problem with Byzantine processor failures ⋮ The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms

This page was built for publication: Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers