Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/~anromash/ps/stacs2006.pdf Äàòà èçìåíåíèÿ: Wed Mar 21 14:44:53 2012 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 12:11:01 2012 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: mercury program

Reliable Computations Based on Locally Decodable Codes
Andrei Romashchenko September 18, 2005

Abstract We investigate the coded model of fault-tolerant computations introduced by D. Spielman. In this model the input and the output of a computation circuit is treated as words in some error-correcting code. A circuit is said to compute some function correctly if for an input which is a encoded argument of the function, the output, been decoded, is the value of the function on the given argument. We consider two models of faults. In the first one we suppose that an elementary processor at each step can be corrupted with some small probability, and faults of different processors are independent. For this model, we prove that a parallel computation running on n elementary non-faulty processors in time t = poly(n) can be simulated on O(n log n/ log log n) faulty processors in time O(t log log n). Note that we get sub-logarithmic blow-up of the memory, which cannot be achieved in the classic model of faulty boolean circuit, where the input is not encoded. In the second model, we assume that at each step some fixed fraction of elementary processors can be corrupted by an adversary, who is free to chose these processors arbitrarily. We show that in this model any computation can be made reliable with exponential blow-up of the memory. Our method employs a sort of mixing mappings, which enjoy some properties of expanders. Based on mixing mappings, we implement an effective selfcorrecting procedure for an array of faulty processors.

1

Introduction

The problem of reliable computations with faulty elements was investigated for several types of computational models, see a survey in [14]. In the most popular models, the computation is implemented by a circuit of boolean gates; each gate can fail with a small probability. A circuit is said fault-tolerant if it returns a correct result with high probability. For the first time such a model of computation was proposed by J. von Neumann [1]. Later ideas by von Neumann was developed by Dobrushin and Ortyukov [3]. N. Pippenger in [5] presented an effective transformation of any boolean circuit with non-faulty gates into a fault-tolerant circuit.


Institute for Information Transmission Problems, Moscow. e-mail:anromash@mccme.ru

1


The construction of Pippenger requires only logarithmic increasing of the number of gates. In general, this result cannot be improved, and logarithmic redundancy is inevitable [4, 8, 6, 7]. But this lower bound is caused by the need to encode the input with some error-correcting code and then to decode the answer. This obstacle can be eliminated if we allow to get the input and to return the result as an encoded word. Such a model was used in the work of D. Spielman [10]. Let us define this model (with minor modifications) in detail. The computational model. The computational array consists of N elementary processors s1 , . . . , sN . At any moment, each processor contains one bit of information (a processor is said to have an internal state 0 or 1). We fix two functions, E : {0, 1}n {0, 1} and D : {0, 1}
N N

{0, 1}

n

which are normally the encoding and decoding functions of some error-correcting code. We say that a circuit gets an input x {0, 1}n if the initial state of the memory (s1 , . . . , sN ) is equal to E (x). (t) (t) Denote by s1 , . . . , sN the internal states of the processors at moment t. We call (t) by a circuit of depth T a list of instructions Fi , t = 1, . . . , T which define how each of the processors should update its internal state at each moment. More precisely, the state of a processor si at moments t evolves by the rule si = F
(t) (t) (t) i

(sj1

(t-1)

,s

(t-1) j2

, . . . , sjr

(t-1)

),

where Fi are boolean functions (the indexes j1 , . . . , jr depend on i and t). The arity r is supposed to be fixed in advance. We shall always suppose that r is a constant independent of n. We say that a circuit of depth T computes a function f : {0, 1}n {0, 1}n if for any x (T ) (0) (0) (T ) D(s1 , . . . , sN ) = f (x), if (s1 , . . . , sN ) = E (x) In other words, we use the encoding E to provide the circuit with an input, and then use the decoding D to retrieve the result. We shall say also that such a circuit computes f in T steps. In the model of random faults we suppose that at any step each processor can be randomly corrupted, i.e., with some small probability it can change its internal state contrary to the rule above. Faults at different positions i and moments t (i.e., the events that a processor si was corrupted at moment t) are supposed to by independent. For this model, we say that some circuit correctly computes a function f with probability , if Prob[D(s1 , . . . , sN ) = f (x)|(s1 , . . . , sN ) = E (x)] = 1 - . 2
(T ) (T ) (0) (0)


