Advanced Distributed Algorithms and Data Structures
Instructor: Prof. Dr. Christian Scheideler
- 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: Mon, 13:15 - 15:45, via BBB
The lectures will be recorded.
- Tutorials: Wed, 11:15 - 12:45, via BBB (start in the second week)
The tutorials will not be recorded.
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 23-26
- March 29 - 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.
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:
Graph Theory, Probability Theory, Process Model
- Access Control
Basic Link Primitives, Relays, Applications
Physical Clocks, Logical Clocks, Hybrid Clocks, Applications
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
Arrow Protocol, Diffraction Trees, Applications
The slides of the chapters can be found in PANDA.
Exercise sheets will be posted in PANDA every Monday after the lecture.
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.