Page Content
to Navigation
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.
News
- 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.
Overview
| Lecturers: | Georgios Smaragdakis |
| Contact persons: | Damien Foucard (contact, tutorial management) |
| Event type: | Lecture with tutorial (VL+UE) |
| Area: | 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 Module MINF-KT-NA.W12. |
| SWS: | 4 |
| LP (ECTS): | 6 |
| Time: | Wednesday, 2pm–4pm weekly |
| First Meeting: | Lecture: 18.10.2017 |
| Room: | MAR 4.064 |
| Tutorial: | Thursday, 2pm–4pm weekly |
| Course ID: | 0432 L 815 |
| Audience: | master students, and Diplom students |
| Prerequisites: |
|
| 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 assignments. |
| Further Information: | s. ISIS |
Topics
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
ISIS
If you are interested in attending, please make sure you are subscribed to the corresponding ISIS Web site to receive information and announcements.
Exam
The details for registering for the exam are to be announced and will be given in the lecture and the tutorials as well.
General References
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, Inc. 2005
- Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, Morgan Kaufmann, 2012