In another model faults are made by an malevolent adversary. This means that at any moment t any N processors can be corrupted. We say that a circuit computes some function f if for any choice of the positions where processors are corrupted, the final result is correct, i.e., again D(s1 , . . . , sN ) = f (x) if (s1 , . . . , sN ) = E (x) Note that the defined model is trivial if the functions E and D may depend on the function f . In the sequel we fix some E and D and show that any function f can be computed by a reliable circuit (in the model with random faults or in the model with an adversary). The rest of the paper is organized as follows. In Section 2 we introduce mixing mappings, the main combinatorial tool of our proofs. In Section 3 we consider the model of random faults and prove that any circuit of depth T with n processors can be converted in a reliable circuit with O(n log(nT )/ log log(nT )) processors, which computes the same function in time O(T log log(nT ). This bound is a bit stronger than the result of [10], where the construction requires poly-logarithmic blow-up and polylogarithmic slow down. If T = poly(n), the blow-up in our construction is equal to O(log n/ log log n), i.e., it is below the log n barrier, which is strict for the usual model of faulty boolean circuits (where the input of a circuit is not encoded). Our construction is effective, i.e., the fault-tolerant circuit can be constructed from the original one by a polynomial algorithm. In Section 4 we deal with the model where faults are chosen by an adversary. We prove that any circuit of depth T with n processors can be converted in a reliable circuit with 2O(n) processors and depth O(nT ).
(T ) (T ) (0) (0)

2

Mixing functions
m

In this section we define mixing mappings and prove some of their properties. Definition 1 We call a mapping F : {0, 1}m â {0, 1} {0, 1} mixer if for any A, B {0, 1}m such that |A| 2m |{(x, u) : x A, F (x, u) B }| - a (m, , , )-

2 |A| · |B | < 2 |A|. 2m

This definition was inspired by the well-known Expander Mixing Lemma, see e.g, [11]. The Expander Mixing Lemma implies that an expander is a mixer with appropriate parameters. We need mixers with some additional structure. First of all, we consider L = {0, 1}m as an m-dimensional linear space over Z/2Z (for u, v L the vector u + v is just the bitwise sum of u and v modulo 2). Definition 2 We call a mapping F : {0, 1}m â{0, 1} {0, 1}m a linear (m, , , )mixer if (1) F is a (m, , , )-mixer, and (2) the mapping G : {0, 1}m â {0, 1} {0, 1}m defined as G(x, u) = F (x, u) + x, is also a (m, , , )-mixer. Standard probabilistic arguments show that a linear mixer exists: 3


Lemma 1 For any , (0, 1) there exists a such that for all m there exists a linear (m, , , )-mixer. We prove this lemma in Appendix. The following properties of a mixer easily follows from the definition: Claim 1 If 0 < < < 1/8 then for any (m, , , )-mixer F , for any B {0, 1}m of size at most 2m /8 there are less than 2m elements x {0, 1}m such that for at least 25% of u {0, 1} F (x, u) B . Claim 2 Let 0 < < < 1/128 and F be an (m, , , )-mixer. Then for any B {0, 1}m of size at most 2m /128 there are less than 2m elements x {0, 1}m such that for at least 1/64 of all u {0, 1} F (x, u) B . We prove Claim 1 in Appendix; Claim 2 follows from similar arguments. Lemma 2 Let F1 be an (m1 , 1 , 1 , 1 )-mixer and F2 be an (m2 , 2 , 2 , 2 )-mixer. Then the tensor product F = F1 F2 F : {0, 1}
m1 +m2

â {0, 1}

1 +2

{0, 1}

m1 +m2 1 +1 +2 2 2

is an (m1 + m2 , 1 + 2 , , )-mixer for =



2 and = O(

+



2 )

This lemma is interesting for 1 1 2 2 . The bound in this lemma is quite rough, but it is enough for application below. Lemma 2 can be proved with quite standard combinatorial arguments, see Appendix. Remark that if F1 and F2 are linear mixers then F1 F2 is also a linear mixer. Lemma 3 For any , and large enough there exists an algorithm which an the m input m constructs a linear (m, , , )-mixer in time poly(22 ). Proof: Denote N = 22 . From Lemma 1 it follows that for all , and a large n enough , for all n a linear (n, , , )-mixer exists. If 2n2 = poly(N ), we can construct a linear (n, , , )-mixer in time poly(N ) using a brute force search. In particular, for any , , , we can get in polynomial time some mixers with parameters (m/2, , , ) and (m/2, , , ). (degree of the polynomial may depend on , , , ). Further, construct a tensor product of these two mixers. From + Lemma 2 it follows that we obtain a linear (m, + , , O( + + ))mixer. It remains to choose appropriate , and , .
m

3

Computations resistant to random faults

In this section we show how to implement reliable computations with a circuit based on faulty processors. We assume that each processor at one step of computation is 4


corrupted with small enough probability > 0, and that faults at different processors and at different moments of time are independent. We use encoding based on the Hadamard code. Remind that the Hadamard code is a mapping n H ad : {0, 1}n {0, 1}2 where H ad(a1 , . . . , an ) is the graph of the linear function of n variables f (x1 , . . . , xn ) =
1in

ai xi

(the coefficients ai and the variables xi ranges over the field Z/2Z). The code is linear, so for any x, y {0, 1}n we have H ad(x y ) = H ad(x) H ad(y ). Here and in the sequel we denote by x y the bitwise sum modulo 2. Theorem 1 For any circuit S of depth t with n processors, for any res > 0 there ^ exists a circuit S of depth O(t log log(tn)), with O(n log(nt)/ log log(nt)) processors that computes the same function for the encoded input so that if any processor at each step is corrupted with probability < 1/8 then the result is correct with probability at least (1 - res ). Moreover, there exists a polynomial algorithm that constructs such a ^ circuit S given S . Proof: Denote by y (j ) = (y1 , y2 , . . . , yn ) the state of the memory of S at the j -th step of the computation, j = 0, . . . , t. We shall define an encoding E : {0, 1}n ^ {0, 1}N and the corresponding decoding D : {0, 1}N {0, 1}n , and a circuit S ( i) ( i) ^ with N processors so that for any j the internal state z (j ) = (z1 , . . . , zN ) of S with high probability is close to E (y (i) ). More precisely, we require that with high probability the equality D(z (j ) ) = y (j ) holds. In particular, for the final result z (t) we get D(z (t) ) = y (t) . Let us implement the plan presented above. We split the set of variables (x1 , . . . , xn ) into blocks of size k = log(log n + log t) + C : b1 = x1 , . . . , xk , b2 = xk+1 , . . . , x2k , ... ... (the constant C will be chosen below). The total number of blocks bi is r = n/k . A Restriction on Parallelism: Let us restrict the power of the parallelism in S . We shall assume that in the circuit S at each step in every block bi only one processor changes its internal state. Moreover, we assume that every time when a processor changes its state, its new state is a boolean function of internal states of two processors from the previous step. In the sequel we show that a circuit that satisfies these ^ restrictions can be simulated by a fault-tolerant circuit S with blow-up of the memory O(2k /k ) in real time, i.e., without any slow down.
(j ) (j ) (j )

5


It is easy to see that an arbitrary circuit can be transformed so that the assumptions above hold. The price for this transformation is a constant blow-up of the memory and slow down O(k ) = O(log log(nt)). Thus, to prove the theorem it remains to explain how to construct a reliable circuit for an S satisfying these restrictions. From this moment, we assume that S satisfy the Restriction on Parallelism. First of all, we specify encoding and decoding. Define encoding E : {0, 1}n {0, 1}N as follows: E (x1 , . . . , xn ) = H ad(b1 ) . . . H ad(br ). Denote ^i = H ad(bi ). Note that the length of each ^i is 2k = 2C log(tn) and the b b length of the codewords is N = r2k = O(n log(tn)/ log log(tn)). Define manipulations with encoded data. Denote by z
(j )

= (z

(j ) 1

,z

(j ) 2

,...,z

(j ) N

)

the state of memory of the circuit at j -th stage of computation. We split z (j ) into blocks (j ) (j ) of length 2k and denote them ^1 , . . . , ^r . b b Further we define the transition rule: how z (j +1) is computed from z (j ) . We define (j ) (j ) it so that with high probability for all j each block ^i differs from H ad(bi ) in a b fraction at most 1/8 of all bits. In our model, at each step j = 1, . . . , t each value z1 , . . . , zN is computed as a function of the internal states of O(1) processors at the previous step. Remind that some of cells can be corrupted by random faults. Faults at different cells are independent and each one occurs with probability . We say that the random perturbation is k ^ 0 -normal if for any block bi at any stage of computation, there are at most 0 · 2 faults. Lemma 4 For any 0 ( , 1/8) and large enough constant C (which defines the length of blocks bi ) the perturbation is 0 -normal with probability greater than (1 - r es ). Proof of the lemma: For each block ^i at each step the average number of faults is b equal to 2k . From the Chernoff bound it follows that Prob[number of faults >
0

2k ] < e-(

-

0

)2 2

k

.

Sum up this probability for all i = 1, . . . , r and all step j = 1, . . . , t. The sum is less than res if the constant C is large enough. Let us fix some 0 ( , 1/8); in the sequel we assume that the perturbation is 0 -normal, and construct a circuit which returns a correct result under this assumption. Also we fix some 0 > 0 such that 80 + 0 < 1/8. Let M ix be a linear (k , , 0 /2, 0 )mixer. As we showed in Lemma 3, such a mixer can be found in time poly(n, t). (j ) In the sequel we prove by induction the following property: if at step j each ^i b (j ) (j +1) differs from the corresponding H ad(^i ) in at most 1/8 of bits, then each ^i b b also (j +1) differs from the corresponding H ad(^i b ) in at most 1/8 of bits (we assume that the random perturbation is 0 -normal). b We define the computation step in two stages. First, we define ^i , i = 1, . . . , r; ^ is a function of O(1) bits from ^(j ) . At the second stage we define each bit of bi bi 6


^ , i = 1, . . . , r, each bit of a ^ is a function of O(1) bits from (^ , . . . , b ). Then we bi bi b1 r ^(j +1) = ^ , i = 1, . . . , r. bi set bi Now we describe the first stage of the construction. Fix a number of a block i, num(j ) ber of a step j , and let ^i = (u1 , . . . , u2k ). We identify an integer q {1, . . . , 2k } b and its k -digit binary representation (with leading zeros). Thus, we can use q as the first argument of the mixer M ix. Moreover, for an integer q 2k and {0, 1} we can consider uM ix(q,)q , where M ix(q , ) is the bitwise sum of two k -bit words: M ix(q , ) and the binary representation of q . (j ) (j ) Assume that ^i differs from E (bi ) in at most 2k /8 bits. For any q the bit uq is b computed as uq = maj ority {(u
M ix(q , )q

-u

M ix(q , )

) | {0, 1} }

(here we identify the integer q 2k and its binary representation; thus, uM ix(q,)q is uj , where the k -digit binary representation of j is the bitwise sum modulo 2 of the binary representation of q and M ix(q , )). ) Let us bound the number of bits in ^ = (u1 , . . . , u2k ) that differ from the corb (j ) responding bits of H ad(bi ). There may be two reasons why a uq differs from the corresponding bit of H ad(b
(j ) i

):
ix(q , )q

