Sometimes Reliable Spanners of Almost Linear Size

$\renewcommand{\Re}{\mathbb{R}}\newcommand{\Of}{\mathcal{O}}\newcommand{\eps}{\varepsilon}$Reliable (Euclidean) spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, some of the remaining vertices of a reliable spanner may no longer admit the spanner property, but this collateral damage is bounded by a fraction of the size of the attack. It is known that $\Omega(n\log n)$ edges are needed to achieve this strong property, where $n$ is the number of vertices in the network, even in one dimension. Constructions of reliable geometric~$(1+\eps)$-spanners, for $n$ points in $\Re^d$, are known, where the resulting graph has $\Of( n \log n \log\!\log^{6}\!n )$ edges. Here, we show randomized constructions of smaller size Euclidean spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical -- replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip list like construction. This results in a $1$-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in $\Re^d$ with~$\Of( n \log\!\log^{2}\!n \log\!\log\!\log n )$ edges.