Regenerating Codes for Distributed Storage Networks

In a storage system where individual storage nodes are prone to failure, the redundant storage of data in a distributed manner across multiple nodes is a must to ensure reliability. Reed-Solomon codes possess the reconstruction property under which the stored data can be recovered by connecting to any k of the n nodes in the network across which data is dispersed. This property can be shown to lead to vastly improved network reliability over simple replication schemes. Also of interest in such storage systems is the minimization of the repair bandwidth, i.e., the amount of data needed to be downloaded from the network in order to repair a single failed node. Reed-Solomon codes perform poorly here as they require the entire data to be downloaded. Regenerating codes are a new class of codes which minimize the repair bandwidth while retaining the reconstruction property. This paper provides an overview of regenerating codes including a discussion on the explicit construction of optimum codes.

Distributed Storage Codes With Repair-by-Transfer and Nonachievability of Interior Points on the Storage-Bandwidth Tradeoff

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any subset of k nodes within the n-node network. However, regenerating codes possess in addition, the ability to repair a failed node by connecting to an arbitrary subset of d nodes. It has been shown that for the case of functional repair, there is a tradeoff between the amount of data stored per node and the bandwidth required to repair a failed node. A special case of functional repair is exact repair where the replacement node is required to store data identical to that in the failed node. Exact repair is of interest as it greatly simplifies system implementation. The first result of this paper is an explicit, exact-repair code for the point on the storage-bandwidth tradeoff corresponding to the minimum possible repair bandwidth, for the case when d = n-1. This code has a particularly simple graphical description, and most interestingly has the ability to carry out exact repair without any need to perform arithmetic operations. We term this ability of the code to perform repair through mere transfer of data as repair by transfer. The second result of this paper shows that the interior points on the storage-bandwidth tradeoff cannot be achieved under exact repair, thus pointing to the existence of a separate tradeoff under exact repair. Specifically, we identify a set of scenarios which we term as ``helper node pooling,'' and show that it is the necessity to satisfy such scenarios that overconstrains the system.

Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary of nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. The four principal results of the paper are (a) the explicit construction of a class of MDS codes for d = n - 1 >= 2k - 1 termed the MISER code, that achieves the cut-set bound on the repair bandwidth for the exact repair of systematic nodes, (b) proof of the necessity of interference alignment in exact-repair MSR codes, (c) a proof showing the impossibility of constructing linear, exact-repair MSR codes for d < 2k - 3 in the absence of symbol extension, and (d) the construction, also explicit, of high-rate MSR codes for d = k+1. Interference alignment (IA) is a theme that runs throughout the paper: the MISER code is built on the principles of IA and IA is also a crucial component to the nonexistence proof for d < 2k - 3. To the best of our knowledge, the constructions presented in this paper are the first explicit constructions of regenerating codes that achieve the cut-set bound.

A simple vibrating reed apparatus for use at low temperatures

The authors report the design and construction of a very simple vibrating reed apparatus with automatic frequency locking capability where the resonance frequency and the internal friction can be recorded continuously as a function of temperature. The apparatus is particularly suitable for studies down to liquid helium temperatures or below.

Reed-Muller Canonical Forms in Multivalued Logic

Canonical forms for m-valued functions referred to as m-Reed-Muller canonical (m-RMC) forms that are a generalization of RMC forms of two-valued functions are proposed. m-RMC forms are based on the operations ?m (addition mod m) and .m (multiplication mod m) and do not, as in the cases of the generalizations proposed in the literature, require an m-valued function for m not a power of a prime, to be expressed by a canonical form for M-valued functions, where M > m is a power of a prime. Methods of obtaining the m-RMC forms from the truth vector or the sum of products representation of an m-valued function are discussed. Using a generalization of the Boolean difference to m-valued logic, series expansions for m-valued functions are derived.

A Note on Minimal Reed-Muller Canonical Forms of Switching Functions

A nonexhaustive procedure for obtaining minimal Reed-Muller canonical (RMC) forms of switching functions is presented. This procedure is a modification of a procedure presented earlier in the literature and enables derivation of an upper bound on the number of RMC forms to be derived to choose a minimal one. It is shown that the task of obtaining minimal RMC forms is simplified in the case of symmetric functions and self-dual functions.

On Generalized Reed-Muller Expansions

The generalized Reed-Muller expansions of a switching function are generated using a single Boolean matrix and step-by-step shifting of the principal column.

The Treewidth of MDS and Reed-Muller Codes