1. in the sequence uM ix(q,0)q , . . . , uM (j ) the corresponding values of E (bi );

at least 25% of values differ from

2. in the sequence uM ix(q,0) , . . . , uM ix( (j ) corresponding values of H ad(bi );

q , )

at least 25% of values differ from the

From Claim 1 it follows that there are at most 20 2k positions q where at least one of these two conditions hold. Thus, we proved the following bound: Claim 3 There are at most 20 2k positions q = 1, . . . , 2k , where uq differs from the corresponding bit of E (b
(j ) i

).

Remind that we assume that at each step of the computation in the original circuit S exactly one bit of every block is updated. Let on the j -th step in a block ^i0 the b (j +1) (j ) (j ) internal state of a processor c0 was updated: xc0 = Fj (xc1 , xc2 ), where Fj is some boolean function. Let the bits xc1 and xc2 be from the blocks ^i1 and ^i2 respectively b b (j ) (j +1) (ci {1, . . . , N }). The difference between H ad(bi0 ) and H ad(bi0 ) is a function of xc0 , xc1 , xc2 . More exactly, if = Fj (xc1 , xc2 ) - xc0 , then the bitwise sum modulo 2 (j +1) (j ) H ad(bi0 ) H ad(bi0 ) is equal to H ad(0, Let us explain all i = i0 we let . . . , 0, , 0, . . . , 0). the second stage of the construction and define uq . First of all, for ^ = ^ . For ^ make the computations as follows. Let ^ = bi bi bi0 bj0
(j ) (j ) (j )

