Output-sensitive decoding for redundant residue systems

Majid Khonji 1 Clement Pernet 1, * Jean-Louis Roch 1, * Thomas Roche 1 Thomas Stalinski 1
* Auteur correspondant
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
Type de document :
Communication dans un congrès
ISSAC'10: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, 2010, New York, NY, United States. ACM, pp.265―272, 2010, 〈10.1145/1837934.1837985〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00798446
Contributeur : Grégory Mounié <>
Soumis le : vendredi 8 mars 2013 - 15:31:55
Dernière modification le : mercredi 11 avril 2018 - 01:54:14

Lien texte intégral

openaccess

Identifiants

Collections

INRIA | LIG_SRCPR | LIG_SRCPR_MOAIS | UGA | LIG | INRIA-RENGRE

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. ACM, pp.265―272, 2010, 〈10.1145/1837934.1837985〉. 〈hal-00798446〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

802

Contact


archive-ouverte@inria.fr