Paging with connections: FIFO strikes again

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00005085" target="_blank" >RIV/00216208:11320/07:00005085 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Paging with connections: FIFO strikes again

Original language description

We continue the study of the integrated document and connection caching problem. We focus on the case where the connection cache has a size of one and show that this problem is not equivalent to standard paging, even if there are only two locations for the pages, by giving the first lower bound that is strictly higher than k for this problem. We then give the first upper bound below the trivial value of 2k for this problem. Our upper bound is k+4l where l is the number of locations where the requested pages in a phase come from. This algorithm groups pages by location. In each phase, it evicts all pages from one location before moving on to the next location. In contrast, we show that the lru algorithm is not better than 2k-competitive.

Czech name

Stránkování se spojeními: FIFO se vrací

Czech description

Studujeme integrovaný model online načítání stránek souborů a spojení.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Volume of the periodical

377

Issue of the periodical within the volume

1-3

Country of publishing house

FR - FRANCE

Number of pages

10

Pages from-to

55-64

UT code for WoS article

—

EID of the result in the Scopus database

—