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.