  We construct data structures for extremal and pairwise distances in directed
graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017]
initiated the study of fault-tolerant (sensitivity) oracles for the diameter
and vertex eccentricities. We extend this with a special focus on space
efficiency. We present several new data structures, among them the first
fault-tolerant eccentricity oracle for dual failures in subcubic space. We
further prove lower bounds that show limits to approximation vs. space and
diameter vs. space trade-offs for fault-tolerant oracles. They highlight key
differences between data structures for undirected and directed graphs.
  Initially, our oracles are randomized leaning on a sampling technique
frequently used in sensitivity analysis. Building on the work of Alon, Chechik,
and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a
hierarchical framework to derandomize fault-tolerant data structures. We first
apply it to our own diameter and eccentricity oracles and then show its
versatility by derandomizing algorithms from the literature: the distance
sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path
algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first
deterministic distance sensitivity oracle with subcubic preprocessing time.