7


(u1 , . . . , u2k ), ^j1 = (v1 , . . . , v2k ) and ^j2 = (w1 , . . . , w2k ). For each q = 1, . . . , 2 b b we estimate the value xc0 as xc0 = maj ority {(u ~ and the values xc1 and xc2 as xc1 = maj ority {(vM ~ and xc2 = maj ority {(wM ~
ix(q , )c2 ix(q , )c1 M ix(q , )c0

k

-u

M ix(q , )

) | {0, 1} },

- vM

ix(q , )

), | {0, 1} } ), | {0, 1} }

- wM

ix(q , )

~ respectively. Set = Fj (xc1 , xc2 ) - xc0 and add the q -th digit of the value ~~ ~ ~ H ad(0, . . . , 0, , 0, . . . , 0) to the bit uq (as usual, all operations are in the field Z/2Z). Note that xc0 is ~ correctly unless at least 25% of the values vM ix(q,0)+c0 , . . . , vM ix(q, )+c0 are or at least 25% of the values vM ix(q,0) , . . . , vM ix(q, ) are corrupted. From there are at most 20 2k positions q where one of these two conditions holds. is true for xc1 and xc2 . ~ ~ Let us bound the number of positions q where uq differs from the q H ad(b
(j +1) 1 (j )

estimated corrupted Claim 1, The same -th bit of

). All but 20 2k positions uq are equal to the corresponding bits of the

