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

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Paging with connections: FIFO strikes again

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Paging with connections: FIFO strikes again

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

Kód důvěrnosti údajů

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

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

377

Číslo periodika v rámci svazku

1-3

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

10

Strana od-do

55-64

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—