The distance sensitivity oracle (DSO) problem asks us to preprocess a given graph G = (V, E) in order to answer queries of the form d(x, y, e), which denotes the shortest path distance in G from vertex x to vertex y when edge e is removed. This is an important problem for network communication, and it has been extensively studied in the sequential setting [2, 4, 8, 9] and recently in the distributed CONGEST model [7]. However, no prior DSO results tailored to the parallel setting were known. We present the first PRAM algorithms to construct DSOs in directed weighted graphs, that can answer a query in O(1) time with a single processor after preprocessing.

Minimum Weight Cycle (MWC) is the problem of finding a simple cycle of minimum weight in a graph G = (V, E). This is a fundamental graph problem with classical sequential algorithms that run in Õ(n3) and Õ(mn) time† where n = |V| and m = |E|. In recent years this problem has received significant attention in the context of fine-grained sequential complexity [3, 50] as well as in the design of faster sequential approximation algorithms [13, 26, 32, 33], though not much is known in the distributed CONGEST model.

We present round complexity results in the CONGEST model for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these fundamental problems in both directed and undirected graphs, weighted and unweighted.

The IT infrastructure of large organizations consists of devices and software services purchased from multiple vendors. The problem of measuring the quality of service (QoS) of each of these vendor devices (and services) is challenging since the vendors may tamper with the measurements for monetary benefits or saving debugging efforts. Existing solutions for QoS measurement in trusted environments cannot be extended for this problem since the vendors can easily circumvent them. Solutions borrowed from other areas such as client-server QoS measurement do not help either since they incur unreasonable storage and network overheads, or require extensive modifications to the packet headers. In this paper, we propose the Measuring Tape scheme, comprised of (1) a novel data structure called evidence Bloom filter (e-BF) that can be deployed at the vendor devices (and services), and (2) unique querying techniques, which can be used by the administrator to query the e-BF to measure QoS. While e-BF uses storage and computational resources judiciously, the querying techniques ensure resilience to adversarial behavior. We evaluate our solution based on a few real-world and synthetic traces and with different adversaries. Our results highlight the trade-off between resources (i.e., storage and computation) and the accuracy of QoS predictions, as well as its implications on security. We also present an analytical model of e-BF that establishes the relationship between storage, prediction accuracy, and security. Further, we present security arguments to illustrate how our solution thwarts adversarial attempts to tamper QoS.