Personen: Dr. Katrin Casel, Dr. Sarel Cohen, Maximilian Katzmann, Gregor Lagodzinski, Martin Schirneck
Links: Courses IT-Systems Engineering, Algorithm Engineering Moodle

In many algorithms used in computing environments such as massive storage devices, large scale parallel computation, and communication networks, recovering from failures must be an integral part. Therefore, designing algorithms and data-structures whose running time is efficient even in the presence of failures is an important task. In this project seminar we study two research directions: (1) variants of shortest paths algorithms and data-structures in settings with failures, and (2) fault-tolerant in the settings of fixed parameter tractable (FPT) algorithms. See more details on these problems below.

The goal is to learn and practice important research techniques: literature search, understanding and presenting research papers, developing ideas in the group, testing of conjectures with the computer, writing down results.

The main focus of the project seminar lies on active research. You will form small groups to work on the topic of your choice. For each topic, there will be a short introduction in the first few weeks. During this time you will get familiar with the underlying problem. After that, you will actively work out solutions for the problem. We will support you with weekly meetings where we discuss your ideas and approaches, the progress, and further actions. While you will be guided by us, we encourage you to propose your own ideas. In the end, each team will write up their findings in a paper and present their results to the others. Summing up, the outline of the course looks roughly as follows.

• First half: Introduction to the topic, literature review, each student presents an existing paper from a list of relevant papers.
• Second half: confrontation with the topic and active research on it. Conducting research together with the lecturers on these problems. Writing a paper and presenting your results.

There are no formal requirements to participate in this course. However, the students should be familiar with algorithms and data-structures.

The grade will be based on 70% on your scientific report / paper and 30% on your presentations (of both an existing paper, and of your new results).

There will be an introductory meeting via Zoom on April 15, 9:15 a.m. (link will be provided in the moodle). There, we discuss the topics, the teams, details and all the following dates.

The officially alloted time slot is on Thursdays 9:15 am.

We will research variants of shortest paths algorithms and data-structures in setting with failures as well as fixed-parameter tractable algorithms in settings with failures, as described below.

(1) Fault-tolerant shortest paths - We study variants of shortest paths algorithms and data-structures in setting with failures. In particular, we study the Replacement Paths (RP) problem, where given a shortest s-t-path P in a graph, we want to compute for every edge e in P the shortest path from s to t avoiding e. The goal of this research direction is to construct efficient algorithm and data-structures for computing both exact and approximate replacement paths in various settings, and derandomize existing randomized algorithms for these problems.

(2) Faulttolerant fixed-parameter tractable algorithms – We aim to develop efficient algorithms and data-structures to solve paramterized problems (such as k-path, vertex cover, maximum independent set, etc.) in settings with failures. Upon a failure, it is inefficient to re-compute in exponential time the solution to the problem. Instead the goal is preprocess the graph in exponential time, and then upon failure to compute the solution in polynomial or even poly-logarithmic time.

(3) Benchmarking algorithms on NVRAM - Non-Volatile Random Access Memory is an up and coming hardware technology, it allows data to persist in memory even if the system crashes or looses power and also comes which much larger storing capacity (up to 6TB). New algorithms are needed to take advantage of these features. We want to find found what is possible on NVRAM machines especially in the context of large real-world networks. This research projects also involves benchmarking the algorithm implemented in GraphBLAST on actual hardware.

This list is not exhaustive and we are open to more suggestions.