(2k )-bit string H ad(b1 ). All three values xc0 , xc1 , and xc2 are estimated correctly for at least 60 2k positions. Further, at most 0 2k bits of one block can be corrupted due to random faults. In total, the fraction of position where uq is not equal to the ) is at most 80 + 0 < 1/8. corresponding bit of H ad(b0 We proved that any computation can be made reliable so that the result is correct with some fixed probability (1 - res ). We might want to get a circuit which fails with exponentially small probability. To decrease the probability of a failure, we can increase the size k of blocks bi used in the proof of Theorem 1. If we let k = C log log(tn) for some C > 1, our construction results in a circuit which fails C with probability e-(log (tn)) ; blow-up of the memory in this circuit is O(2k /k ) = O(logO(1) (tn)). To implement this construction, we need a linear mixer with parameters (log(logO(1) (tn)), , , ). Such a mixer can be constructed in time poly(t, n); really, it is enough to get the tensor product of O(1) linear mixers with parameters ( 1 log log(nt), , , ). 2 To get a circuit that fails with probability e-(n) , we need a linear (log(tn), , , )mixer. Such a mixer exists, though we have no effective algorithm to construct it. But ^ if we omit the condition that S can be received from S effectively then we can apply the same arguments as in Theorem 1 and get the following result: ^ Theorem 2 For any circuit S of depth t with n processors there exists a circuit S of depth poly(t, n) with poly(t, n) processors that computes the same function for the encoded input so that if any processor at each step is corrupted with probability ^ < 1/8 then the result is correct with probability at least (1 - e-(n) ). The circuit S can be constructed from S in time 2poly(t,n) . 8
(i+1)


4

Computations resistant to an adversary

Now we consider the model where at each step an adversary chooses arbitrarily the fraction of all processors and corrupts them. We show that any computation circuit can made resistant to such an adversary with exponential blow-up of the memory. Theorem 3 For a small enough > 0, for any circuit S of depth t with n processors ^ ^ there exists a circuit S of depth tn with N = 2O(n) processors such that S computes correctly the same function (for the encoded input) if at each step the fraction at most of all processors are corrupted. ^ The circuit S can be constructed from S quasi-effectively: there exists a polynomial algorithm which gets S , the number of a processor i 22n , and the number , and returns (1) the boolean function required to update the state of the i-th processor at the -th step, and (2) the list of O(1) processors that are queried by the processor number i at this step of computation. Note that the binary representation of i is O(n), so this algorithm runs in time poly(n, t). Proof: We assume that in the original circuit at each step of computations only one processor can update its internal state (any circuit can be transformed to this form, for the price of n-time slow down and constant blow-up of the memory). Further we prove ^ that a circuit S which satisfy this assumption can be simulated by a fault-tolerant S in real time. (j ) (j ) Denote by y (j ) = (y1 , . . . , yn ) the state of the memory of S at the j -th step of 2n computation, j = 0, . . . , t. Define an encoding function E : {0, 1}n {0, 1}2 as follows: E (x) = H ad(x), . . . , H ad(x), i.e., E is just the Hadamard code repeated 2n times. The decoding function D : 2n {0, 1}2 {0, 1}n is defined as follows: to get D(x) split x into 2n blocks of length 2n ; decode each block using the Hadamard decoding; then for each position i = 1, . . . , n take the majority of the i-th bits in all 2n results. ^ We shall define the computation process so that at each step j the memory of S (j ) (j ) (j ) (j ) contains a value z = (z1 , . . . , zN ) which differers from E (y ) in at most N positions for = 1/214 . Note that this condition implies D(z (t) ) = y (t) . (j ) (j ) Let us split the internal states of the processors (z1 , . . . , zN ) into 2n blocks of (j ) (j ) size 2n and denote them b1 , . . . , b2n . We shall employ an (n, , 0 /2, 0 )-mixer M ix, where 0 = ( - )/7. Such a mixer exists for large enough = (0 ). We don't need it to be a linear mixer, so we can employ an expander with appropriate parameters. There are known constructions of effective expanders with required parameters, e.g. [12]. We describe the transformation from z (j ) to z (j +1) in four stages. (j ) Stage 1. Fix i {1, . . . , 2n }. For each {0, 1} get the block bM ix(i,) = (u1 ( ), . . . , u2k ( )) and compute the vector wi ( ) = (u
i1

( ) - u1 ( ), . . . , u

i2

n

( ) - u2n ( ))

9


(here for i, s {1, . . . , 2n } we denote by i s the bitwise sum of n-bits binary representations of i and s). For each position r = 1, . . . , 2n get the majority of the r-th (j ) bits in all wi ( ), {0, 1} . Denote by ci the obtained result (which is a vector in n {0, 1}2 ). (j ) Let us call a block zi harmed if it differs from H ad(y (j ) ) in more than 2n positions. We assumed that z (j ) differs from E (y (j ) ) in at most N position. Hence, (j ) there are at most 2n harmed locks zi . From Claim 2 it follows that for the fraction at least (1 - 0 ) of all indexes i (j ) (1 - 1/64) · 2 of blocks bM ix(i,) ( {0, 1} ) are not harmed. Note that if for some i at least the fraction (1 - 1/64) of blocks bM ix(i,) are not harmed then all but (j ) (j ) 4(1/64 + ) · 2n = 2n /8 bits in the resulted block ci are equal to yi . (j ) Stage 2. Fix i {1, . . . , 2n }. Let the block ci consists of bits (v1 , . . . , v2k ). For each r = 1, . . . , 2n calculate the majority in the sequence vM
(j ) ix(r, ) (j )

