Ad­van­ced Dis­tri­bu­ted Al­go­rithms and Da­ta Struc­tu­res

Instructor: Prof. Dr. Christian Scheideler

Module Information:

  • 6 ECTS Credits
  • Focus Areas: Algorithm Design, Networks and Communication
  • Modelle und Algorithmen (MuA)

For those students that just need to take the 4 ECTS variant of the course: only the contents taught till the end of December will be relevant for the exam. Please inform the lecturer if you want to make use of this option.

Time and Location:

  • Lectures: Fri, 16:15 - 18:45, F1.110
  • Tutorials: Wed, 14:15 - 15:45, F2.211

Grading:

To be admitted to the exam, at least one solution has to be presented in a tutorial. The grade of the course will be determined by the grade of the oral exam. There are two time periods for the oral exams:

  • February 21-24
  • March 28 - April 1

If you fail in the first time period, you still have the chance for a second exam in the second time period. Please contact my secretary Marion Hucke for a time slot.

Contents:

The course will cover advanced topics in distributed algorithms and data structures, so it is highly advised that attendees have a solid algorithms and math background. Knowledge about distributed systems is not needed but helpful to follow the course. The course will consist of the following chapters:

  • Introduction
  • Foundations
    Graph Theory, Probability Theory, Process Model
  • Access Control
    Basic Link Primitives, Relays, Applications
  • Synchronization
    Physical Clocks, Logical Clocks, Hybrid Clocks, Applications
  • Consensus
    Classical Consensus, Eventual Consensus, Blockchains, Applications
  • Information Dissemination
    Amnesiac Flooding, Push Protocols, Flooding via Random Linear Codes, Applications
  • Hybrid Networks
    Well-formed Trees, MST and Shortest Paths, Applications
  • Scheduling
    Arrow Protocol, Diffraction Trees, Applications

The slides of the chapters can be found in PANDA.

Homework Assignments:

Exercise sheets will be posted in PANDA every Friday after the lecture.

Literature:

The lecture will be based on research papers that are cited in the slides. Unfortunately, most of the topics cannot be found in books yet.