The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
On Broadcast Disk Paging
Sanjeev Khanna, Vincenzo Liberatore,
Pages. 1683-1702
Abstract Broadcast disks are an emerging paradigm for massive data
dissemination. In a broadcast disk, data is divided into n
equal-sized pages, and pages are broadcast in a round-robin
fashion by a server. Broadcast disks are effective because many
clients can simultaneously retrieve any transmitted data. Paging
is used by the clients to improve performance, much as in virtual
memory systems. However, paging on broadcast disks differs from
virtual memory paging in at least two fundamental aspects: \
A page fault in the broadcast disk model has a variable cost that
depends on the requested page as well as the current state of the
broadcast. Prefetching is both natural and a provably essential
mechanism for achieving significantly better competitive ratios in
broadcast disk paging. In this paper, we design a deterministic
algorithm that uses prefetching to achieve an O(n log k)
competitive ratio for the broadcast disk paging problem, where k
denotes the size of the client's cache. We also show a matching
lower bound of $Omega(nlog k)$ that applies even when the
adversary is not allowed to use prefetching. In contrast, we show
that when prefetching is not allowed, no deterministic online
algorithm can achieve a competitive ratio better than
$Omega(nk)$. Moreover, we show a lower bound of $Omega(n log
k)$ on the competitive ratio achievable by any nonprefetching
randomized algorithm against an oblivious adversary. These lower
bounds are trivially matched from above by known results about
deterministic and randomized marking algorithms for paging. An
interpretation of our results is that in the broadcast disk
paging, prefetching is a perfect substitute for randomization.
Contents 1. Introduction 2. Preliminaries 3. BDP and virtual memory paging: The case $n = k + 1$ 4. BDP algorithms without prefetching 5. BDP algorithms with prefetching 6. Delay model 7. Concluding remarks
Key words design of algorithms, online algorithms, competitive analysis, paging, distributed systems, client-server architecture, broadcast disks
Mathmatical Subject Classification 68A10, 68Q25, 68H