  We (nearly) settle the time complexity for computing vertex fault-tolerant
(VFT) spanners with optimal sparsity (up to polylogarithmic factors). VFT
spanners are sparse subgraphs that preserve distance information, up to a small
multiplicative stretch, in the presence of vertex failures. These structures
were introduced by [Chechik et al., STOC 2009] and have received a lot of
attention since then. We provide algorithms for computing nearly optimal
$f$-VFT spanners for any $n$-vertex $m$-edge graph, with near optimal running
time in several computational models:
  - A randomized sequential algorithm with a runtime of $\widetilde{O}(m)$
(i.e., independent in the number of faults $f$). The state-of-the-art time
bound is $\widetilde{O}(f^{1-1/k}\cdot n^{2+1/k}+f^2 m)$ by [Bodwin, Dinitz and
Robelle, SODA 2021].
  - A distributed congest algorithm of $\widetilde{O}(1)$ rounds. Improving
upon [Dinitz and Robelle, PODC 2020] that obtained FT spanners with
near-optimal sparsity in $\widetilde{O}(f^{2})$ rounds.
  - A PRAM (CRCW) algorithm with $\widetilde{O}(m)$ work and $\widetilde{O}(1)$
depth. Prior bounds implied by [Dinitz and Krauthgamer, PODC 2011] obtained
sub-optimal FT spanners using $\widetilde{O}(f^3m)$ work and
$\widetilde{O}(f^3)$ depth.
  An immediate corollary provides the first nearly-optimal PRAM algorithm for
computing nearly optimal $\lambda$-\emph{vertex} connectivity certificates
using polylogarithmic depth and near-linear work. This improves the
state-of-the-art parallel bounds of $\widetilde{O}(1)$ depth and $O(\lambda m)$
work, by [Karger and Motwani, STOC'93].
