Reliable Computations Based on Locally Decodable Codes
Reliable Computations Based on Locally Decodable Codes
复制标题
基于本地可解码代码的可靠计算
DOI：
10.1007/11672142_44
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Andrei E. Romashchenko
中科院分区：
文献类型：
--
作者：
Andrei E. Romashchenko
研究了由D. Spielman提出的容错计算的编码模型。在该模型中，计算电路的输入和输出被视为纠错码中的单词。如果一个电路的输入是一个函数的编码参数，那么被解码的输出是该函数在给定参数上的值，那么我们就说这个电路正确地计算了某个函数。
We investigate the coded model of fault-tolerant computations introduced by D. Spielman. In this model the input and the output of a computational 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(nlogn / log log n) faulty processors in time O(tlog log n). Note that we get a 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 an 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 self-correcting procedure for an array of faulty processors.