Algebraic Decoding for Design Fault Tolerant Algorithms

Abstract: In this talk we will discuss a generalization of the decoding of Reed Solomon codes to fault tolerant computer algebra algorithms. The use case is the resolution of large polynomial coefficient linear systems via evaluation interpolation (PLS), that have as solution a vector of rational functions. For that purpose, a server, in charge of solving the system, delegates the evaluation process to nodes, which compute the evaluation step in a parallel way. The server therefore has a number of evaluated data and can proceed with interpolation to find the solution. In the case of untrusted nodes, the server could receive erroneous evaluations and find itself in the same case of a decoder If the server can handle it, the algorithm is said to be «Fault Tolerant». In this talk we will first see how starting from the key equations defined on the algebraic codes, it is possible to reconstruct the solution of PLSwE and we will deal with the problem of the minimum redundancy by exploiting the structure of the vector solution on one side, and the interleaving techniques on correcting codes on the other.