Formal models of distributed
computing: shared memory versus message passing, determinism versus
randomization, concepts of synchronism, asynchrony and real-time. Design
and analysis of distributed algorithms and impossibility/improbability
results for fundamental problems such as mutual exclusion, consensus,
synchronization, leader election, construction of minimum spanning trees.
Fault tolerance: Byzantine generals, wait-free algorithms, fault degrees.
Formal methods for proving correctness of distributed algorithms. Advanced
topics. Special emphasis throughout the course on lower and upper bounds
on time and memory.
CS 211: Theory of Computation and Complexity
CS 231: Data Structures and Algorithms