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:
- työsuunnitelma (lähdeluettelo ja muutaman virkkeen sisältöhahmotelma) pe 21.9. klo 16 mennessä
- kirjoitelman luonnos (ainakin 5 sivua valmista tekstiä, loput hahmoteltu esim. ranskalaisin viivoin) pe 12.10. klo 16 mennessä
- valmis kirjoitelma ma 29.10. klo 10 mennessä
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. | Kivinen | jä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ä
- Chen, Welch: Self-stabilizing dynamic mutual exclusion for mobile ad hoc networks J. Par. Distr. Comput. 2005.
- Johnen, Nguyen: Robust Self-stabilizing Clustering Algorithm. OPODIS 2006.
- Afek, Bremler: Self-stabilizing unidirectional network algorithms by power supply. Chicago Journal of Theoretical Computer Science 1998(3).
- Antonoiu, Srimani: Distributed self-stabilizing algorithm for minimum spanning tree construction. Euro-par 1997.
- Bein, Datta, Larmore: On Self-stabilizing Search Trees. DISC 2006.
- Chlebus, Kowalski: Time and Communication Efficient Consensus for Crash Failures. DISC 2006.
- Dijkstra: Self-stabilizing systems in spite of distributed control. Comm. ACM 1974.
- Dolev, Tzachar: Self-stabilizing and self-organizing distributed algorithms. OPODIS 2006.
- Drabkin, Friedman, Gradinariu: Self-stabilizing wireless connected overlays. OPODIS 2006.
- Fischer, Jiang: Self-stabilizing leader election in networks of finite-state anonymous agents. OPODIS 2006.
Jyrki Kivinen