Helsingin yliopisto Tietojenkäsittelytieteen laitos
 

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta:

 

58307301 Seminaari: Hajautetut algoritmit (3 op, 2 ov)

Seminaari on päättynyt ja tulokset saatavilla.

Seminaari syksyllä 2007
Kokoontumiset perjantaisin 10-12 salissa C221

Vastuuhenkilö Jyrki Kivinen; myös Timo Karvi osallistuu järjestelyihin

Sisältö

Seminaarissa keskitytään hajautetuissa järjestelmissä tärkeään vikasietoisuuteen (fault-tolerance) ja erityisesti ongelmista toipumiseen (self-stabilization). Tavoitteena on esitellä hajautettuja algoritmeja, jotka toipuvat erilaisista tiedonsiirto- ja laiteongelmista. Tyyppiesimerkkejä tällaisista algoritmeista ovat keskinäinen poissulkeminen, hajautettu virittävän puun muodostaminen, kellojen synkronointi ja johtajan valinta renkaassa.

Esitietovaatimukset

Tieteellinen kirjoittaminen. Lisäksi osanottajilta edellytetään algoritmisen ajattelun ja analyysin hallintaa.

Seminaarin muodot

Kukin osallistuja pitää yhden esitelmän, laatii kirjoitelman sekä osallistuu keskusteluun muiden esitelmien pohjalta. Arvosanasta 50% määräytyy kirjoitelmasta, 40% esitelmästä ja 10% muusta aktiivisuudesta.

Periodilla I ei ole esitelmiä, (poikkeus:12.10.), vaan kaikki keskittyvät aiheeseen perehtymiseen ja kirjoitelman laatimiseen. Valmiissa kirjoitelmassa tulisi olla noin 10-15 tekstisivua (poislukien kansilehti, viiteluettelo yms.) laitoksen opinnäytetyön formaatissa. Kaikkien osallistujien on palautettava kirjoitelma periodin II alkuun mennessä.

Periodilla II pidetään kaksi esitelmää kokoontumiskertaa kohti. Yhden esitelmän pituuden pitäisi siis olla noin 45 minuuttia, mistä 5 minuuttia on syytä varata keskusteluun.

Seminaariesitelmän kuulijoiden oletetaan tutustuvan etukäteen esitelmään liittyvään kirjoitelmaan. Seminaaritilaisuudessa jokainen kuulija saa täytettäväkseen arvostelulomakkeen, jolla arvioidaan lyhyesti sekä kirjallinen että suullinen esitys. Arvostelijan nimellä varustetut lomakkeet jäävät seminaarin vetäjälle, mutta esitelmänpitäjä saa anonymisoidut kopiot palautteeksi itselleen.

Kirjallisten töiden määräajat

Seuraavat kirjalliset tuotokset on toimitettava Jyrki Kiviselle sähköpostitse PDF-muodossa:

  1. työsuunnitelma (lähdeluettelo ja muutaman virkkeen sisältöhahmotelma) pe 21.9. klo 16 mennessä
  2. kirjoitelman luonnos (ainakin 5 sivua valmista tekstiä, loput hahmoteltu esim. ranskalaisin viivoin) pe 12.10. klo 16 mennessä
  3. valmis kirjoitelma ma 29.10. klo 10 mennessä
Määräaikoihin 1 ja 2 voi saada lykkäystä perustellusta syystä. Lopullisen kirjoitelman määräaikaan ei saa lykkäystä.

Kokoontumisten aikataulu

Sivunumerot lähdeluettelossa viittaavat kirjaan

Shlomi Dolev: Self-Stabilization. MIT Press 2000.
Seuraava aiheluettelo ja aikataulu sovittiin seminaarin toisella kokoontumiskerralla:

aika esittäjä kirjoitelma / muuta alkuperäislähde
7.9.Kivinenjärjestyminen, johdanto
14.9.- aiheiden jakaminen, aiheisiin perehtyminen
21.9.- ei kokoontumista; työsuunnitelman palautus
28.9.- ei kokoontumista
5.10.- ei kokoontumista
12.10.Suomela (kalvot) Itsestabilointi: perusmääritelmiä ja klassisia tuloksia Dolev pp. 1-55
12.10.Räsänen (kalvot) Jaetun muistin muuntaminen viestinvälitykseksi Dolev pp. 73-86
12.10.-luonnoksen palautus
19.10.-tenttiviikko (ei kokoontumista)
26.10.- väliviikko (ei kokoontumista)
2.11.Elovaara (kalvot) Itsevakautuva järjestäytyminen ja päivittäminen Dolev pp. 86-98
2.11.Ajoviita (kalvot) Stabiloivat synkronoijat ja nimeäminen Dolev pp. 98-119
9.11.Hassinen (kalvot) Stabilointi Dolev pp. 121-133
9.11.Brunberg (kalvot) Hajautetun laskennan vakaantuminen häiriöiden kestäessä Dolev pp. 135-156
16.11.Koponen (kalvot) Itsestabiloivat algoritmit: paikallinen stabilointi Dolev pp. 159-172
16.11.Pervilä (kalvot) Kellojen synkronointi itsestabiloituvasti Dolev, Welch: Self-stabilizing clock synchronization in the presence of Byzantine faults. J. Assoc. Comput. Mach. 2004.
23.11.Luosto (kalvot) Yleinen vakautuva paikallinen synkronointialgoritmi Boulinier, Petit, Villain: When graph theory helps self-stabilization. PODC 2004.
23.11. (ei toista esitystä)
30.11.Siren (kalvot) Itsestabiloituva johtajan valinta vakiotilassa Beauquier, Gradinariu, Johnen: Memory space requirements for self-stabilizing leader election protocols. PODC 1999.
30.11.Välimäki (kalvot) Konsensusongelma hajautetuissa järjestelmissä Lynch: Distributed Algorithms, ch. 5
7.12.Tani Bysanttilaiset kenraalit Lynch: Distributed Algorithms, ch. 6
7.12.Virkkala (kalvot) Itsestabiloiva bysanttilainen yhteisymmärrys Daliot, Dolev: Self-stabilizing byzantine agreement. PODC 2006.

Muita lähteitä


Jyrki Kivinen