Theory of Communication in Parallel Systems (TCPS)


Prof. Dr. rer. nat. Rolf Wanka

Module Description

Theory of Communication in Parallel Systems

Teaching Hours per Week:

V2  |  5 ECTS

Target Audience:

Students of

  • Advanced Signal Processing and Communications Engineering (ASC),
  • Computer Science (Master level),
  • Other interested students (Mathematics, etc.)

Room and Hours:

Monday, 10:15 – 11:45 Uhr, Room E1.11

Important Dates

  • October 22, 2018: First Lecture


This course presents basic algorithmic methods and analysis tools for routing in computer networks

  • Offline routing on the double Butterfly network: Waksman approach and application of graph theoretic methods (matchings and Hall’s marriage theorem)
  • Randomized routing on the Butterfly network: Random rank protocol, congestion analysis, and Chernoff bounds
  • Deterministic online routing on Multibutterfly network: Expanders and the probabilistic method
  • The Butterfly network applied to Peer-to-Peer networks


  • TBA