| Weeks | Topics |
| 1 |
Distributed system definition, distributed application example, message transmission models, shared memory models.
|
| 2 |
Finite state machines, threads, thread types, semaphore examples.
|
| 3 |
Graph theory, fundamental graph algorithms: BFS algorithm, DFS algorithm, connectivity, topological sorting.
|
| 4 |
Vertex and tree coloring algorithms, distributed vertex and tree coloring algorithms, distributed spanning tree algorithms: broadcast and convergecast algorithms
|
| 5 |
BFS tree construction, flooding, serial and distributed MST algorithms, cycle and cut concepts.
|
| 6 |
Distributed time synchronization, Berkeley time synchronization protocol, logical clocks , Lamport’s logical clock algorithm, vector clocks, matrix clocks
|
| 7 |
Resource sharing, critical section problem, hardware synchronization, semaphores.
|
| 8 |
Midterm
|
| 9 |
Mutual Exclusion Algorithms: Lamport’s algorithm, Ricart-Agrawala’s algorithm, Suzuki-Kasami’s algorithm, Raymond’s algorithm, Maekawa’s algorithm.
|
| 10 |
Global states of distributed systems, Chandy Lamport’s algorithm, Lai Yang’ın algorithm, snapshot.
|
| 11 |
Deadlocks and termination detection, Dijkstra-Scholten algorithm, distributed deadlock, Chandy Misra Haas deadlock prevention algorithm.
|
| 12 |
Leader election algorithms: Bully algorithm, LeLann algorithm, Chang Roberts algorithm, Synchronizers.
|
| 13 |
Consensus protocols, byzantine generals problems, consensus.
|
| 14 |
Self-stabilization. Project Presentations. Final Exam
|