Credit points:  3

Prerequisites: Design and Analysis of Algorithms, or equivalent.

 

Text: Peleg, Distributed Computing: A Locality-Sensitive Approach

Description: This course studies algorithms that are run on a system of processors connected by communication links. The main questions guiding the course are the influence of locality and communication on the complexity and solvability of various tasks. The material is explored from the theoretical perspective.

Topics.

• Leader election

• Independent sets, matchings and coloring

• Spanning trees

• Logical time

• Clock synchronization

• Datalink protocols

• Sparse partitions

• Self stabilization