Lower bounds for randomized exclusive write PRAMs

DOI10.1007/S002240000070MaRDI QIDQ1384693zbMATH OpenOpenAlexWikidataFDO

Authors Philip MacKenzie

Publication date 20 April 1998

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://digital.library.unt.edu/ark:/67531/metadc743131/

zbMATH Keywords

randomizationexclusive write PRAM computations

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• Limits on the power of parallel random access machines with weak forms of write conflict resolution
• scientific article; zbMATH DE number 512845
• New lower bounds for parallel computation
• The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms

Cited in

(7)

• Limitations of the QRQW and EREW PRAM models
• Transforming comparison model lower bounds to the parallel-random-access-machine
• scientific article; zbMATH DE number 512845 (Why is no real title available?)
• Time lower bounds do not exist for CRCW PRAMs
• \(O (\log^* n)\) algorithms on a Sum-CRCW PRAM
• Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM
• Limits on the power of parallel random access machines with weak forms of write conflict resolution

This page was built for publication: Lower bounds for randomized exclusive write PRAMs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1384693)