Output-sensitive decoding for redundant residue systems
Output-sensitive decoding for redundant residue systems
复制标题
冗余残差系统的输出敏感解码
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Thomas Stalinski
中科院分区：
文献类型：
--
作者：
M. Khonji;Clément Pernet;Jean;Thomas Roche;Thomas Stalinski
我们研究基于算法的容错技术，用于基于中国剩余定理的分布式计算中的恶意错误。该描述适用于通过整数或多项式在字段上的多项式计算。它通过GAO提出的REED所罗门解码算法统一了冗余残留数系统和冗余多项式系统的方法。我们提出了有关扩展欧几里得算法的应用的几种变化，其中误差校正率是自适应的。研究了一些改进，包括使用各种标准终止欧几里得算法，以及使用半GCD技术的加速度。当输入中有一些冗余时，在符合误差校正的步骤中，商序列中的差距会符合差异，从而实现了早期终止并行计算。证明实验可以比较这些方法。
We study algorithm based fault tolerance techniques for supporting malicious errors in distributed computations based on Chinese remainder theorem. The description holds for both computations with integers or with polynomials over a field. It unifies the approaches of redundant residue number systems and redundant polynomial systems through the Reed Solomon decoding algorithm proposed by Gao. We propose several variations on the application of the extended Euclid algorithm, where the error correction rate is adaptive. Several improvements are studied, including the use of various criterions for the termination of the Euclidean Algorithm, and an acceleration using the Half-GCD techniques. When there is some redundancy in the input, a gap in the quotient sequence is stated at the step matching the error correction, which enables early termination parallel computations. Experiments are shown to compare these approaches.