Heat and Dump: competitive distributed paging
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper gives a randomized competitive distributed paging algorithm called Heat and Dump, The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to within a constant factor. This is in contrast to the linear optimal deterministic competitive ratio.Keywords
This publication has 13 references indexed in Scilit:
- The directory-based cache coherence protocol for the DASH multiprocessorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Strongly Competitive Algorithms for Paging with Locality of ReferenceSIAM Journal on Computing, 1996
- LogP: towards a realistic model of parallel computationPublished by Association for Computing Machinery (ACM) ,1993
- Ultracomputers: a teraflop before its timeCommunications of the ACM, 1992
- Competitive paging algorithmsJournal of Algorithms, 1991
- A strongly competitive randomized paging algorithmAlgorithmica, 1991
- Competitive paging with locality of referencePublished by Association for Computing Machinery (ACM) ,1991
- Competitive algorithms for on-line problemsPublished by Association for Computing Machinery (ACM) ,1988
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- One-Level Storage SystemIEEE Transactions on Electronic Computers, 1962