Output-sensitive decoding for redundant residue systems

Majid Khonji 1 Clement Pernet 1, * Jean-Louis Roch 1, * Thomas Roche 1 Thomas Stalinski 1
* Corresponding author
1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : 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.
Liste complète des métadonnées

Contributor : Grégory Mounié <>
Submitted on : Friday, March 8, 2013 - 3:31:55 PM
Last modification on : Monday, February 18, 2019 - 1:24:08 PM




Majid Khonji, Clement Pernet, Jean-Louis Roch, Thomas Roche, Thomas Stalinski. Output-sensitive decoding for redundant residue systems. ISSAC'10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, 2010, New York, NY, United States. pp.265―272, ⟨10.1145/1837934.1837985⟩. ⟨hal-00798446⟩



Record views