, {0, 1} ,

Denote the result vr . Set di = (v1 , . . . , v2k ). (j ) From Claim 1 it follows that if a block ci contains at least 7/8 · 2n bits equal to (j ) (j ) (j ) yi then in the corresponding block di at least (1 - 0 )2n bits are equal to yi . Of (j ) (j ) course, we guarantee nothing for a block di if in the corresponding ci more than (j ) 1/8 of all bits differ from yi . (j ) (j ) Stage 3. This stage is trivial: we just make a permutation of bits in (d1 , . . . , d2n ). (j ) For each l, m we get the l-th bit from cm and put it to the m-th position in the l-th (j ) (j ) block. Denote the result (f1 , . . . , f2n ). Stage 4. Assume that at the j -th step of the computation in the original circuit S the bit yi0 is modified: (j +1) (j +1) (j +1) y i0 = F (yi1 , yi2 ), where F is some boolean function. function F has only two arguments.) Fix i {1, . . . , 2n } and denote calculate y i0 ~ y i1 ~ y i2 ~ (W.l.o.g. we may assume that that the boolean fi
(j )

= (u1 , . . . , u2k ). For each q = 1, . . . , 2
q i q i q i
0 1 2

n

=u =u =u

-u -u -u

q q q

Then set q = F (yi1 , yi2 ) - yi0 , and calculate q = H ad(0, . . . , 0, q , 0, . . . , 0) (the ~~ ~ value q is placed at the i0 -th position). Further, get the q -th position of q and add it to the value uq . Denote the resulted block z (j +1) . Note that if d(j ) differs from H ad(y (j ) ) in 2n positions (for some fraction (0, 1)) then z (j +1) differs from H ad(y (j ) ) in at most 6 2n positions. Hence, the whole vector z (j +1) differs from E (y (j +1) ) in at most (0 + 60 + )2n 10


positions. Note that 70 + < , and we are done. (j ) In our construction each bit zi depends on O(1) bit from z well defined the transition rule z (j ) z (j +1) .

(j )

. Thus, we have

5

Conclusion

We proved that any parallel computation fulfilled on memory n in time t can be simulated by a reliable circuit with memory O(n log(nt)/ log log(nt)) in time O(t log log(tn)). Such a reliable circuit returns a correct result with high probability even if it is based on faulty elements (i.e., each element faults at any step with some small probability , and faults of different elements are independent). Our construction employs encoding based on the Hadamard code. Actually similar arguments can be applied for a code base on any other linear locally decodable code. For example, we can use the Reed-Muller code instead of the Hadamard code; then essentially the same construction provides a bit stronger bound: any computation which was done on non-faulty circuit with memory n in time t, can be simulated on faulty elements with memory O(n log(nt)/ logC log(nt)), where the constant C can be made arbitrarily large. By this method, we cannot obtain much better bounds (like O(n)), because for any linear locally decodable error correcting code the codeword length must be exponential in the block length [13]. Thus, the main question, which remains open, is if reliable polynomial computations can be fulfilled on memory O(n). Our second result, which concerns computations resistant to an adversary who can corrupt at each step some fraction of memory cells, seems quite weak. We presented a construction with exponential blow-up of the memory. Again, the proved bound cannot be essentially improved with our method, because it is based on a linear locally decodable error correcting code. Remind that if we want just to store some information (without computations), this can be done with a constant blow-up of the memory, even if at each step an adversary corrupts some fraction of memory cells [2]. To our knowledge, there are no results achieving polynomial blow-up of the memory for circuits computing an arbitrary function and tolerating a constant fraction of processors being corrupted at every step. In [9] this problem was solved only for a special class of boolean functions. Thus, the second important open question is if any computation can be made resistant to an adversary, with linear or at least polynomial increasing of the memory. Another interesting question is if a linear (m, , , )-mixer can be effectively constructed in time poly(2m ). If such a construction exists, the proof of Theorem 2 can be made effective.

References
[1] J. von Neuman. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In C. Shannon and J. McCarthy, editors, Automata Studies. Princeton University Press, 1956.

11


[2] A.V. Kuznetsov. Information storage in a memory assembled from unreliable components. Problems of Information Transmission. vol. 9(3), 1973, pp. 254­ 264. [3] R. L. Dobrushin, S. L. Ortyukov. Upper bound for the redundancy of selfcorrecting arrangement of unreliable functional elements. Problems for Information Transmission, vol. 13(1), 1977, pp. 203-218. [4] R. L. Dobrushin, S. L. Ortyukov. Lower bound on the redundancy of selfcorrecting arrangement of unreliable functional elements. Problems for Information Transmission, vol. 13(1), 1977, pp. 201-208. [5] N. Pippenger. On Networks of Noisy gates. In Proc. of the 26-th IEEE FOCS Symposium, 1985, pp. 30­38. [6] N. Pippenger, G.D. Stamoulis, J.N. Tsitsikilis. On a lower bound on for the redundancy of reliable networks with noisy gates. IEEE Trans. Inform. Theory, vol. 37(3), 1991, pp. 639-643. [7] R. Reischuk, B. Schmeltz. Reliable computation with noisy circuits and decision trees ­ a general n log n lower bound. In Proc. of the 32-th IEEE FOCS Symposium, 1991, pp. 602-611. ´ ´ [8] P. Gacs, A. Gal. Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates. IEEE Transactions Information Theory. vol. 40, 1994, pp. 579­ 583. ´ [9] A. Gal, M. Szegedy. Fault Tolerant Circuits and Probabilistically Checkable proofs. In Proc. of 10th Annual Structure in Complexity Theory Conference, 1995, pp. 65­73. [10] D. A. Spielman. Highly fault-Tolerant parallel Computation. Proc. of the 37-th IEEE FOCS Symposium, 1996, pp. 154-163. [11] A. Goldreich, A. Wigderson. Tiny Families of Functions with Random Properties: a Quality-Size Trade-off for Hashing. Random Struct. Algorithms 11(4), 1997, pp. 315-343. [12] O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag product, and new constant degree expanders. Annals of Mathematics, 155(1), 2002, pp. 157­187. [13] O. Goldreich, H.J. Karloff, L.J. Schulman, L. Trevisan. Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. IEEE Conference on Computational Complexity, 2002, 175-183. [14] P. Gacs. Lectures on Reliable Cellular Automata. http://www.cs.bu.edu/ gacs/papers/iv-eng.pdf

12


6

Appendix

Proof of Lemma 1: Chose a random mapping F : {0, 1}m â {0, 1} {0, 1}m and check that with high probability F is a linear (m, , , )-mixer. We assume that for all x {0, 1}m and u {0, 1} the value F (x, u) {0, 1}m is chosen at random (uniformly), and values for different points are independent. Let us bound the probability that a random F is not a linear mixer. Fix some A, B {0, 1}m . For each pair (x, u) A â {0, 1} the value F (x, u) belongs to B with probability |A|/2m . From the Chernoff bound we get Prob[ {(x, u) : x A, F (x, u) B }| - If |A| 2m , we get Prob[ {(x, u) : x A, F (x, u) B }| - 2 |A| · |B | > 2 |A|] < 2 · e- 2m
2 m+

2 |A| · |B | > 2 |A|] < 2e- 2m

2

| A| 2



2

As the values of F (x, u) are chosen at random independently, the values of G(x, u) are also random and independent. Hence, for the function G the same bound holds: Prob[ |{(x, u) : x A, G(x, u) B }| - 2 |A| · |B | > 2 |A|] < 2e- 2m
2 m+

2

Now sum up the probabilities above for all A, B . The total number of subsets in m {0, 1}m is 22 . Thus, a randomly chosen F is not a linear mixer with probability less than m 2 m+ 2 · (22 )2 4e-2 2 , which is less than 1 for large enough . Proof of Claim 1: Let us fix some B of size at most 2m /8. Assume the claim is false: suppose there exist 2m different elements x {0, 1}m such that for a randomly chosen u {0, 1} Probu [F (x, u) B ] 0.25 Let A be a set that contains exactly 2
m

points x as above. As F is a mixer, we have 2 2m · |B | + 2 2 2 2m
m

|{(x, u) : x A, F (x, u) B }| <

< ( /4) · 2

m+

On the other hand, we assumed that for each x A, for at least 0.25 · 2 points u {0, 1} the value F (x, u) is in B . Hence, |{(x, u) : x A, F (x, u) B }| 0.25 · 2
m+

,

and we get a contradiction. Proof of Lemma 2: Denote X1 = {0, 1}m1 and X2 = {0, 1}m2 . Let us fix some A, B X1 â X2 . Our aim is to evaluate the number of pairs (x, u) such that x A, u {0, 1}1 +2 , and F1 F2 (x, u) B . Let = (2 )2 . We use the following notation: 13


· for any u X1 let Au = {u v |v X2 , u v A}; · for any v X2 let Bv = {u v |u X1 , u v B }; · Ai = {x X1 |i |Ax |/2
m2 m2

< (i + 1) }; < (i + 1) }; Ax , i = 0, . . . , 1/ ;
i

