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.
Keywords : adaptive algorithms algorithm based fault tolerance early termination fast extended Euclidean algorithm redundant residue number system
Document type :
Conference papers
Liste complète des métadonnées
https://hal.inria.fr/hal-00798446
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

Identifiers

Collections

INRIA | LIG_SRCPR | LIG_SRCPR_MOAIS | UGA | LIG

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

1118

Contact


archive-ouverte@inria.fr