Master Ma/WiMa/Finance/Wiwi

Type 

Optional

MATH, 4 Hours Course, 2 Hour Exercises (4+2)

A combination with OR-Praktikum is possible.

Please arrange a date with Dr. Maßberg if so.

• Every Monday, 10am-12pm in Room He22E18
• Every Thursday, 10am-12pm in Room He22E18

• Every Wednesday, 12pm-2pm in Room He22E18

In this modular master course, we will cover a handful of the nicest algorithms and techniques from the principles of distributed computing by looking at a different theme every class, including many graph and network related topics, such as vertex coloring, dominating set, maximal independent set, diameter and radius, small networks, sorting/counting in networks, searching and routing issues, but now from a distributed point of view instead of a sequential one traditional from optimization.

This master course is self-contained and does not need any class as prior requirement, though those who have already taken graph theory, optimization or game theory may find it particularly interesting. However, the model of computation differs from all those. Though it is distributed, each network graph node being a distinct participant in the algorithm, a solution does not involve an equilibrium such as in game theory, but rather achieves in a distributed manner a specific goal, such as optimizing a parameter or finding a sort of structure.

Due to the distributed computation, besides the time complexity, communication complexity issues such as message complexity will play a role. We will take a look at both deterministic and randomized algorithms, as well as at approximation algorithms for hard problems.

Information

• The exam is oral.
• There will be exercise classes every week, but no "Vorleistung" requirement to register for exam.
• There will be a total of 10 Exercise Sheets.
• Registration for an exam is allowed until 4 days before it takes place, according to university rules.
• The exams are the same for all master fields.

Exercises

• Pearls of Distributed Computing, Roger Wattenhofer (Chapters 1,2,3,4,7,19)
• "Searching for a Blackhole in Arbitrary Networks: Optimal Mobile Agents Protocols", Distributed Computing (2006) 19(1):1-18.
• "The South Zone: Distributed Algorithms for Alliances", (SSS 2011), Stabilization, Safety, and Security of Distributed Systems Lecture Notes in Computer Science Volume 6976, 2011, pp 178-192.
• "Self-Stabilizing Smoothing and Balancing Networks", Distributed Computing (2006) 18(5): 345-357 (Section 4: Periodic Counting Networks).
• (Note that you must be logged in the university internet system to retrieve article references.)
• Most classes will be closely linked to graph theory.
• Not all script chapters will be considered.
• Material will be given for classes not in the script.
• Further references may be found inside the script.