Course Number: CS 625

Course Name: Foundations of Distributed Computing

Course Coordinator: Antonio Nicolosi

Graduate or Undergraduate Equivalent:

 

Catalog Description: Design and analysis of distributed algorithms, and impossibility results showing when some problems are unsolvable. Models of synchronous and asynchronous distributed computing. Fault models, including crash failures and malicious failures, and communication models, including message passing and shared memory systems. Distributed algorithms and impossibility results for problems, such as consensus, Byzantine agreement, clock synchronization, mutual exclusion, and secure multiparty computation. Prerequisite: CS 600.

 

Course Outcomes

Each course outcome is followed in parentheses by the Program Outcome to which it relates.

1. Articulate relative advantages and drawbacks of the main types of formal models for a distributed system (synchronous vs. asynchronous timing model, shared memory vs. message passing interprocess communication mechanism). (core:concurrency)
   
2. Describe algorithms and/or impossibility results for typical abstract problems in distributed computing (consensus, communication, resource allocation, synchronization) in the different system settings. (core:concurrency)
   
3. Recognize the occurrence of (a variant of) one of the typical abstract problems in a practical setting, and apply the known solution or argue about its impossibility based on known results. (core:problem-solving)
   
4. Reason formally about the requirements of a distributed algorithm. (core:requirements)
   
5. Identify appropriate complexity measures and analyze solutions to a distributed computing problem accordingly. (core:problem-solving)