Distribuirani procesi
Važne obavijesti
- Objavljene su teme za projekte. Nalaze se u rubrici "Projekti, kolokviji, ...".
Studenti se trebaju udružiti u timove te trebaju javiti nastavniku koju temu žele raditi.
Kod dodjele tema prednost imaju oni koji su se ranije javili.
- Kao priprema za prvi kolokvij, objavljeni su zadatci s prošlogodišnjeg i pretprošlogodišnjeg prvog kolokvija.
Također se nalaze u rubrici "Projekti, kolokviji, ...".
Osnovni podaci o kolegiju
- Predaje se na drugoj godini diplomskog studija Računarstvo i matematika.
- Predaje se jedan semestar (ljetni).
- Satnica: 2 sata predavanja i 1 sat vježbi tjedno.
- ECTS bodovi: 5.
Ciljevi kolegija
- Upoznavanje s temeljnim problemima vezanim uz rad distribuiranih procesa.
- Proučavanje distribuiranih algoritama koji rješavaju navedene temeljne probleme.
- Stjecanje vještine korištenja barem jednog alata za razvoj distribuiranih programa.
- Izrada vlastitog distribuiranog programa.
Svrha kolegija
- Ovaj predmet potreban je zato jer je on sastavni dio obrazovanja svakog softverskog inženjera.
- Naime, zbog globalne umreženosti svih vrsta računala, od današnjeg softverskog inženjera
očekuje se da razvija distribuirane aplikacije.
- Predmet je koristan zato jer softverskog inženjera osposobljava da pri razvoju distribuiranih
aplikacija koristi provjerena rješenja.
Sadržaj predavanja
- Uvod. Paralelni i distribuirani sustavi. Programi, procesi i dretve.
Programski jezik Java. Podrška za dretve u Javi.
- Distribuirano programiranje. IP adrese i imena računala.
Utičnice zasnovane na UDP protokolu. Primjer slanja i primanja datagrama.
Utičnice zasnovane na TCP protokolu.
Primjer jednostavnog poslužitelja imena.Primjer povezivanja skupa procesa.
- Modeli i satovi. Model distribuiranog sustava. Modeli distribuiranog
računanja. Jednostavni logički satovi. Vektorski satovi. Satovi neposredne ovisnosti.
Matrični satovi.
- Međusobno isključivanje. Specifikacija problema. Centralizirani algoritam.
Lamportov algoritam. Algoritam Ricarta i Agrawale. Algoritam sa žetonom koji kruži.
- Globalna snimka. Globalna snimka i modeli računanja. Algoritam Chandya i
Lamporta. Snimanje kanala na strani pošiljatelja. Studijski primjer – snimka žetona
koji kruži.
- Otkrivanje završetka rada. Difuzijsko računanje i njegov završetak.
Studijski primjer - traženje najkraćeg puta u mreži. Algoritam Dijkstre i
Scholtena. Algoritam zasnovan na žetonu.
- Uređivanje redoslijeda poruka. Uređajne relacije za poruke. Algoritam
za osiguravanje kauzalnog uređaja. Studijski primjer - chat. Algoritam za
osiguravanje sinkronog uređaja.
- Izbor vođe i još ponešto. Izbor vođe u prstenu. Izbor vođe u općenitoj
mreži. Konstrukcija razapinjućeg stabla. Računanje globalne funkcije.
- Sinkronizacija. Općenito o sinkronizaciji. Jednostavni sinkronizator.
Studijski primjer – konstrukcija BFS stabla. Sinkronizatori α i β.
- Usuglašavanje. Konsenzus u asinkronoj mreži, uz mogućnost prestanka
rada procesa. Konsenzus u sinkronoj mreži, uz mogućnost prestanka rada procesa.
Konsenzus u sinkronoj mreži, u uvjetima “bizantinskih” grešaka.
Sadržaj vježbi
- Studenti se udružuju u timove od dva do tri člana.
- Svaki tim bira jedan od ponuđenih projektnih zadataka te radi na njemu.
- Rezultati rada na projektnom zadatku su: referat u pismenom obliku,
softversko rješenje, prezentacija na seminaru.
Literatura
- Garg V.K., Concurrent and Distributed Computing in Java. Wiley – IEEE Press,
Hoboken NY, 2004.
- Fokkink W., Distributed Algorithms: An Intuitive Approach. Second Edition.
The MIT Press, Cambridge MA, 2018.
- Kshemkalyani A.D., Singal M., Distributed Computing: Principles, Algorithms and
Systems. Cambridge University Press, Cambridge, 2011.
- Raynal M., Distributed Algorithms for Message-Passing Systems. Springer,
Berlin Heidelberg, 2013.
- Raynal M., Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic
Approach. Springer, Berlin Heidelberg, 2018.
- Garg V.K., Elements of Distributed Computing. Wiley – IEEE Press, New York NY,
2008.
- Tel G., Introduction to Distributed Algorithms. Second Edition. Cambridge
University Press, Cambridge, 2008.
- Lynch N.A., Distributed Algorithms. Morgan Kaufmann, San Francisco CA, 1997.
- Attiya H., Welch J., Distributed Computing: Fundamentals, Simulations, and
Advanced Topics. Second Edition. Wiley-Interscience, New York NY, 2004.
- Van Steen M., Tannenbaum A.S., Distributed Systems: Principles and Paradigms.
Third Edition. CreateSpace Independent Publishing Platform, North Charleston
SC, 2017.
- Pattamsetti R.M.R. Distributed Computing in Java 9: Leverage the Latest
Features of Java 9 for Distributed Computing. Packt Publishing, Birmingham UK,
2017.
- Ghosh S. Distributed Systems: An Algorithmic Approach. Second Edition. Chapman
and Hall/CRC, Boca Raton FL, 2020.
- Ghosh R.K., Ghosh H., Distributed Systems: Theory and Applications. IEEE Press,
Piscataway NJ, 2023.
- Sigs F. Distributed Algorithms: A Verbose Tour. Independently published, 2019.
- Santoro N. Design and Analysis of Distributed Algorithms. Wiley-Interscience,
New York, 2006.
- Burns B., Designing Distributed Systems. O’Reilly Media, 2018.
- Liu M.L., Distributed Computing: Principles and Applications. Pearson, 2019.
- Wattenhofer R., Mastering Distributed Algorithms. Independently published, 2020.
Obveze studenata, pravila ocjenjivanja
- Obveze su: sudjelovanje u nastavi, rad na projektnom zadatku, polaganje
kolokvija i ispita.
- Pravila ocjenjivanja detaljno su opisana u sljedećem dokumentu
(pdf) .
Nastavni materijali
- Skripta: R. Manger, "Distribuirani procesi"
(pdf) ,
- Web sjedište autora
Vijay K. Garg-a .
- Programi u Javi od istog autora koji se koriste na predavanjima
(zip) .
- Alati za programiranje u Javi s pripadnom
dokumentacijom na stranicama tvrtke Oracle
(download) .
- Priručnici za Javu, također na stranicama tvrtke Oracle
(tutorials) .
Projekti, kolokviji, ispiti, rezultati
- Popis tema za projekte
(pdf) .
- Prvi kolokvij trebao bi se održati u petak 26.04.2024.
Evo nekoliko relevantnih zadataka za vježbu:
- prvi kolokvij iz 2023. godine
(pdf),
- prvi kolokvij iz 2022. godine
(pdf).
Nastavnici u akademskoj godini 2023/2024
- Predavanja i vježbe: Robert Manger. Konzultacije su utorkom 12-14 h u sobi 232.
Raspored sati u akademskoj godini 2023/2024
- Predavanja i vježbe: ponedjeljak 9-12 h, dvorana 110.