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:

Thursday, 16:15 – 17:45 Uhr, Room 01.019 (Cauerstr. 7, formerly E1.11)

Important Dates

  • October 17, 2019: 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