Randomized parallel prefetching and buffer management

We show that deterministic algorithms using bounded lookahead cannot fully exploit the potential of a parallel I/O system. Randomization can be used to significantly improve the performance of parallel prefetching and buffer management algorithms. Using randomization in the data layout and a simple prefetching scheme, we show that a read-once reference string of length N can be serviced in Theta(N/D) parallel I/Os in a D-disk system. For the case of read-many reference strings we introduce a novel algorithm using randomized write-back with a competitive ratio of Theta(root D). In contrast, we show that deterministic write-back results in a competitive ratio of at least Omega(D).