The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parameterization of the maximum-likelihood decoding complexity for linear codes. In this paper, we show the surprising fact that for maximum distance separable codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code, is defined to be the least constraint complexity (or branch complexity) of any of its trellis realizations. From this, we obtain exact expressions for the treewidth of these codes, which constitute the only known explicit expressions for the treewidth of algebraic codes.

On the treewidth of MDS and Reed-Muller codes

The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parametrization of the maximum-likelihood decoding complexity for linear codes. In this paper, we compute exact expressions for the treewidth of maximum distance separable codes, and first- and second-order Reed-Muller codes. These results constitute the only known explicit expressions for the treewidth of algebraic codes.

Novel ultrahigh resolution silverless photothermal imaging in obliquely deposited amorphous Se-Ge films

A new photothermal imaging process which utilizes no silver has been demonstrated in obliquely deposited Se-Ge films. Band-gap irradiation of Se-Ge films has been found to give rise to phases of the type SeOx, GeO, and Se as borne by x-ray initiated Auger electron spectroscopy and x-ray photoelectron spectroscopy. Annealing of SeOx leads to the formation of SeO2. The large (several orders of magnitude) difference in vapor pressures of SeO2 and Se-Ge films results in differential evaporation of the films when annealed around 200 °C, thereby leading to imaging. Such a large contrast in evaporation rates between the exposed and unexposed regions has great potential applications in high resolution image storage and phase holography. Applied Physics Letters is copyrighted by The American Institute of Physics.

Regional Differences in the Influence of Irrigation on Climate

A global climate model experiment is performed to evaluate the effect of irrigation on temperatures in several major irrigated regions of the world. The Community Atmosphere Model, version 3.3, was modified to represent irrigation for the fraction of each grid cell equipped for irrigation according to datasets from the Food and Agriculture Organization. Results indicate substantial regional differences in the magnitude of irrigation-induced cooling, which are attributed to three primary factors: differences in extent of the irrigated area, differences in the simulated soil moisture for the control simulation (without irrigation), and the nature of cloud response to irrigation. The last factor appeared especially important for the dry season in India, although further analysis with other models and observations are needed to verify this feedback. Comparison with observed temperatures revealed substantially lower biases in several regions for the simulation with irrigation than for the control, suggesting that the lack of irrigation may be an important component of temperature bias in this model or that irrigation compensates for other biases. The results of this study should help to translate the results from past regional efforts, which have largely focused on the United States, to regions in the developing world that in many cases continue to experience significant expansion of irrigated land.

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). Let Delta = Delta(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K-n,K-n. Alon, McDiarmid and Reed observed that a'(K-p-1,K-p-1) = p for every prime p. In this paper we prove that a'(K-p,K-p) <= p + 2 = Delta + 2 when p is prime. Basavaraju, Chandran and Kummini proved that a'(K-n,K-n) >= n + 2 = Delta + 2 when n is odd, which combined with our result implies that a'(K-p,K-p) = p + 2 = Delta + 2 when p is an odd prime. Moreover we show that if we remove any edge from K-p,K-p, the resulting graph is acyclically Delta + 1 = p + 1-edge-colorable. (C) 2009 Elsevier B.V. All rights reserved.

Origin of anomalous photoinduced transformations in amorphous Ge-based chalcogenide thin films

Anomalous photoinduced transformations in amorphous Ge-based chalcogenide thin films are established as being due to photochemical modification of the surfaces, by photoemission studies. Mass measurements indicate that the giant thickness reduction on irradiation is predominantly due to the loss of material as a result of photogenerated volatile high vapor pressure oxide fractions on the surface. This extrinsic contribution contradicts the models of the phenomenon proposed so far, which are based purely on intrinsic structural transformations.

Investigation of surface activity and photoinduced diffusion of metals in solution deposited amorphous films of As2S3

Surface activity of solution deposited (SD) amorphous films of As2S3 has been investigated. Silver and copper are readily deposited on such films from appropriate aqueous ionic solutions. The metals diffuse into the films upon irradiation with energetic photons. Structure and properties of SD films have been investigated using electron microscopy, optical spectroscopy and differential scanning calorimetry. The amorphous films tend to crystallize upon metal diffusion. The stability of amorphous films, the deposition of metals on their active surfaces and the photo-induced diffusion may all be attributed to the presence or production of charged defects in amorphous chalcogenide films.

Rectangular universal cellular array

A rectangular universal cellular array consisting of cells having three inputs and one output is described. This array is based on the Reed-Muller canonical expansion of a switching function. Although the total number of external input pins required in this array is the same as that of a rectangular array proposed in the literature, the number of cells is very much less.