· Bi = {x X1 |i |Bx |/2

^ · Ai = {u v A|u Ai } =
xA

^ · Bi = {u v B |v Bi } =
y B
i

By , i = 0, . . . , 1/ .

Step 1. First, we count the number of pairs (x, u) A â {0, 1}1 +2 such that x A and F (x, u) B . To evaluate the number of such pairs, we calculate for each ^ ^ i, j the number of pairs (x, u) such that x Ai and F (x, u) Bj , and then sum up these values. The first case: i, j 1/ , |Ai | 1 2m1 . Fix some integer i, j as above. At first, count the number of pairs (x, u) X1 â {0, 1}1 such that x Ai and F1 (x, u) Bj . As F1 is a mixer, |{(x, u) Ai â {0, 1}1 |F1 (x, u) Bj }| - Further, for any x Ai , y Bj we have |Ax | - i 2 and |Ay | - j 2m2 < 2m2 Note that the condition i > 1/ implies |Ax | 2 2m2 . As F2 is a mixer, we have |{(y , v ) Ax â {0, 1}2 |F2 (y , v ) By }| - ij 2m2 2 (i + 1) 2m2 +2 + O(1/i + 1/j ) · ij 2m2 +2 2 = 2 (i + 1) 2m2 +2 + O( ) · ij 2m2 +2 2
+2 2 m2

21 |Ai | · |Bj | 1 21 |Ai |. 2m1

< 2

m2



^ ^ Thus, the number of pairs (x, u) such that x Ai , u {0, 1}1 , and F (x, u) Bj is equal to |Ai | |Bj | · · ij 2 2m1 2m1
m1 +m2 +1 +2 2

(1 + O( )) + O(1 + 2 ) · 2

m1 +m2 +1 +2

The second case: |Ai | < 1 2m1 . For every i such that |Ai | < 1 2m1 |{(x, u) Ai â {0, 1}1 |F1 (x, u) B }| 1 2
m1 +m2 +1 +2

14


The index i ranges over 1, . . . , 1/ . Hence, ^ |{(x, u) Ai â{0, 1}
i,j : Ai <1 2
m1

1 +2

^ |F1 (x, u) Bj }| O(1 / )·2

m1 +m2 +1 +2

.

The third case: i < 1/ . If i < 1/ and x Ai we have |Ax | 2
0i<1/ ,j 0

m2

. Hence, 2
m2 +1 +2

^ |{(x, u) Ai â {0, 1}

1 +2

^ |F (x, u) Bj }| |X1 | ·

,

1 which less than 2m1 +m2 ++2 The fourth case: j < 1/ and i > 1/ . For i, j under those conditions and any x Ai and y Bj there are at most |Ax |22 + 2 |Ax |22 ( + 2 )2m2 +2 pairs (x, u) Ax â {0, 1}
0j <1/ , i>1/ 2

such that F2 (x, u) By . Thus,
1 +2

^ |{(x, u) Ai â{0, 1}

^ |F1 (x, u) Bj }| (2 + )·2

m1 +m2 +1 +2

Sum up the four cases above: |{(x, u) A â {0, 1}1 +2 |F1 (x, u) B }| = 21 +2 +m1 +m2 · (1 + O( )) · i,j >1/ and |Ai |1 2m 1 +2 +m1 +m2 +2 · (O((1 + 1 + 2 )/delta + ))) Step 2. Count the product |A| · |B |: |A| · |B | =
i,j >1/ 2(m1 +m2 ) | Ai | | B j | 2 m1 2 m2
1

ij

2

^^ |Ai ||Bj | = ^^ |Ai ||Bj | + O( ) · 2
i,j

2(m1 +m2 )

=
2(m1 +m2 )

2 2

· ·

| Ai | | B j | m m 2 12 1 i,j >1/

ij + O( ) · 2
| Ai | | B j | 2 m1 2 m1
m1

= · O(1 / + )

2(m1 +m2 )

i,j >1/ ,|Ai |1 2

ij + 2

2(m1 +m2 )

Step 3. From the bounds obtained in step 1 and step 2 we get |{(x, u) A â {0, 1} Obviously, if |A|
1 +2

|F1 (x, u) B }| = |A||B | · 2(1 +2 )-(m1 +m2 ) + O((1 + 1 + 2 )/ + )) · 2

m1 +m2 +1 +2

2 2m1 +m+2+1 +2 , we have O((1 + 1 + 2 )/ + )) · 2m1 +m2 +1 +2 = O(((1 + 1 + 2 )/ + ))/2 ) · |A| Recall that = (2 )2 , and we get that F1 F2 is a (m1 + m2 , 1 + 2 , 2 , )-mixer + + for = O( 12122 + 2 ). 15