Az online algoritmusok k-szerver probléma
Bittner Emese, Imreh Csanád, Nagy-György Judit Szegedi Tudományegyetem Online algoritmusok Online problémáról beszélünk azokban az esetekben, ahol nem ismert az egész input, hanem az algoritmus az inputot részenként kapja meg, és a döntéseit a megkapott részletek alapján a további részekre vonatkozó információk nélkül kell meghoznia. Az algoritmusok hatékonyságát általában a versenyképességi analízis alapján mérik (a másik használt elemzési módszer az átlagos eset analízis). Optimalizálási feladatok esetén minden I inputra OPT (I) jelöli az optimális megoldás célfüggvényértékét és egy A algoritmusra A(I) jelöli az algoritmus által az A inputon felvett célfüggvényértéket. Minimalizálási feladatok esetén egy online A algoritmusra azt mondjuk C-versenyképes, ha minden I inputra teljesül A(I) ≤ C · OPT (I). Gyakran a definícióban megengednek egy inputtól független D additiv konstanst, azaz az A(I) ≤ C · OPT (I) + D egyenl˝otlenségnek kell teljesülnie minden inputra, ekkor enyhe versenyképességr˝ol beszélünk. Egy algoritmus versenyképességi hányadosának a legkisebb C számot nevezzük, amire C-versenyképes. Szórakozott professzor Adott egy parkoló, ahol egy professzor a kocsiját tartja. A parkolóhelyeket egy −n és n közötti egész szám azonosítja, az azonosító szerint helyezkednek el balról jobbra. (Az egyszer˝ubb számolás érdekében tegyük fel, hogy 0-ás parkolóhely nincs.) A professzor kijön az egyetemr˝ol az −1 és 1 parkolóhelyek között. Nem tudja hol parkol, és meg akarja keresni a kocsiját. Normális algoritmus: Kipróbáljuk a pozitív irányt, elmegyünk a kocsiig vagy a parkoló végéig, és ha nem találjuk meg a kocsit, akkor visszafordulunk és kipróbáljuk a másik oldalt. A legrosszabb input a −n, amelyre az algoritmus költsége 3n, az optimális költség n, így a versenyképességnél számolt hányados 3. Normális algoritmus: Kipróbáljuk a pozitív irányt, elmegyünk a kocsiig vagy a parkoló végéig, és ha nem találjuk meg a kocsit, akkor visszafordulunk és kipróbáljuk a másik oldalt. A legrosszabb input a −n, amelyre az algoritmus költsége 3n, az optimális költség n, így a versenyképességnél számolt hányados 3. 1
Az algoritmus nem 3-versenyképes, mivel ez a klasszikus értelemben vett legrosszabb eset. Versenyképesség szempontjából a legrosszabb eset a −1, hiszen ott az algoritmus költsége 2n + 1 az optimális költség 1 és a hányados 2n + 1 A következ˝o gondolat, hogy a i-dik fázisban elmegyünk jobbra az i-edik helyig, majd onnan, ha nem találjuk a kocsit balra a −i-edik helyig. Ez az algoritmus sem konstans versenyképes, hiszen ha a kocsi a −n helyen áll, akkor az optimális költség n az algoritmus költsége 4 ∑n−1 i=1 i + 3n = n(2n + 1). Ezt követ˝oen adódik a gondolat, hogy kevesebb irányváltoztatással keressük a kocsit. Az i-dik fázisban elmegyünk jobbra az 2i -edik helyig, majd onnan, ha nem találjuk a kocsit balra az −2i -edik helyig. Err˝ol az algoritmusról már belátható, hogy konstans-versenyképes. Tegyük fel, hogy a kocsi a k helyen van. Legyen i olyan kitev˝o, amelyre 2i < |k| ≤ 2i+1 . Ekkor az algoritmus által megtett lépések száma kisebb, mint j i+2 ≤ 16|k|, azaz az algoritmus valóban konstans versenyképes. 4 ∑i+1 j=0 2 < 4 · 2 k-szerver probléma Egy (M, d) párost, ahol M a metrikus tér pontjait tartalmazza, d pedig az M × M halmazon értelmezett távolságfüggvény metrikus térnek nevezünk, ha a távolságfüggvényre teljesülnek az alábbi tulajdonságok • d(x, y) ≥ 0 minden x, y ∈ M esetén, • d(x, y) = d(y, x) minden x, y ∈ M esetén, • d(x, y) + d(y, z) ≥ d(x, z) minden x, y, z ∈ M esetén, • d(x, y) = 0 akkor és csak akkor teljesül, ha x = y. A k-szerver problémában adott egy metrikus tér, és van k darab szerverünk, amelyek a térben mozoghatnak. A probléma során a tér pontjaiból álló kérések egy listáját kell kiszolgálni azáltal, hogy a megfelel˝o kérések helyére odaküldünk egy-egy szervert. A probléma on-line, ami azt jelenti, hogy a kéréseket egyenként kapjuk meg, és az egyes kéréseket a további kérések ismerete nélkül azok érkezése el˝ott kell kiszolgálnunk. A cél a szerverek által megtett össztávolság minimalizálása. Lapozás mint speciális eset A lapozási probléma a számítógépek gyorsmemóriájának a kezelését modellezi. Adott lapok egy univerzuma, és ebb˝ol vett lapok egy sorozata az input. Az algoritmusnak egy k lap kapacítású gyorsmemóriát kell kezelnie. Ha az aktuálisan igényelt lap nincs a memóriában, akkor a lapot az algoritmusnak be kell tennie és ehhez, amennyiben már nincs hely, valamely lapot ki kell raknia. Ezt az eseményt, amikor egy igényelt lap nincs a memóriában hibának hívjuk, és a cél a hibák számának minimalizálása. Ha az univerzum a metrikus tér és a memória celláit a szervereknek feleltetjük meg (egy szerver azon a ponton van, amely lapot a cella tartalmazza), akkor egy k-szerver feladatot kapunk. A metrikus térben bármely két pont távolsága 1. Az ilyen tereket uniform térnek nevezzük.
következmény: Uniform tereken vannak k-versenyképes algoritmusok, és nincsen olyan algoritmus, amely versenyképe hányadosa kisebb, mint k. Mohó algoritmus Természetes gondolat a kéréseket mindig a legközelebbi szerverrel kiszolgálni. Lemma A mohó algoritmus nem konstans versenyképes. 2
1. ábra.
Munkafüggvény algoritmus Azt a metrikus tér pontjaiból álló multihalmazt, amely megadja mely pontokban helyezkednek el a szerverek (azért kell multihalmazokat használnunk, mert egy pontban több szerver is lehet) a szerverek konfigurációjának nevezzük. Legyen A0 az on-line szerverek kezdeti konfigurációja. Ekkor a t-edik kérés utáni X multihalmazra vonatkozó munkafüggvény wt (X) a minimális költség, amellyel kiszolgálható az els˝o t kérés az A0 konfigurációból kiindulva úgy, hogy a szerverek az X konfigurációba kerüljenek a kiszolgálás végén. A munkafüggvény algoritmus a munkafüggvényt használja. Legyen At−1 a szervereknek a konfigurációja közvetlenül a t-edik kérés érkezése el˝ott. Ekkor a munkafüggvény algoritmus azzal az s szerverrel szolgálja ki az Rt pontban megjelent kérést, amelynek a P helyére a wt−1 (At−1 \ P ∪ Rt ) + d(P, Rt ) érték a minimális. Példa Tekintsük azt a metrikus teret, amelyben három pont van A, B és C, a távolságok d(A, B) = 1, d(B,C) = 2, d(A,C) = 3. A kezdeti szerver konfiguráció legyen A, B. Ekkor a kezdeti munkafüggvények w0 ({A, A}) = 1, w0 ({A, B}) = 0, w0 ({A,C}) = 2, w0 ({B, B}) = 1, w0 ({B,C}) = 3, w0 ({C,C}) = 4. Legyen az els˝o kérés a C pontban. Ekkor w0 ({A, B} \ {A} ∪ {C}) + d(A,C) = 3 + 3 = 5 és w0 ({A, B} \ {B} ∪ {C}) + d(B,C) = 2 + 2 = 4, így a M UNKAFÜGGVÉNY algoritmus a B pontban lev˝o szerver küldi a kérés kiszolgálására. Tétel A M UNKAFÜGGVÉNY algoritmus enyhén (2k − 1)-versenyképes. (Koutsoupias and Papadimitriou 1995) Sejtés A M UNKAFÜGGVÉNY algoritmus enyhén k-versenyképes. Dupla lefed˝o algoritmus Egy gyakran vizsgált speciális tér az egyenes. Az egyenes pontjait a valós számoknak feleltetjük meg, és két pontnak a-nak és b-nek a távolsága |a − b|. Erre az esetre, ahol a metrikus tér egy egyenes, Chrobak és Larmore (1990) kifejlesztett egy k-versenyképes algoritmust, amelyet dupla lefed˝o algoritmusnak nevezünk. Az algoritmus a P kérést a P-hez legközelebb es˝o s szerverrel szolgálja ki, és amennyiben vannak szerverek P-nek az s-el átellenes oldalán is, akkor azon szerverek közül a P-hez legközelebbit d(s, P) egységnyit mozdítja P felé. A továbbiakban a dupla lefed˝o algoritmust DL-el jelöljük. 3
Tétel A DL algoritmus enyhén k-versenyképes ha a metrikus tér egy egyenes. Példa 0
2
6
0
3
0
3 1
0
5 7
2
7
2
7
2. ábra.
Fa metrikus tér Az egyenes általánosításaként kaphatjuk a fa metrikus teret. vegyünk egy tetsz˝oleges súlyozott fát. A metrikus tér pontjai a fa csúcsai továbbá minden élhez és minden 0 < λ < 1 számhoz definiáljuk az élet λ és 1 − λ arányban felosztó pontokat. Mivel a fa körmentes ezért bármely két pont között egyetlen út vezet. A két pont közötti távolság a közöttük vezet˝o út hossza. Az élek bels˝o pontjai esetén az él hosszának a felosztásnak megfelel˝o részét vesszük figyelmebe. Azt mondjuk, hogy egy szerver lát egy pontot, ha a közte és a pont között lev˝o úton nincs másik szerver. Lefed˝o algoritmus Az algoritmus egy kérést úgy szolgál ki, hogy minden szervert, ami látja a kérés helyét egyenletes sebességgel mozgat a szerver felé. (A kérést látó szerverek halmaza változik a szerverek mozgatása során.) tétel A lefed˝o algoritmus enyhén k-versenyképes, ha a metrikus tér egy fa.
3. ábra. Visszautasításos online problémák
4
A visszautasításos modellekben az egyes inputrészeknek van egy büntetés értéke is. Az algoritmus visszautasíthatja az egyes részeket a végrehajtásuk helyett, de ekkor ki kell fizetnie a büntetést. Az elfogadott feladatrészekre adott megoldáson vett értékét a célfüggvénynek növeljük a kifizetett büntetésekkel. • Bartal et al 00, Seiden 01, Imreh, Németh 09: Visszautasításos ütemezés • Dósa, He 06, Nagy-György, Imreh 07: Visszautasításos ütemezés gépköltségekkel • Dósa, He 06, Epstein 08: Visszautasításos ládapakolás • Epstein et al 08: Visszautasításos gráfszínezés • Epstein et al 11: Visszautasításos memóriakezelés • Bittner et al 12: Visszautasításos k-szerver feladat • Jaillet, Lu 13: Visszautasításos utazó ügynök Uniform terek T HR Algoritmus Minden ponthoz egy számlálót rendelünk 0 kezdeti értékkel. (i) Növeljük a kért pont számlálóját a kérés büntetésével. Ha a számláló értéke eléri az 1-et jelöljük meg a pontot. Amikor a k + 1-dik pont is jelölté válik, akkor töröljük az összes jelölést (az újonnan kért pontét is). Az új pont számlálója csökkenjen 1-el, a többiekét állítsuk 0-ra. (ii) Ha a kérést lefedi egy szerver, akkor nem mozgatunk szervert. Ha a kért pont jelöletlen és nincs rajta szerver, akkor visszautasítjuk. (iii) Ha a kért pont jelölt és nincs rajta szerver, akkor a legrégebben mozgatott szervert küldjük oda a kiszolgálására. Tétel A THR algoritmus (2k + 1)-versenyképes a visszautasításos k-szerver problémára. A M UNKAFÜGGVÉNY algoritmus A M UNKAFÜGGVÉNY algoritmus kiterjeszthet˝o a visszautasításos modellre. A munkafüggvény definíciójában az optimális kiszolgálás költségénél figyelembe kell venni azt is, hogy lehetséges az egyes kérések visszautasítása. Továbbá az aktuális kérésnél is figyelmbe kell venni azt a lehet˝oséget, hogy nem mozdítunk szervert, hanem visszautasítjuk a kérést. Tétel A M UNKAFÜGGVÉNY algoritmus enyhén 4k − 1-versenyképes a visszautasításos k-szerver feladatra. Tétel A M UNKAFÜGGVÉNY algoritmus enyhén 5-versenyképes a visszautasításos k-szerver feladatra, ha k = 2. Tétel A M UNKAFÜGGVÉNY algoritmus enyhén 2k + 1-versenyképes a visszautasításos k-szerver feladatra, ha a metrikus tér az egyenes. Tétel A M UNKAFÜGGVÉNY algoritmus enyhén 2k + 1-versenyképes a visszautasításos k-szerver feladatra, ha a metrikus tér pontosan k + 1 pontot tartalmaz. Egy memóriamentes algoritmus EDC algoritmus Az algoritmus egy ri kérést a következ˝oképpen szolgál ki. 5
(i) Vegyük az ri -hez legközelebbi szerver, jelölje az ri -t˝ol vett távolságát d. (ii) Ha d ≤ pi /2 akkor az algoritmus kiszolgálja a kérést a legközelebbi szerverrel, továbbá ha van szerver a kérés másik oldalán is, akkor azok közül a legközelebbi is d távolságot mozog a kérés felé. (iii) Ha d > pi /2, akkor a kérést visszautasítjuk, és a legközelebbi szerver mozog pi /2 távolságot a kérés felé. Továbbá ha van szerver a kérés másik oldalán is, akkor azok közül a legközelebbi is pi /2 távolságot mozog a kérés felé. Tétel Az EDC algoritmus 3k-versenyképes. Bizonyítás Vegyünk egy tetsz˝oleges sorozatát a kéréseknek, jelölje ezt az inputot I. Az eljárás elemzése során feltételezzük, hogy párhuzamosan fut a EDC algoritmus és egy optimális off-line algoritmus OPT. Szintén feltesszük, hogy minden kérést els˝oként az off-line algoritmus szolgál ki, utána pedig az on-line algoritmus. Az on-line algoritmus szervereit és egyben a szerverek pozícióit, (amelyek valós számok az egyenesen) s1 , . . . , sk jelöli, az optimális off-line algoritmus szervereit és egyben a szerverek pozícióit x1 , . . . , xk jelöli. Mivel a szerverek rendszeres átjelölésével ez elérhet˝o feltételezzük, hogy s1 ≤ s2 ≤ · · · ≤ sk és x1 ≤ x2 ≤ · · · ≤ xk mindig teljesül. A tétel állítását a potenciálfüggvény technikájával igazoljuk. A potenciálfüggvény a szerverek aktuális pozíciójához rendel egy értéket, az on-line és az off-line költségeket a potenciálfüggvény változásainak alapján hasonlítjuk össze. Legyen a potenciálfüggvény k
Φ = k ∑ |xi − si | + ∑ (s j − si ). i< j
i=1
Legyen a potenciálfüggvény értéke Φi az i-edik kérés kiszolgálása után. És legyen EDCi és OPTi az i-edik kérés kiszolgálásának a költsége az EDC és OPT algoritmusoknál. Igazoljuk, hogy Φi − Φi−1 ≤ k · OPTi − 1/3 · EDCi . OPT kiszolgálja a kérést és EDC csak 1 szervert mozgat. Feltehetjük, hogy a kérés kisebb, mint s1 . Els˝oként OPT szolgálja ki és OPTi -t mozog. Ezzel Φ els˝o része legfeljebb k · OPTi -vel n˝o, a második nem változik. Legyen δ = min{d(ri , s1 ), pi /2}. Ekkor EDC szervere δ távolságot mozog. Ha δ = d(ri , s1 ) ≤ pi /2, akkor eléri a kérést, majd kiszolgálja, és ekkor EDCi = δ. Ha δ = pi /2 < d(ri , s1 ), akkor EDC nem éri el, így kifizeti a büntetést is, ami 2δ, tehát ekkor EDCi = 3δ. Φ els˝o részében |x1 − s1 | csökken δ-val, a második részben az s j − s1 értékek növekednek δ-val. Tehát Φi − Φi−1 ≤ k · OPTi − k · δ + (k − 1)δ = k · OPTi − δ ≤ k · OPTi − 1/3 · EDCi . OPT visszautasítja a kérést és EDC csak 1 szervert mozgat. Ismét feltehetjük, hogy a kérés kisebb, mint s1 . OPT visszautasítja a kérést így a költsége pi és Φ nem változik OPT lépése alatt. Legyen δ = min{d(s1 , ri ), pi /2}. Ekkor EDC szervere δ távolságot megy. Ha δ = d ≤ pi /2, akkor eléri a kérést, majd kiszolgálja és EDCi = δ. Ha δ = pi /2 < d(ri , s1 ), akkor EDC nem éri el, így kifizeti a büntetést is, ami 2δ, tehát ekkor EDCi = 3δ. 6
Φ els˝o részében |x1 − s1 | csökken δ-val, a második részben az s j − s1 értékek növekednek δ-val. Tehát Φi − Φi−1 ≤ k · δ + (k − 1)δ = 2k · δ − δ ≤ 2kpi /2 − δ ≤ k · OPTi − 1/3 · EDCi . OPT kiszolgálja a kérést és EDC két szervert mozgat. Ekkor EDC-nek van a kérés mindkét oldalán szervere, legyenek a legközelebbi s j és a másik oldalról a legközelebbi s j+1 . Az offline mozgás növeli Φ els˝o részét legfeljebb k · OPTi -vel, a másik rész nem változik. EDC két szervert mozgat, mindkett˝ot δ = min{d(s j , ri ), pi /2} távolságot. Ha δ = d(s j , ri ) ≤ pi /2, akkor kiszolgálja a kérést és EDCi = 2δ. Egyébként büntetést is fizet, ami 2δ, így EDCi = 4δ. Φ els˝o részében a j-dik és j + 1-dik tag változik. Mivel xl = ri valamely l-re, ezért az egyik tag csökken, így az els˝o rész nem n˝o. Kiszámolható, hogy a második rész változása −2δ. Tehát Φi − Φi−1 ≤ k · OPTi − 2 · δ ≤ k · OPTi − 1/2 · EDCi ≤ k · OPTi − 1/3 · EDCi . OPT visszautasítja a kérést és EDC két szervert mozgat. Ekkor EDC-nek van a kérés mindkét oldalán szervere, legyenek a legközelebbi s j és a másik oldalról a legközelebbi s j+1 . Az offline algoritmus lépése nem változtatja meg Φ-t. EDC két szervert mozgat, mindkett˝ot δ = min{d(s j , ri ), pi /2} távolságot. Ha δ ≤ pi /2, akkor kiszolgálja a kérést és EDCi = 2δ, egyébként büntetést is fizet, így EDCi = 4δ. Φ els˝o részében a j-dik és j + 1-dik tag változhat mindkett˝o legfeljebb δ-val n˝o. Kiszámolható, hogy a második rész változása −2δ. Tehát Φi − Φi−1 ≤ 2k · δ − 2δ ≤ 2kpi /2 − 2δ ≤ k · OPTi − 1/2 · EDCi ≤ k · OPTi − 1/3 · EDCi . Alsó korlát Tétel Tetsz˝oleges, legalább k + 1 pontot tartalmazó metrikus térre igaz, hogy nincs olyan online algoritmus a visszautasításos k-szerver problémára, amelynek kisebb a versenyképességi hányadosa, mint 2k + 1. Következmény A M UNKAFÜGGVÉNY algoritmus eléri a lehetséges legkisebb versenyké- pességi hányadost a visszautasításos 2-szerver problémára, továbbá tetsz˝oleges k-ra, ha a metrikus tér k + 1 pontot tartalmaz vagy a metrikus tér az egyenes. Következmény A THR algoritmus eléri a lehetséges legkisebb versenyképességi hányadost a visszautasításos k-szerver problémára uniform terek esetén. Következmény Az EDC algoritmus eléri a lehetséges legkisebb versenyképességi hányadost az egyenesen a visszautasításos 1-szerver problémára.
7
