  A $k$-spanner of a graph $G$ is a sparse subgraph $H$ whose shortest path
distances match those of $G$ up to a multiplicative error $k$. In this paper we
study spanners that are resistant to faults. A subgraph $H \subseteq G$ is an
$f$ vertex fault tolerant (VFT) $k$-spanner if $H \setminus F$ is a $k$-spanner
of $G \setminus F$ for any small set $F$ of $f$ vertices that might "fail." One
of the main questions in the area is: what is the minimum size of an $f$ fault
tolerant $k$-spanner that holds for all $n$ node graphs (as a function of $f$,
$k$ and $n$)? This question was first studied in the context of geometric
graphs [Levcopoulos et al. STOC '98, Czumaj and Zhao SoCG '03] and has more
recently been considered in general undirected graphs [Chechik et al. STOC '09,
Dinitz and Krauthgamer PODC '11].
  In this paper, we settle the question of the optimal size of a VFT spanner,
in the setting where the stretch factor $k$ is fixed. Specifically, we prove
that every (undirected, possibly weighted) $n$-node graph $G$ has a
$(2k-1)$-spanner resilient to $f$ vertex faults with $O_k(f^{1 - 1/k} n^{1 +
1/k})$ edges, and this is fully optimal (unless the famous Erdos Girth
Conjecture is false). Our lower bound even generalizes to imply that no data
structure capable of approximating $dist_{G \setminus F}(s, t)$ similarly can
beat the space usage of our spanner in the worst case. We also consider the
edge fault tolerant (EFT) model, defined analogously with edge failures rather
than vertex failures. We show that the same spanner upper bound applies in this
setting. Our data structure lower bound extends to the case $k=2$ (and hence we
close the EFT problem for $3$-approximations), but it falls to $\Omega(f^{1/2 -
1/(2k)} \cdot n^{1 + 1/k})$ for $k \ge 3$. We leave it as an open problem to
close this gap.
