98-36: Broadcast Disk Paging with a Small Cache

DIMACS TR: 98-36

Broadcast Disk Paging with a Small Cache

Author: Vincenzo Liberatore

ABSTRACT
We consider the broadcast disk paging problem when the cache size is 2 and n pages are transmitted. We show an algorithm that is (n - 2 / (n - 2))-competitive and prove that no better competitive ratio is possible.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-36.ps.gz

DIMACS Home Page