1. komponenta

Lecture type	Total
Lectures	30
Exercises	15

* Load is given in academic hour (1 academic hour = 45 minutes)

COURSE AIMS AND OBJECTIVES:
Enable students to:
- recognize basic problems associated with distributed computing
- design distributed algorithms that solve the basic problems mentioned
- use at least one programming language or tool for development of distributed applications
- create a distributed application.

COURSE DESCRIPTION AND SYLLABUS:
1. Introduction. Parallel and distributed systems. Programs, processes, and threads. The Java programming language. Threads in Java.
2. Distributed programming. IP addresses and host names. Sockets based on the UDP protocol. Using datagrams. Sockets based on the TCP protocol. A simple name server. Linking a given set of processes with each other.
3. Models and clocks. Model of a distributed system. Models of distributed computation. Simple logical clocks. Vector clocks. Direct-dependency clocks. Matrix clocks.
4. Mutual exclusion. Specification of the problem. Centralized algorithm. Lamport's algorithm. Ricart and Agrawala's algorithm. Token-based algorithms.
5. Global snapshot. Global snapshot versus models of computation. Chandy and Lamport's algorithm. Channel recording by the sender. Case study - snapshot of a circulating token.
6. Detecting termination. Diffusing computation and its termination. Case study - finding shortest paths in a network. Dijkstra and Scholten's algorithm. Token-based algorithm.
7. Message ordering. Ordering relations. Algorithm for causal ordering. Case study - chat. Algorithm for synchronous ordering.
8. Leader election and related problems. Leader election on a ring. Leader election on a general network. Spanning tree construction. Computing global functions.
9. Synchronization. Synchronous and asynchronous networks. A simple synchronizer. Case study - BFS tree construction. Synchronizers alpha and beta.
10. Agreement. Consensus in an asynchronous network under crash failures. Consensus in a synchronous network under crash failures. Consensus in a synchronous network under Byzantine faults.

1. Distribuirani procesi - nastavni materijali, http://web.studenti.math.pmf.unizg.hr/~manger/dp/, R. Manger.
2. Distributed Algorithms: An Intuitive Approach, Fakkink W., The MIT Press, 2013.
3. Distributed Computing: Principles, Algorithms and Systems, Kshemkalyani A.D., Singal M., Cambridge University Press, 2011.
4. Distributed Algorithms for Message-Passing Systems, Raynal M., Springer, Berlin Heidelberg, 2013.
5. Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach, Raynal M., Springer, Berlin Heidelberg, 2018.
6. Concurrent and Distributed Computing, Garg V.K., Wiley - IEEE Press, New Jersey, 2004.

Izborni modul A - Softversko inženjerstvo - Regular study - Computer Science and Mathematics
Izborni modul B - Teorijsko računarstvo - Regular study - Computer Science and Mathematics
Ostali izborni predmeti - Regular study - Computer Science and Mathematics

Izborni modul A - Softversko inženjerstvo - Regular study - Computer Science and Mathematics
Izborni modul B - Teorijsko računarstvo - Regular study - Computer Science and Mathematics
Ostali izborni predmeti - Regular study - Computer Science and Mathematics