PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Chessa S., Maestrini P. Robust distributed storage of residue encoded data. In: IEEE Transactions on Information Theory, vol. 58 (12) pp. 7280 - 7294. IEEE Transactions on Information Theory, 2012.
 
 
Abstract
(English)
We consider a problem where a physical quantity is repeatedly measured by replicated devices, yielding a stream of numerical data. Data are stored within the measuring devices and sporadically retrieved by a user. To avoid data losses due to large data streams with insufficient memory, the data are split into frag- ments, each of which is a compressed encoding of a number in the stream, and different fragments are stored in different, repli- cated devices. The devices are not allowed to communicate with each other, and they produce the local streams of fragments from independent measurements. Given the independence of measure- ments, the fragments are corrupted by independent errors, which are likely to be small integers, although errors of unbounded mag- nitude may also occur due to failures or to interferences. As de- vices may fail, or communication may be unreliable, the user may be unable to download fragments from some of the replicated de- vices, leading to fragment erasures. Our approach to the problem is to encode the data in a Residue Number System with Nonpair- wise-Prime Moduli, named D-RNS-NPM. With  moduli and residue digits, every replicated device is tied to a different modulus, with which it produces and stores a residue digit (i.e., a fragment) from the local measurement. Assuming an upper bound  , with , to the number of erasures, we show that the D-RNS-NPM guarantees the reconstruction of any number from a subset of at least    fragments. If fragments bear errors, whose magnitude is unrestricted for at most one error and upper bounded by a small for the others, reconstruction is within an approximation of   , and this property is retained when errors cannot be detected due to the unbounded error multiplicity. The time complexity of the decoding algorithm is polynomial. This problem appears to be rel- evant in wireless sensor networks, and an application in this area is envisioned.
URL: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6293891&contentType=Journals+%26+Magazines&searchField%3DSearch_All%26queryText%3DRobust+distributed+storage+of+residue+encoded+data
DOI: 10.1109/TIT.2012.2216937
Subject Arithmetic residue codes
Data fragmentation and dispersal
Erasure codes
Wireless sensor networks (WSNs)
E.4 CODING AND INFORMATION THEORY


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional