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.

 

Prerequisites:

CS 211: Theory of Computation and Complexity

CS 231: Data Structures and Algorithms