Dealing with failures is an essential part of modern computing. Built in processes that deal with failures are an essential part of many computing environments, from massive storage devices, large scale parallel computation, and communication networks.In this projectseminar we study how to answer queries in the presence of failures in a network, where one assumes apriori a bound on the number of simultaneous failures. Such a bound is especially relevant in the context of independent failures where the probability of multiple failures decreases exponentially with the number of failures.
In particular, we consider distance and shortest path queries in the presence of edge failures for undirected weighted graphs. Our goal is to preprocess a graph G=(V,E) and produce some (hopefully small) data structure used to answer subsequent queries of the form (s,t,F), where F is a subset of at most f edges.
The answer to such a query is an approximation to the shortest path length between s and t in the graph G - F (which is the graph obtained by removing the edges of F from G). Moreover, one may desire to print out such a path. We call such a data structure an f-DSO (DSO = Distance Sensitivity Oracle). There are several parameters to be considered with respect to suggested f-DSOs.
- The size of the data structure required.
- The time needed to answer distance queries (s,t,F).
- The approximation ratio (also known as the stretch), how close are our estimated distances to the actual distances?
- The time required for the preprocessing phase.
There has been tramendous amount of theoretical work on f-DSOs for optimizing the above parameters, for example:
SODA 2017
SODA 2019
ICALP 2019
STOC 2020
MFCS 2021
ESA 2021
ITCS 2021
ICALP 2022
STOC 2023
However, there is very limited algorithm engineering research for implementing these algorithms and data-structures.
In this project seminar we will explore algorithm engineering aspects of implementing some of these data-structures and algorithms.
