Distributed information storage
J.R. Roche · Medical Entomology and Zoology · 1992
Information is distributed in many different applications. In conventional parallel processing, for example, data is distributed in order to speed up computation. We consider the less-studied problem of distributing data among different sites for fault-tolerance. The primary example that we consider involves storing information on a network of disks so that the information can be recovered reliably even when some of the disks fail. The techniques developed in this thesis apply equally well, however, to problems in which communication links can fail and information packets can be lost. Using techniques from Galois field theory and network flow theory, we show how to store information at different sites with an absolute minimum of redundancy so as to prevent any loss of data if several sites become inaccessible. We allow the different sites to have different storage capacities and to be arranged in a variety of network topologies. The theoretical results on reliable information storage derived for general networks can be specialized to a particular configuration of disks that is widely used in practice. Although the information storage scheme for this configuration is simple in principle, there are practical difficulties because of the need to update parity-check blocks continually as data blocks are modified. For the setup above, the delay between reading a parity block and writing its updated value back onto the disk can seriously degrade the performance of a disk array. We analyze a technique called floating parity track that dramatically reduces the average delay between reading and writing a parity block. We find that the delay can typically be reduced by a factor of thirty in return for a slight decrease in storage efficiency.