k -palvelinongelma - k-server problem

Tietotekniikan ratkaisematon ongelma :

Onko olemassa -kilpailukykyinen algoritmi palvelin -ongelman ratkaisemiseksi mielivaltaisessa metrisessa tilassa?

(lisää ratkaisemattomia ongelmia tietotekniikassa)

K -palvelin ongelma on ongelma tietojenkäsittelyteoria luokkaan verkossa algoritmeja , toinen kahdesta abstrakteja ongelmia metriset tilat , jotka ovat keskeisiä teoria kilpailukykyinen analyysin (toinen on metrinen tehtävä järjestelmiä ). Tässä ongelmassa online -algoritmin on ohjattava k -palvelimen joukon liikettä, joka esitetään metrisen tilan pisteinä, ja käsiteltävä pyyntöjä, jotka ovat myös avaruuden pisteitä. Jokaisen pyynnön saapuessa algoritmin on määritettävä, mikä palvelin siirretään pyydettyyn kohtaan. Algoritmin tavoitteena on pitää kaikkien palvelimien kokonaismatka pienenä suhteessa kokonaismatkaan, jonka palvelimet olisivat voineet siirtää optimaalisen vastustajan, joka tietää etukäteen koko pyyntöjen sarjan.

Ongelman esittivät ensin Mark Manasse , Lyle A.McGeoch ja Daniel Sleator (1990). Näkyvin avoin kysymys k -palvelinongelmasta on ns. K -palvelin -olettamus, jonka ovat esittäneet myös Manasse et ai. Tämä otaksuma todetaan, että on olemassa algoritmi ratkaista k -palvelin ongelma mielivaltaisessa metrinen tilaa ja mahdollisesti useita k palvelimia, jotka on kilpailukykyinen suhde täsmälleen k . Manasse et ai. pystyivät todistamaan olettamuksensa, kun k = 2, ja yleisemmille arvoille k, kun metrinen tila on rajoitettu täsmälleen k +1 pisteeseen. Chrobak ja Larmore (1991) todistivat oletuksen puumittareista . Erikoistapaus muuttujista, jossa kaikki etäisyydet ovat yhtä suuret kutsutaan henkilöhaku ongelma , koska se malleja ongelma sivun korvaavan algoritmien muistiin välimuistit, ja oli myös jo tiedetään olevan K -competitive algoritmia ( Sleator ja Tarjan 1985). Fiat et ai. (1990) osoitti ensin, että on olemassa algoritmi, jolla on rajallinen kilpailusuhde mille tahansa vakion k ja metrisen avaruuden suhteen, ja lopulta Koutsoupias ja Papadimitriou (1995) osoittivat, että työtoimintoalgoritmilla (WFA) on kilpailusuhde 2 k - 1. Kuitenkin monien muiden tutkijoiden ponnistelut kilpailusuhteen pienentämiseksi k: ksi tai parannetun alarajan saaminen on avoinna vuodesta 2014. Yleisin uskottu skenaario on, että työtoimintoalgoritmi on k -kilpailukykyinen. Tähän suuntaan Bartal ja Koutsoupias osoittivat vuonna 2000, että tämä pätee joihinkin erityistapauksiin (jos metrinen tila on viiva, painotettu tähti tai mikä tahansa k +2 pisteen mitta ).

Vuonna 2011 löydettiin satunnaistettu algoritmi, johon liittyi kilpailukykyinen Õ (log 2 k log 3 n). Vuonna 2017 julkaistiin satunnaistettu algoritmi, jolla oli kilpailukykyinen O (log 6 k), mutta se peruutettiin myöhemmin.

Esimerkki

Jos haluat tehdä ongelmasta konkreettisemman, kuvittele, että lähetät asiakastukihenkilöitä asiakkaille, kun heillä on ongelmia laitteidensa kanssa. Esimerkkiongelmassamme on kaksi teknikkoa, Mary ja Noah, jotka palvelevat kolmea asiakasta San Franciscossa, Kaliforniassa; Washington, DC; ja Baltimore, Maryland. Koska k -palvelin ongelma, palvelimet ovat teknikot, joten k = 2, ja tämä on 2-palvelin ongelma. Washington ja Baltimore ovat 35 mailin (56 mailin) ​​päässä toisistaan, kun taas San Francisco on 3 800 mailin (4800 km) päässä molemmista, ja aluksi Mary ja Noah ovat molemmat San Franciscossa.

Harkitse algoritmia palvelimien määrittämiseksi pyyntöihin, joka määrittää aina pyynnölle lähimmän palvelimen, ja oletetaan, että joka arkipäivän aamu Washingtonissa tarvitsee apua, kun taas joka arki -iltapäivä Baltimoren asiakas tarvitsee apua ja että San Franciscon asiakas ei koskaan tarvitse apua. Sitten algoritmimme määrittää yhden palvelimista (esimerkiksi Mary) Washingtonin alueelle, minkä jälkeen hän on aina lähin palvelin ja määritetään aina kaikkiin asiakaspyyntöihin. Näin ollen algoritmistamme aiheutuu joka päivä kustannuksia matkoista Washingtonin ja Baltimoren välillä ja takaisin, 110 mailia. Vuosi tämän pyyntömallin jälkeen algoritmille on tehty 20 500 mailin (33 000 km) matka: 3000 lähettää Marian itärannikolle ja 17 500 matkaa Washingtonin ja Baltimoren välillä. Toisaalta optimaalinen vastustaja, joka tuntee tulevan pyyntöaikataulun, olisi voinut lähettää sekä Maryn että Nooan Washingtoniin ja Baltimoreen, maksamalla kerran 6 700 mailia matkaa, mutta välttäen sitten mahdolliset tulevat matkakulut. Algoritmimme kilpailusuhde tässä syötteessä on 20 500/6000 tai noin 3,4, ja tämän esimerkin parametreja säätämällä tämän algoritmin kilpailusuhde voidaan tehdä mielivaltaisen suureksi.

Näin näemme, että aina lähimmän palvelimen määrittäminen voi olla kaukana optimaalisesta. Toisaalta vaikuttaa hölmöltä, että algoritmi, joka ei tiedä tulevia pyyntöjä, lähettää molemmat teknikonsa pois San Franciscosta, koska seuraava pyyntö voi olla kyseisessä kaupungissa ja sen on lähetettävä joku takaisin heti. Joten näyttää siltä, ​​että k -palvelimen algoritmin on vaikea tai mahdotonta toimia hyvin vastustajaansa verrattuna. Kuitenkin 2-palvelinongelmaan on olemassa algoritmi, jonka kokonaismatka on aina enintään kaksi kertaa vastustajan etäisyys. K -palvelin arveluihin todetaan, että samanlaisia ratkaisuja olemassa ongelmia tahansa useampien teknikot.

Viitteet

  1. ^ http://people.csail.mit.edu/madry/docs/kserver.pdf
  2. ^ "Toinen ärsyttävä avoin ongelma" . 19. marraskuuta 2011.
  3. ^ [1] joka rakentui läheisesti [2]
  4. ^ "Virhe: Sulava HSTS ja satunnaistettu k-palvelin-olettamus" .
  • Fiat, A .; Rabani, Y .; Ravid, Y. (1990). "Kilpailukykyiset k -palvelinalgoritmit". 31. vuosittaisen IEEE Symposium on Tietojenkäsittelytieteen perusteet -artikkelit . s. 454–463.