The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms

DOI10.1137/S0097539791224030MaRDI QIDQ4376188zbMATH OpenOpenAlexFDO

Authors Philip MacKenzie

Publication date 10 February 1998

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

Full work available at URL https://doi.org/10.1137/s0097539791224030

zbMATH Keywords

expected timeload balancinglower boundsparallel algorithmsparallel computationPRAM modelrandomized parallel algorithms

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• Publication:4942231
• scientific article; zbMATH DE number 176073
• Robust parallel computations through randomization
• scientific article; zbMATH DE number 1304350
• Lower time bounds for randomized computation
• Parallel randomized load balancing: a lower bound for a more general model
• Parallel randomized load balancing: a lower bound for a more general model
• From randomizing polynomials to parallel algorithms
• scientific article; zbMATH DE number 1302200

Cited in

(2)

• Lower bounds for randomized exclusive write PRAMs
• A reduction theorem for randomized distributed algorithms under weak adversaries

This page was built for publication: The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms

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