Network Algorithms (Lecture, WS 2017/18)
The goal of this lecture is to provide the students with tools and techniques to reason about efficient network algorithms. The lecture is problem-oriented and structured into different fundamental principles, such as Randomization, Decentralization, Indirection, etc. Each lecture will cover a different basic problem (such as Load Balancing, Medium Access, Symmetry Breaking, etc.) and will be self-contained.
- First lecture: Wednesday October 18th, 2017, 2:00 - 4:00 p.m., room MAR 4.064
- Please hand in the solutions for exercise sheet 1 either
on ISIS before 2:00 p.m. Wednesday or right before the lecture in
person to Georgios .
For any open questions regarding ISIS, the worksheets or the tutorials, you can contact Damien Foucard .
persons:||Damien Foucard  (contact, tutorial
type:||Lecture with tutorial
Compulsory elective module in the programs Master Computer Science (focus: Communication Systems (KS), Master Computer Engineering (focus: Technical Applications) Master Computer Engineering (StO/PO 2012): Studienschwerpunkt Netze (Networks; Elektrotechnik, Technische Informatik oder Informatik).
|Modules:||Lecture plus tutorial are the
|Course ID:||0432 L
students, and Diplom
|Exam:||There is a written exam. In order
to register for the exam the sutdens must obtain at least 50% of the
points for exercises and/or programming
Exemplary list of topics addressed in this lecture:
- Models for networks and distributed systems
- Robust and efficient network design: self-stabilization and self-optimization
- Decentralization: Why and how? And complexity measures
- Randomization: Why and how? Basic tools
- Algorithms: Local algorithms, random algorithms, online algorithms, dynamic programming
- Network Algorithms for leader election, coloring, maximal independent sets, Medium Access
- Resource Allocation and embedding (e.g., energy, bandwidth, CPU)
- Flow & congestion control, routing
- Social networks: An algorithmic perspective
If you are interested in attending, please make sure you are subscribed to the corresponding ISIS Web site to receive information and announcements.
The details for registering for the exam are to be announced and will be given in the lecture and the tutorials as well.
David Peleg: Distributed Computing – A Locality-Sensitive Approach, SIAM 2000.
- Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, MIT press, 2009
- Hagit Attiya and Jennifer Welch,
Distributed Computing Fundamentals, Simulations,
and Advanced Topics, John Wiley and Sons,
- Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, Morgan Kaufmann, 2012
Lehre / Teaching, WiSe 17/18
- Network Protocols and Architectures (VL+UE) 
- Introduction to Programming (Einführung in die Programmierung, VL+UE) 
- NA: Internet Routing (SE) 
- Wirelesslab (PR) 
- Network Algorithms (VL+UE) 
Integrierte LV (VL mit UE)
Lecturer: Georgios Smaragdakis
14.10.2013 to 15.02.2014
We 14:00 - 16:00 o'clock
Th 14:00 - 16:00 o'clock
Location: MAR 4.064