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
|