Lower bounds for randomized exclusive write PRAMs

DOI10.1007/S002240000070zbMATH Open0893.68076OpenAlexW2041927040WikidataQ127121034 ScholiaQ127121034MaRDI QIDQ1384693FDOQ1384693

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/

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

zbMATH Keywords

randomizationexclusive write PRAM computations

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Cited In (7)

• Limitations of the QRQW and EREW PRAM models
• Title not available (Why is that?)
• Transforming comparison model lower bounds to the parallel-random-access-machine
• 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)