Hlavná stránka
Cvičenia
Skúška
Rasťo Královič

Vitajte na stránke predmetu Úvod do distribuovaných algoritmov. Kurz je úvodom do návrhu protokolov a distribuovaných algoritmov. Zahŕňa základné komunikačné protokoly, fundamentálne distribuované algoritmy a algoritmy odolné voči chybám. .

Sylabus prednášok

Materiály uvedené v sylaboch sú chránené uatorskými právami príslušných vydavateľov. Sú tu prístupné iba pre účely tejto prednášky.

  1. Modely distribuovaných výpočtov:
    prechodové systémy a ich vlastnosti, distribuované algoritmy, varianty modelu, miery zložitosti.
    Materiál: G. Tel: Introduction to distributed algorithms, ( Chapter 2: Model ), Cambridge University Press, 1994,2000 (png)
  2. Voľba šéfa na kruhoch I:
    Problém distribuovaného výberu (voľba šéfa) vyžaduje prejsť z konfigurácie, kde sú všetky procesory v stave začiatok do konfigurácie, kde práve jeden procesor je v stave šéf a ostatné v stave nešéf.
    • Algoritmus LeLann'79: každý procesor pošle správu so svojím ID okolo celého kruhu, t.j. všetky procesy vedia všetky ID. Proces s najmenším ID sa vyhlási za šéfa. O(n2) správ.
    • Algoritmus Chang, Roberts'79: jednosmerný kruh, 0.69nlogn správ v priemernom prípade
      Materiál: Ernest Chang, Rosemary Roberts: An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of Processes, Communications of the ACM, 22(5), 1979, pp. 281-283 (pdf)
    • Algoritmus Hirschberg, Sinclair'80: dvojsmerný kruh, 8nlogn správ v najhoršom prípade
      Materiál: D.S. Hirschberg, J.B. Sinclair: Decentralized Extrema-Finding in Circular Configurations of Processors, Communications of the ACM, 23(11), 1980, pp. 627-628 (pdf)
    • Algoritmy Franklin'82 a Dolev, Klawe, Rodeh'82: dvoj- (resp. jednosmerný) kruh, 2nlogn správ v najhoršom prípade
      Materiál: G. Branscombe et al: Introduction to Distributed Computing - Lecture Notes (pdf)
    • Algoritmus Peterson'82: jednosmerný kruh, 1.44nlogn správ v najhoršom prípade
      Materiál: Gary L. Peterson: an O(n log n) Unidirectional Algorithm for the Circular Extrema Problem, ACM Transactions on Programming Languages and Systems, 4(4), October 1982, pp. 658-762 (pdf)
      Materiál: G. Branscombe et al: Introduction to Distributed Computing - Lecture Notes (pdf)
  3. Voľba šéfa na kruhoch II:
  4. Voľba šéfa na synchrónnych kruhoch
    • Dolný odhad v tvare Omega(nlogn) pre algoritmy založené na porovnaniach
    • Lineárne algoritmy nezaložené na porovnaniach
      Algoritmus Frederickson, Lynch'87 využívajúci správy s rôznymi "rýchlosťami".
      Iný prístup: fáza i testuje, či v kruhu existuje proces s ID najviac f(i): každý proces s ID najviac f(i) pošle na začiatku fázy ping. Ak je nasledujúcich n tikov ticho, znamená to, že všetky procesory majú väčšie ID. Ak existuje viac procesorov s ID najviac f(i), každý dostane ping za ostro menej ako n tikov. Ak je taký procesor práve jeden, príde mu ping za práve n tikov a vie, že je šéf.
    Materiál: Greg N. Frederickson, Nancy A. Lynch: Electing a Leader in a Synchronous Ring JACM, 34(1), 1987, pp. 98-115 (pdf)
  5. Voľba šéfa na úplných grafoch
    Optimálne algoritmy a dolné odhady pre úplné grafy bez zmyslu pre orientáciu. Lineárne algoritmy a ich čas pri zmysle pre orientáciu.
    • Alogritmy
      Materiál: poznámky v slovenčine(pdf)
      Materiál: G. Singh: Leader election in complete networks Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, October 1992, pp. 179-190 (pdf)
    • Dolný odhad v tvare Omega(nlogn)
      Materiál: E. Korach, S. Moran, S. Zaks: Tight Lower and Upper Bounds for Some Distributed Algorithms for a Complete Network of Processors Proceedings of the third annual ACM symposium on Principles of distributed computing, August 1984, pp. 199-207 (pdf)
  6. Prehľadávani grafov
    Prehľadávanie začína v stave, keď jeden uzol je označený ako iniciátor a všetky ostatné sú v identickom stave. Cieľom je, aby bol každý vrchol v priebehu výpočtu informovaný (t.j. dostal aspoň jednu správu).
    Prehľadávací algoritmus, v ktorom je v každom momente v sieti iba jedna správa (t.j. každý uzol v priebehu výpočtu posiela správu iba ako odpoveď na práve prijatú správu) sa nazýva traverzovací algoritmus.
    • Algoritmus shout-echo
      Iniciátor pošle všetkým svojim susedom správu SHOUT. Ak správa SHOUT dorazí do nenavštíveného uzla, označí ho ako navštívený a hranu, po ktorej prišla ako použitú. Potom pošle SHOUT po všetkých neoznačených hranách a čaká, kým z každej nepríde ECHO. Nakoniec vráti ECHO po hrane, po ktorej pôvodne prišla. Ak príde SHOUT do navštíveného vrchola, okamžite sa vráti ECHO.
    • prehľadávanie do šírky:
      Okrem prehľadania grafu trba vyrobiť BFS kostru.
      • algoritmus Cheung'83 s kubickou komunikáciou a lineárnym časom
        Každá správa obsahuje počítadlo hopov. Na začiatku iniciátor pošle všetkým svojim susedom správu 1. Každý vrchol má lokálnu premennú (inicializovanú na nekonečno), v ktorej si uchováva vzdialenosť od iniciátora. Keď dostane správu i a jeho doterajšia vzdialenosť je väčšia, nastaví si svoju vzdialenosť na i a pošle správu i+1 svojim susedom.
      • algoritmusCheung,Zhu'87 s kvadratickou komunikáciou aj časom
        Podobne ako predchádzajúci, ale kostra sa vytvára po vrstvách. V každej fáze iniciátor pošle po už vybudovanej časti kostry správu. Aktuálne listy pošlú správu do vzdialenosti 1, čím vyrobia novú vrstvu. Kvôli synchronizácii sa pošlú potvrdenia k iniciátorovi.
      • kombinovaný algoritmus
        Pre parameter k vytvára naraz k vrstiev.
    • prehľadávanie do hĺbky:
      • traverzovací algoritmus so zložitosťou 2m
      • algoritmus Awerbuch'85
        Materiál: B. Awerbuch: Complexity of network synchronization Journal of the ACM (JACM), Volume 32 Issue 4, October 1985 , pp. 804-823 (pdf)
      • algoritmus Cidon'88
      Materiál: G. Tel: Introduction to distributed algorithms, ( Section 6.3, 6.4: Traversal, DFS ), Cambridge University Press, 1994,2000 ()
  7. Minimálna kostra
     Zhrnutie algoritmov GHS a KKM sa dá nájsť aj v G. Tel: Introduction to distributed algorithms, ( Chapter 7 : Election Algorithms ), Cambridge University Press, 1994,2000 ()
  8. Routovanie s tabuľkami
     Materiál: G. Tel: Introduction to distributed algorithms, ( Chapter 4 : Routing ), Cambridge University Press, 1994,2000 ()
  9. Kompaktné routovanie
     Materiál: G. Tel: Introduction to distributed algorithms, ( Chapter 4 : Routing ), Cambridge University Press, 1994,2000 ()
  10. Routovanie paketov
  11. Dohoda v distribuovaných systémoch
    Neexistencia deterministického algoritmu dohody pri chybách liniek, randomizovaný algoritmus, stop-chyby procesorov, byzantínske chyby
    Materiál: Nancy A. Lynch : Distributed Algorithms, (Chapter 5,6), Morgan Kaufmann 1997 ()

šie materiály