Fault Tolerant Data Structures
Speaker
Keerti Choudhary
Weizmann Institute
Host
Akshay Degwekar, Pritish Kamath and Govind Ramnarayan
Abstract:
In this talk, we look at the problem of single-source-reachability (SSR) in presence of failures of vertices and edges. In the static setting, it can be solved in O(|V|+|E|) time, for any directed graph G=(V, E). To model the scenario of a faulty network, we associate a parameter k with the network such that there are at most k vertices (or edges) that are failed at any stage. The goal is to preprocess the graph G and compute a compact data structure, that, given any set F of at most k vertices (or edges), efficiently solves the SSR problem for the graph G\F. We show that for any set F of size k, solves SSR problem for G\F in O(2^k n) time. Previously the only known construction was single fault. One major application of this structure is a fault tolerant algorithm for SSC (strongly connected components).
In this talk, we look at the problem of single-source-reachability (SSR) in presence of failures of vertices and edges. In the static setting, it can be solved in O(|V|+|E|) time, for any directed graph G=(V, E). To model the scenario of a faulty network, we associate a parameter k with the network such that there are at most k vertices (or edges) that are failed at any stage. The goal is to preprocess the graph G and compute a compact data structure, that, given any set F of at most k vertices (or edges), efficiently solves the SSR problem for the graph G\F. We show that for any set F of size k, solves SSR problem for G\F in O(2^k n) time. Previously the only known construction was single fault. One major application of this structure is a fault tolerant algorithm for SSC (strongly connected components).