# Advanced Distributed Algorithms and Data Structures

**Lecturer:** Prof. Dr. Christian Scheideler

**Module Information:**

- Modules III.2.1, III.2.2, and III.2.4
- 4 ECTS

**Time and Location:**

- Lecture: Thu, 2-4 pm, F2.211
- Tutorial: Thu, 10-11 am, F2.211 (starts 3rd week)

**Contents**

The course will give an introduction into advanced concepts in the area of distributed algorithms and data structures, ranging from access control and synchronization to overlay networks and various applications.

**Grading**

The grade will be determined as follows:

- 50%: oral exam
- 50%: software project

Both parts must be passed in order to pass the course. The deadline for the presentation of the software project is **April 28**.

**Lecture Notes**

- Chapter 1: Introduction
- Chapter 2: Graph Theory
- Chapter 3: Probability Theory
- Chapter 4: Link Primitives
- Chapter 5: TCM Model and Programming Environment
- Chapter 6: Contention Resolution
- Chapter 7: Clock Synchronization
- Chapter 8: Logical Clocks
- Chapter 9: Dynamic Overlay Networks
- Chapter 10: Communication Primitives
- Chapter 11: Applications

**Homework Assignments**

- Homework 1 (due Nov 3)
- Homework 2 (due Nov 10)
- Homework 3 (due Nov 17)
- Homework 4: get familiar with C++ (due Nov 24)
- Homework 5 (due Dec 1)
- Homework 6 (due Dec 8)
- Homework 7 (due Dec 15)
- Homework 8 (due Dec 22)
- Homework 9 (due Jan 12): Implement and test the corrected Build-List protocol in Chapter 5.
- Homework 10 (due Jan 19)
- Homework 11 (due Jan 26)
- Homework 12 (due Feb 2)

**Programming Environment**

- A survey of the programming environment can be found here.
- The virtual machine for the implementations can be downloaded here.
- The script for installing the environment under Ubuntu can be found here.

If there are any questions, please contact Thorsten Götte.

**Literature**

The lecture will be based on state-of-the-art research, so there is no bock available for the lecture. However, the slides will contain references to the research papers they are based on.