A liquid system provides durable object storage based on spreading redundantly generated data across a network of hundreds to thousands of potentially unreliable storage nodes. A liquid system uses a combination of a large code , lazy repair , and flow storage organization . We show that a liquid system can be operated to enable flexible and essentially optimal combinations of storage durability, storage overhead, repair bandwidth usage, and access performance.

Consider the following problem: Given k=2 q random lists of n-bit vectors, L 1,…,L k , each of length m, find x 1∈L 1,…,x k ∈L k such that x 1+⋅⋅⋅+x k =0, where + is the XOR operation. This problem has applications in a number of areas, including cryptanalysis, coding theory, finding shortest lattice vectors, and learning theory. The so-called k-tree algorithm, due to Wagner, solves this problem in $\tilde{O}(2^{q+n/(q+1)})$ expected time provided the length m of the lists is large enough, specifically if m≥2 n/(q+1). In many applications, however, it is necessary to work with lists of smaller length, where the above algorithm breaks down. In this paper we generalize the algorithm to work for significantly smaller values of the list length m, all the way down to the threshold value for which a solution exists with reasonable probability. Our algorithm exhibits a tradeoff between the value of m and the running time. We also provide the first rigorous bounds on the failure probability of both our algorithm and that of Wagner. As a third contribution, we give an extension of this algorithm to the case where the vectors are not binary, but defined over an arbitrary finite field $\mathbb{F}_{r}$ , and a solution to λ 1 x 1+⋅⋅⋅+λ k x k =0 with $\lambda_{i} \in \mathbb{F}_{r}^{*}$ and x i ∈L i is sought.

In the standard consensus problem there are n processes with possibly different input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called the stabilizing consensus problem [2]. In this problem, we do not require that each process commits to a final value at some point, but that eventually they arrive at a common, stable value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Our main result is a simple randomized algorithm called median rule that, with high probability, just needs O(log m log log n + log n) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most √n processes at any time. Without adversarial involvement, just O(log n) time and work is needed for a stable consensus, with high probability. As a by-product, we obtain a simple distributed algorithm for approximating the median of n numbers in time O(log m log log n + log n) under adversarial presence.

Consider the following problem: Given k = 2q random lists of n-bit vectors, L1, …, Lk, each of length m, find x1 ∊ L1, …, xk ∊ Lk such that x1 + ··· + xk =0, where + is the XOR operation. This problem has applications in a number of areas, including cryptanalysis, coding theory, finding shortest lattice vectors, and learning theory. The so-called k-tree algorithm, due to Wagner, solves this problem in expected time provided the length m of the lists is large enough, specifically if m ≥ 2n/(q+1). In many applications, however, it is necessary to work with lists of smaller length, where the above algorithm breaks down. In this paper we generalize the algorithm to work for significantly smaller values of the list length m, all the way down to the threshold value for which a solution exists with reasonable probability. Our algorithm exhibits a tradeoff between the value of m and the running time. We also provide the first rigorous bounds on the failure probability of both our algorithm and that of Wagner.

We show that the error probability for decoding interleaved Reed-Solomon Codes with the decoder found by Bleichenbacher et al. [1] is upper bounded by O(1/q), independently of η.