Hajautetut järjestelmät K07 LH 4 Tanenbaum Ch 5 tai CoDoKi Ch 11, 12 1. Totaalijärjestyksen toteuttava monilähetys (multicast) voidaan toteuttaa seuraavasti (ns. ISIS-algoritmi; ks esim. CoDoKi, 2. ed., kuva 11.10): - asiakas lähettää sanoman kaikille toisinnoille - kukin toisinto ehdottaa sanomalle järjestysnumeroa, jonka palauttaa asiakkaalle - asiakas valitsee suurimman ehdotuksen lopulliseksi järjestysnumeroksi ja lähettää sen toisinnoille - toisinto luovuttaa sanoman sovellukselle, kun sanoma on saanut lopullisen numeron eikä jonossa ole yhtään sanomaa, jolla olisi pienempi (tilapäinen tai lopullinen) järjestysnumero. Täsmennä algoritmin yksityiskohdat (aikaleimojen käyttö, jonotus). Perustele ratkaisun oikeellisuus. Vertaa algoritmia luennolla / Tanenbaumin kirjassa esitettyyn (samanlaisuus/erilaisuus, suorituskyky, muut näkökohdat). 2. Rengasvaalialgoritmista on olemassa myös versio, jossa vaalisanomassa kuljetetaan vain senhetkistä johtajakandidaatin tunnusta. Jos usea osallistuja käynnistää vaalin "samanaikaisesti", niin verkkoa alkaa kiertää ylimääräisiä vaalisanomia, jotka olisi oikeastaan mukava saada hävitettyä niin pian kuin mahdollista. Suunnittele algoritmiin ylimääräiset sanomat hävittävä osa. 3. a) Oletetaan, että sarjallistuvuus toteutetaan lukkojen avulla (2PL). Mitkä suoritusjärjestykset (reaaliajassa) ovat mahdollisia, kun seuraavat transaktiot käynnistyvät rinnakkain: T: x:=Read(i); Write(j,44) U: Write(i,55); Write(j,66) ? b) Miksi transaktio ei voi jostain lukosta luovuttuaan enää varata uusia lukkoja? Anna esimerkki. c) Voidaanko kaksivaiheista lukitusta lieventää lukulukkojen osalta eli voitaisiinko lukulukko avata sen jälkeen, kun transaktio ei enää koske ko. tietoon? d) Kuka varaa ja kuka vapauttaa hajautetun transaktion lukot? 4. Seuraavat transaktiot käynnistyvät rinnakkain: T: ... x=Read(i); Write(j,2*x); ... U: y=Read(i); z=Read(j); Write(i,y+z); (i,j ovat tietokannan tietoja, x,y,z ovat ohjelman muuttujia). Käytä näiden transaktioiden erilaisia etenemisnopeuksia reaaliajassa havainnollistamaan a) (pessimistisen) aikaleimamenetelmän (jossa kaikki kirjoitetaan suoraan näkyviin) b) optimistisen (aikaleima-) menetelmän (taaksepäin validointi) toimintaperiaate (kummassakin tapauksessa voit olettaa: TS(T)