RedStuff Recovery Example

A Walrus shard that loses its slivers recovers them by requesting recovery symbols from other shards. This recovery scenario continues the RedStuff encoding example and uses shard 3 as the failed shard.

How does a shard recover lost slivers?

Consider that shard 3 fails, losing its slivers, and needs to recover them. Recovery symbols are ordinary sliver symbols: each one is the symbol where a contacted shard's sliver intersects the lost sliver. This example recovers the primary sliver first. When the other shards hold their slivers, either order works, and storage nodes recover both slivers concurrently. Only in the worst-case initial sharing does the secondary sliver have to come first, because it needs only $N-2f$ symbols.

In the matrices in this section, red marks the symbols of the lost slivers and green marks the recovery symbols that other shards provide. Shards never store the lower-right quadrant. In the following matrix, row 3 is the primary sliver of shard 3 and column 3 is its secondary sliver.

$$\left[ \begin{array}{ccccc|cc} s_{0,0} & s_{0,1} & s_{0,2} & \color{red} s_{0,3} & s_{0,4} & r_{0,5} & r_{0,6} \\ s_{1,0} & s_{1,1} & s_{1,2} & \color{red} s_{1,3} & s_{1,4} & r_{1,5} & r_{1,6} \\ s_{2,0} & s_{2,1} & s_{2,2} & \color{red} s_{2,3} & s_{2,4} & r_{2,5} & r_{2,6} \\ \hline \color{red} r_{3,0} & \color{red} r_{3,1} & \color{red} r_{3,2} & \color{red} r_{3,3} & \color{red} r_{3,4} & & \\ r_{4,0} & r_{4,1} & r_{4,2} & r_{4,3} & r_{4,4} & & \\ r_{5,0} & r_{5,1} & r_{5,2} & r_{5,3} & r_{5,4} & & \\ r_{6,0} & r_{6,1} & r_{6,2} & r_{6,3} & r_{6,4} & & \\ \end{array} \right]$$

How does shard 3 recover its primary sliver?

To recover the primary sliver:

1. The node contacts 5 other shards and requests the recovery symbols for primary sliver 3.
2. Each contacted shard encodes its secondary sliver (highlighted as a column) to obtain its recovery symbol. This step is necessary because these symbols are repair symbols.
3. Each contacted shard provides its recovery symbol to shard 3.

For example, shards 0, 1, 2, 4, and 6 provide the symbols $r_{3,0}$, $r_{3,1}$, $r_{3,2}$, $r_{3,4}$, and $r_{3,6}$, shown in green:

$$\left[ \begin{array}{c|c|c|c|c|c|c} s_{0,0} & s_{0,1} & s_{0,2} & \color{red} s_{0,3} & s_{0,4} & r_{0,5} & r_{0,6} \\ s_{1,0} & s_{1,1} & s_{1,2} & \color{red} s_{1,3} & s_{1,4} & r_{1,5} & r_{1,6} \\ s_{2,0} & s_{2,1} & s_{2,2} & \color{red} s_{2,3} & s_{2,4} & r_{2,5} & r_{2,6} \\ \color{green} r_{3,0} & \color{green} r_{3,1} & \color{green} r_{3,2} & & \color{green} r_{3,4} & & \color{green} r_{3,6}\\ \end{array} \right]$$

How does shard 3 recover its secondary sliver?

To recover the secondary sliver:

1. The node contacts at least 3 other shards to obtain recovery symbols.
2. Each contacted shard provides the recovery symbol from its primary sliver (highlighted as a row). The recovery symbols are already part of the primary slivers that the other shards store, so no re-encoding is necessary.
3. Shard 3 decodes the 3 symbols to obtain its secondary sliver, unless the symbols are the symbols of the secondary sliver itself.

For example, shards 0, 1, and 5 provide the recovery symbols $s_{0,3}$, $s_{1,3}$, and $r_{5,3}$, shown in green:

$$\left[ \begin{array}{ccccc} s_{0,0} & s_{0,1} & s_{0,2} & \color{green} s_{0,3} & s_{0,4} \\ \hline s_{1,0} & s_{1,1} & s_{1,2} & \color{green} s_{1,3} & s_{1,4} \\ \hline s_{2,0} & s_{2,1} & s_{2,2} & s_{2,3} & s_{2,4} \\ \hline \color{red} r_{3,0} & \color{red} r_{3,1} & \color{red} r_{3,2} & \color{red} r_{3,3} & \color{red} r_{3,4} \\ \hline r_{4,0} & r_{4,1} & r_{4,2} & r_{4,3} & r_{4,4} \\ \hline r_{5,0} & r_{5,1} & r_{5,2} & \color{green} r_{5,3} & r_{5,4} \\ \hline r_{6,0} & r_{6,1} & r_{6,2} & r_{6,3} & r_{6,4} \\ \end{array} \right]$$

Because $r_{5,3}$ is a repair symbol, shard 3 decodes the 3 symbols to obtain its secondary sliver. If shards 0, 1, and 2 respond instead, they provide $s_{0,3}$, $s_{1,3}$, and $s_{2,3}$, which are the symbols of the secondary sliver itself, so shard 3 does not need to decode.

For properties, Walrus-specific parameters, blob size limits, and sliver authentication details, see RedStuff properties and parameters.