Онлайн алгоритм

Є два види пам'яті — дискова, більша за об'ємом, але повільна, і кеш, швидка, але дуже мала. Вся пам'ять розбита на блоки. Нехай в кеш-пам'яті k блоків, а на диску, відповідно, набагато більше. До нас поступають запити на ті чи інші блоки, і ми повинні відразу ж їх обробити. Є два варіанти: або цей блок вже є в кеші, або його там немає. Якщо він в кеші є, то в цьому випадку ми майже не витрачаємо час. I тоді час роботи алгоритму можна вимірювати кількістю звернень до вінчестера. Алгоритми відрізняються один від одного реакцією на запити відсутніх в кеші блоків. Зрозуміло, що ми повинні блок, на який йде запит довантажити в кеш, не зрозуміло тільки, який з уже присутніх там блоків ми повинні для цього вивантажити. Звичайно, хотілося б вивантажити «непотрібний» блок, але оскільки ми обробляємо запити в реальному часі, ми не знаємо, який блок нам буде потрібний в подальшому. Постає й інше питання: як порівняти, який алгоритм найкращий[2].

Нехай ${\displaystyle {\mbox{A}}}$ — алгоритм, а ${\displaystyle {\mbox{r}}}$ — послідовність запитів. Час обробки послідовності запитів алгоритмів ${\displaystyle {\mbox{cost}}_{\mathrm {A} }(r)}$ — це кількість звернень до диску. Нехай ${\displaystyle {\mbox{opt}}}$ — якийсь оптимальний алгоритм. Тоді алгоритм ${\displaystyle {\mbox{A}}}$ називається ${\displaystyle {\mbox{c}}}$-оптимальним (c-competitive), якщо для будь-якого ${\displaystyle {\mbox{r}}}$: ${\displaystyle {\mbox{cost}}_{\mathrm {A} }(r)}$ ${\displaystyle \leq }$ ${\displaystyle c\cdot {\mbox{cost}}_{\mathrm {otp} }(r)+c_{1}}$. Де, ${\displaystyle {\mbox{c}}}$ — константа відносно ${\displaystyle {\mbox{r}}}$, але вона може залежати від k інших параметрів. Але це виконується — для детермінованих алгоритмів, для ймовірнісних, розглядається не час, а її математичне очікування. Будемо розглядати випадок, коли ${\displaystyle {\mbox{A}}}$ — ймовірнісний online алгоритм, а ${\displaystyle {\mbox{opt}}}$ — детермінований offline алгоритм («oblivious adversary»), тобто він заздалегідь всю знає послідовність запитів ${\displaystyle {\mbox{r}}}$.

Узагальнимо задачу кешування. Нехай у нас є деякий метричний простір з метрикою ${\displaystyle {d}}$, точки якого ми будемо розглядати як столики, і ${\displaystyle {k}}$ офіціантів, тобто деяка підмножина ${\displaystyle k}$ точок цього простору. Час від часу зі столиків надходять замовлення. Формально, замовлення — це координати столика. Замовлення потрібно обслуговувати, тобто треба вибрати одного з офіціантів і перемістити його в дану точку простору. Довжиною такого переміщення буде відстань між вихідною та кінцевою його точками. Кожен офіціант в кожен момент часу знаходиться біля якогось столика, і стан (конфігурація) системи описується множиною координат столиків, біля яких в даний момент знаходяться офіціанти. Тобто стан ${\displaystyle {X}}$ — це мультимножина (множина з кратними елементами), яка складається з ${\displaystyle {k}}$ точок простору. Назавжди зафіксуємо початковий стан ${\displaystyle {A}_{0}}$ нашої системи. Нехай ${\displaystyle {r}}$ = ${\displaystyle {r}_{1},{r}_{2},...,{r}_{n}}$ — послідовність замовлень. Тоді робоча функція ${\displaystyle {W}_{r}}$, що зіставляє стану ${\displaystyle {X}}$, найменшу відстань обслуговування ${\displaystyle {r}}$ з початкового стану ${\displaystyle {A}_{0}}$, в стан ${\displaystyle {X}}$. (Відстань обслуговування — це сума відстаней, пройдених всіма офіціантами, причому найменший шлях визначається за допомогою оптимального offline алгоритму, якому відоме ${\displaystyle r}$).[2]