Duality Between Prefetching and Queued Writing with Parallel Disks

DOI10.1137/S0097539703431573zbMath1081.68119MaRDI QIDQ5317205

Peter Sanders, Jeffrey Scott Vitter, David A. Hutchinson

Publication date: 16 September 2005

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

zbMATH Keywords

randomized algorithm; lower bound; prefetching; load balancing; caching; external memory sorting

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68P10: Searching and sorting

68W10: Parallel algorithms in computer science

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68P20: Information storage and retrieval of data

68W20: Randomized algorithms