Network Algorithms (Vorlesung, WS 2017/18)

Diese Vorlesung vermittelt Techniken zum Entwurf und zur Analyse von effizienten Netzwerkalgorithmen. Solche Algorithmen bilden eine wichtige Grundlage vieler verteilter Systeme: von Multicore Computern über Internet Netzwerke bis hin zu Online Social Networks. Jede Lektion dieser Vorlesung wird sich mit einem in sich abgeschlossenen Problem (z.B. Load Balancing, Medium Access, Symmetry Breaking) und Thema (z.B. Randomisierung, Dezentralisierung,Dereferenzierung) befassen.

• Erste Vorlesung: Mittwoch 18.10.2017, 14:00 - 16:00 Uhr, Raum MAR 4.064
• Bitte gebt die Lösungen zum ersten Übungsblatt bis Mittwoch 14 Uhr entweder bei ISIS oder direkt vor der Vorlesung bei Georgios [1] ab.
  
  Für offene Fragen bzgl. ISIS, den Hausaufgaben oder dem Übungsbetrieb steht Damien Foucard [2] als Ansprechpartner bereit.

Übersicht möglicher Themen:

• 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

Falls du an unserer Vorlesung teilnehmen willst, trag dich bitte auf der zugehörigen ISIS-Webseite ein, um wichtige Informationen und Ankündigungen zu bekommen.

Die Vorlesungen und die Übungen werden auf Englisch gehalten.

Zum Bestehen der Übungen sind mind. 50% der maximal erreichbaren Punkte notwendig.

Details zur Prüfung werden noch bekannt gegeben und in Vorlesung und Übung angekündigt.

• 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