Output-sensitive decoding for redundant residue systems

Majid Khonji, Clément Pernet, Jean Louis Roch, Thomas Roche, Thomas Stalinski

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

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.

Original languageBritish English
Title of host publicationProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010
PublisherAssociation for Computing Machinery (ACM)
Pages265-272
Number of pages8
ISBN (Print)9781450301503
DOIs
StatePublished - 2010
Event2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010 - Munich, Germany
Duration: 25 Jul 201028 Jul 2010

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Conference

Conference2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010
Country/TerritoryGermany
CityMunich
Period25/07/1028/07/10

Keywords

  • Adaptive algorithms
  • Algorithm based fault tolerance
  • Early termination
  • Fast extended euclidean algorithm
  • Redundant residue number system

Fingerprint

Dive into the research topics of 'Output-sensitive decoding for redundant residue systems'. Together they form a unique fingerprint.

Cite this