Ad­vanced Dis­trib­uted Al­gorithms and Data Struc­tures

Lecturer: Prof. Dr. Christian Scheideler

Module Information:

  • 6 ECTS
  • Focus Areas: Algorithm Design, Networks and Communication

Time and Location:

  • Lecture: Mon, 11:00-14:00, F0.530
  • Tutorial: Mon, 9:00-11:00, F0.530 (starts 2nd week)

Contents

The course will give an introduction into advanced concepts in the area of distributed algorithms and data structures, ranging from strategies for network management to strategies for information management, scheduling und optimization.

Grading

Prerequisites to pass the course are:

  • presentation of solution to homework problem in tutorial,
  • passing a software project at the end of the course (can be done with up to 4 people), and
  • passing the oral exam.

The grade of the course will be determined by the software project (40%) and the oral exam (60%).

Two weeks have been reserved for the oral exams: July 22-26 and September 23-27. Please ask Marion Hucke (marion.hucke@upb.de) for an appointment.

Software projects are graded in the following way:

  • very good: The program runs flawlessly and satisfies all requirements of the chosen topic. Moreover, some original extension has been included or some simulation results are presented demonstrating the scalability of the solution.
  • good: The program runs flawlessly and satisfies all requirements.
  • satisfactory: The program only has some minor issues or satisfies almost all requirements.
  • pass: The program has some major issues or satisfies only a small part of the requirements.
  • fail: The program does not run oder does not satisfy the requirements.

In the following some example topics are given. However, a group may also choose its own topic. In any case, the topic needs to be approved by the lecturer before the group starts with the implementations.

Topics for one person:

  • Implement the algorithm presented in Chapter 4 for the rooted tree distance problem (see slide 96).
  • Implement the basic extension of the median rule presented in Chapter 5 (see slide 59), i.e, without the improvement of efficiently computing b'(u) and the round counter in slide 69.
  • Implement the algorithm for the committee assembly in Chapter 5 (see slide 86) based on arbitrary weight distributions and some desired committee size of s.
  • Implement the Arrow protocol presented in Chapter 7 (see slide 6).
  • Implement the 2-choice algorithm presented in Chapter 7 (see slide 51) together with a simple mechanism to contact random nodes (i.e., via a random walk in a hypercube).

Topics for two people:

  • Implement the algorithm presented in Chapter 4 for the well-formed tree problem.
  • Implement the algorithm presented in Chapter 4 (see slide 69) for the minimum spanning tree problem.
  • Implement the extension of the median rule presented in Chapter 5 with the improvement of efficiently computing b'(u) (see slide 65ff) and the round counter (see slide 69).
  • Implement the RLNC algorithm presented in Chapter 6 (see slide 31).
  • Implement an extension of the Arrow protocol presented in Chapter 7 for multiple servers (see slide 28).
  • Implement the prism-based diffracting tree presented in Chapter 7 to process put requests (no get requests).

Topics for three people:

  • Implement the algorithm presented in Chapter 4 for the SSSP problem (see slide 111).
  • Implement the algorithm presented in Chapter 4 for the bipartiteness problem (see slide 112).
  • Implement the algorithm presented in Chapter 4 for the random cycle formation problem (see slide 126).
  • Implement the prism-based diffracting tree presented in Chapter 7 to match put and get requests (see slide 44).

Topics for four people:

  • Implement one of the algorithms presented in Chapter 4 for the rapidly changing H-graph (either via pointer doubling along hypercubic connections or by combining pieces of random walks in the H-graph).
  • Implement a distributed hashing solution based on a blockchain for each data item (see Chapter 5). You may assume here that the nodes form a hypercube of fixed size and the c locations of the c copies of each data item are determined by c hash functions.
  • Implement a publish-subscribe system based on a blockchain for each subscriber group.
  • Implement a hybrid broadcasting algorithm (where a well-formed tree and random H-graph can be assumed to be given).
  • Implement the low-load or high-load Clarkson algorithm presented in Chapter 8.

Lecture Notes

Homework Assignments

Programming Environment

We will use a simulation environment called NetSimLan. It can be downloaded from https://netsimlan.org/download. You can also find examples there.

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.

Further information: