Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, a reliable spanner may have some additional vertices for which the spanner property no longer holds, 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+\varepsilon)$-spanners, for $n$ points in $\Re^d$, are known, where the resulting graph has $O( n \log n \log \log^{6}n )$ edges. Here, we show randomized constructions of smaller size 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 $O( n \log \log^{2} n \log \log \log n )$ edges.

翻译：可靠的光扇可以经受巨大的失败, 即使网络中从网络中删除了线性数量的脊椎。 如果失败, 可靠的光扇可能会有一些额外的脊椎, 而这样的脊椎已经不再有, 但是这种附带损害是由攻击规模的一小部分捆绑起来的。 众所周知, 需要美元( n\ log n) 的边缘来实现这个强大的属性, 美元是网络中的脊椎数量, 即使是一个维度。 如果失败, 可靠的脊椎可能有一些额外的脊椎。 建造可靠的几何 $( 1 ⁇ varebsilon) $- spanner, $( $\ re ⁇ d$, $ $, $, $, $, 美元, 但由此得出的图表有 $( n\ log n\ log\ log\ } 6n ) 的边緣。 在这里, 我们展示了规模较小、 以期望的可靠性属性或良好的概率为单位的建筑。 新的构造非常简单, 而且可能很实用 -- 以一个简单的跳板 取代扩大行的等级使用( 使先前的建筑不切实际) $ 美元 。