Course Contents


PART I - Multiprocessor Algorithms

  • Introduction - Synchronization
    • Difficulties encountered in achieving parallelism
    • Amdhal's law
    • Modeling a shared memory system
    • Fundamental properties and parameters
  • Mutual Exclusion & Locks
    • Basic mutual exclusion algorithms
    • Practice: Spin Locks and Contention
    • Combining Techniques
    • Hierarchical Approaches
  • Atomic Objects
    • Linearizability
    • Blocking and non-blocking progress conditions
  • Concurrent Data Structures
    • Concurrent Queues, Stacks, Lists
    • Concurrent Hash Tables
    • Concurrent Trees
    • Garbage Collection, Safe memory reclamation
  • Barriers
    • Applications
    • Barrier Implementations


PART II - Algorithms for Message-Passing Systems

  • Introduction, Basic Network Algorithms
    • Modeling a message-passing system
    • Broadcast, convergecast and other collective communication algorithms
    • Basic distributed graph algorithms
  • Leader Election
    • Leader election in rings
    • Leader election in general graphs
  • Network Resource Allocation
    • Mutual exclusion algorithms
    • General resource allocation
  • Logical Time and global states
    • Adding logical time to distributed algorithms
    • Consistent global snapshots
  • Detection of properties on Distributed Executions
    • Termination detection
    • Deadlock detection
    • Failure detection




Attendance

Attendance is not mandatory, but strongly recommended. In addition, students that attend the lectures will have a bonus in their final grade.