Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis

Joan Boyar, Sushmita Gupta, Kim Skak Larsen

Research output: Contribution to journalConference articleResearchpeer-review

Abstract

Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis. In this model, FWF is shown to be strictly worse than both LRU and FIFO on any access graph. LRU is shown to be strictly better than FIFO on paths and cycles, but they are incomparable on some families of graphs which grow with the length of the sequences.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume7357
Pages (from-to)328-339
Number of pages12
ISSN0302-9743
DOIs
Publication statusPublished - 2012
Event13th Scandinavian Symposium and Workshops on Algorithm Theory - Helsinki, Finland
Duration: 4. Jul 20126. Jul 2012
Conference number: 13

Conference

Conference13th Scandinavian Symposium and Workshops on Algorithm Theory
Number13
CountryFinland
CityHelsinki
Period04/07/201206/07/2012

Fingerprint

Strictly
Graph in graph theory
Competitive Analysis
Paging
Locality
Cycle
Path
Model
Family

Cite this

@inproceedings{df9ce0314b134dcba2fccfe5fc47c3b8,
title = "Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis",
abstract = "Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis. In this model, FWF is shown to be strictly worse than both LRU and FIFO on any access graph. LRU is shown to be strictly better than FIFO on paths and cycles, but they are incomparable on some families of graphs which grow with the length of the sequences.",
keywords = "online algorithms, paging, access graphs, relative worst order analysis",
author = "Joan Boyar and Sushmita Gupta and Larsen, {Kim Skak}",
year = "2012",
doi = "10.1007/978-3-642-31155-0_29",
language = "English",
volume = "7357",
pages = "328--339",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Heinemann",

}

Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis. / Boyar, Joan; Gupta, Sushmita; Larsen, Kim Skak.

In: Lecture Notes in Computer Science, Vol. 7357, 2012, p. 328-339.

Research output: Contribution to journalConference articleResearchpeer-review

TY - GEN

T1 - Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis

AU - Boyar, Joan

AU - Gupta, Sushmita

AU - Larsen, Kim Skak

PY - 2012

Y1 - 2012

N2 - Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis. In this model, FWF is shown to be strictly worse than both LRU and FIFO on any access graph. LRU is shown to be strictly better than FIFO on paths and cycles, but they are incomparable on some families of graphs which grow with the length of the sequences.

AB - Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst order analysis. In this model, FWF is shown to be strictly worse than both LRU and FIFO on any access graph. LRU is shown to be strictly better than FIFO on paths and cycles, but they are incomparable on some families of graphs which grow with the length of the sequences.

KW - online algorithms

KW - paging

KW - access graphs

KW - relative worst order analysis

U2 - 10.1007/978-3-642-31155-0_29

DO - 10.1007/978-3-642-31155-0_29

M3 - Conference article

VL - 7357

SP - 328

EP - 339

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -