Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage

Erasure coding techniques are used to increase the reliability of distributed storage systems while minimizing storage overhead. Also of interest is minimization of the bandwidth required to repair the system following a node failure. In a recent paper, Wu et al. characterize the tradeoff between the repair bandwidth and the amount of data stored per node. They also prove the existence of regenerating codes that achieve this tradeoff. In this paper, we introduce Exact Regenerating Codes, which are regenerating codes possessing the additional property of being able to duplicate the data stored at a failed node. Such codes require low processing and communication overheads, making the system practical and easy to maintain. Explicit construction of exact regenerating codes is provided for the minimum bandwidth point on the storage-repair bandwidth tradeoff, relevant to distributed-mail-server applications. A sub-space based approach is provided and shown to yield necessary and sufficient conditions on a linear code to possess the exact regeneration property as well as prove the uniqueness of our construction. Also included in the paper, is an explicit construction of regenerating codes for the minimum storage point for parameters relevant to storage in peer-to-peer systems. This construction supports a variable number of nodes and can handle multiple, simultaneous node failures. All constructions given in the paper are of low complexity, requiring low field size in particular.

Memory-based reasoning approach for pattern recognition of binary images

Template matching is concerned with measuring the similarity between patterns of two objects. This paper proposes a memory-based reasoning approach for pattern recognition of binary images with a large template set. It seems that memory-based reasoning intrinsically requires a large database. Moreover, some binary image recognition problems inherently need large template sets, such as the recognition of Chinese characters which needs thousands of templates. The proposed algorithm is based on the Connection Machine, which is the most massively parallel machine to date, using a multiresolution method to search for the matching template. The approach uses the pyramid data structure for the multiresolution representation of templates and the input image pattern. For a given binary image it scans the template pyramid searching the match. A binary image of N × N pixels can be matched in O(log N) time complexity by our algorithm and is independent of the number of templates. Implementation of the proposed scheme is described in detail.

Phase diagram and dielectric studies of binary organic materials

The phase equilibrium studies of organic system, involving resorcinol (R) and p-dimethylaminobenzaldehyde (DMAB), reveal the formation of a 1:1 molecular complex with two eutectics. The heat of mixing, entropy of fusion, roughness parameter, interfacial energy, and the excess thermodynamic functions were calculated based on enthalpy of fusion data determined via differential scanning calorimetric (DSC) method. X-ray powder diffraction studies confirm that the eutectics are not simple mechanical mixture of the components under investigation. The spectroscopic investigations (IR and NMR) suggest the occurrence of hydrogen bonding between the components forming the molecular complex. The dielectric measurements, carried out on hot-pressed addition compound (molecular complex), show higher dielectric constant at 320 K than that of individual components. The microstructural investigations of eutectic and addition compound indicate dendritic and faceted morphological features. (C) 2000 Elsevier Science B.V. All rights reserved.

A molecular theory of collective orientational relaxation in pure and binary dipolar liquids

A molecular theory of collective orientational relaxation of dipolar molecules in a dense liquid is presented. Our work is based on a generalized, nonlinear, Smoluchowski equation (GSE) that includes the effects of intermolecular interactions through a mean‐field force term. The effects of translational motion of the liquid molecules on the orientational relaxation is also included self‐consistently in the GSE. Analytic expressions for the wave‐vector‐dependent orientational correlation functions are obtained for one component, pure liquid and also for binary mixtures. We find that for a dipolar liquid of spherical molecules, the correlation function ϕ(k,t) for l=1, where l is the rank of the spherical harmonics, is biexponential. At zero wave‐vector, one time constant becomes identical with the dielectric relaxation time of the polar liquid. The second time constant is the longitudinal relaxation time, but the contribution of this second component is small. We find that polar forces do not affect the higher order correlation functions (l>1) of spherical dipolar molecules in a linearized theory. The expression of ϕ(k,t) for a binary liquid is a sum of four exponential terms. We also find that the wave‐vector‐dependent relaxation times depend strongly on the microscopic structure of the dense liquid. At intermediate wave vectors, the translational diffusion greatly accelerates the rate of orientational relaxation. The present study indicates that one must pay proper attention to the microscopic structure of the liquid while treating the translational effects. An analysis of the nonlinear terms of the GSE is also presented. An interesting coupling between the number density fluctuation and the orientational fluctuation is uncovered.

Electrical and Dielectric Behaviour at the Critical Point of Binary Liquids: Acetonitrile + Cyclohexane

The electrical capacitance and resistance of the binary liquid mixture cyclohexane + acetonitrile are measured in the one phase and two phase regions at spot frequencies between 5 kHz and 100 kHz. This sample has a very low gravity affected (∼0.6 mK) region. In one phase region the capacitance data show a sharp, ∼0.7% increase above background within 0.5 degrees of Tc whereas the resistance has a smooth increase of ∼1.5% above background in a (T−Tc) range of 4 degrees. Two phase values of capacitance and resistance from the coexisting phases are used to determine the critical parameters Tc (critical temperature), Rc (resistance at Tc) and Cc (capacitance at Tc). A precise knowledge of these parameters reduces the uncertainty on the critical exponent 0 for C and R. The one phase capacitance data fit to an (1 - α) exponent in a limited temperature range of 0.2 degrees. Resistance data strongly support an (1 - α) exponent over the entire 5 degree range.

Convolutional Codes for Network-Error Correction

In this work, we introduce convolutional codes for network-error correction in the context of coherent network coding. We give a construction of convolutional codes that correct a given set of error patterns, as long as consecutive errors are separated by a certain interval. We also give some bounds on the field size and the number of errors that can get corrected in a certain interval. Compared to previous network error correction schemes, using convolutional codes is seen to have advantages in field size and decoding technique. Some examples are discussed which illustrate the several possible situations that arise in this context.

An algorithm to detect linearly separable clusters of binary patterns

The clusters of binary patterns can be considered as Boolean functions of the (binary) features. Such a relationship between the linearly separable (LS) Boolean functions and LS clusters of binary patterns is examined. An algorithm is presented to answer the questions of the type: “Is the cluster formed by the subsets of the (binary) data set having certain features AND/NOT having certain other features, LS from the remaining set?” The algorithm uses the sequences of Numbered Binary Form (NBF) notation and some elementary (NPN) transformations of the binary data.

An algorithm to detect linearly separable clusters of binary patterns

The clusters of binary patterns can be considered as Boolean functions of the (binary) features. Such a relationship between the linearly separable (LS) Boolean functions and LS clusters of binary patterns is examined. An algorithm is presented to answer the questions of the type: “Is the cluster formed by the subsets of the (binary) data set having certain features AND/NOT having certain other features, LS from the remaining set?” The algorithm uses the sequences of Numbered Binary Form (NBF) notation and some elementary (NPN) transformations of the binary data.

On BCH codes over arbitrary integer rings

Bose-C-Hocquenghem (BCH) atdes with symbols from an arbitrary fhite integer ring are derived in terms of their generator polynomials. The derivation is based on the factohation of x to the power (n) - 1 over the unit ring of an appropriate extension of the fiite integer ring. lke eomtruetion is thus shown to be similar to that for BCH codes over fink flelda.

Critical behavior of electrical resistivity in polar + nonpolar binary liquid systems

The behavior of electrical resistivity in the critical region of three polar + nonpolar binary liquid systems CS2 +(CH3CO)2O, C6H12+(CH3CO)2O, and n‐C7H16+(CH3CO)2O is studied. For the mixtures with critical composition, the two phase region shows a conductivity behavior with σ1−σ2∼ (−ϵ)β with β?0.35. In the one phase region dR/dT has a singularity ϵ−b with b?0.35. A possible theory of the impurity conduction is given, which broadly explains these results. The possibility of dR/dT being positive or negative is also discussed.

Dispersion of resistivity anomalies in critical binary liquid systems

The critical resistivity in the binary liquid systems n-C7H16 + CH3OH and CS2 + CH3NO2 is measured from 10 Hz to 100 kHz. There is no noticeable effect of the frequency on the resistivity singularities. Thus any contribution from dielectric dispersion is not appreciable.

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.

Enhanced Pair Hydrophobicity in the Water-Dimethylsulfoxide (DMSO) Binary Mixture at Low DMSO Concentrations

We observe a surprisingly sharp increase in the pair hydrophobicity in the water climethylsulfoxide (DMSO) binary mixture at small DMSO concentrations, with the mole fraction of DMSO (x(D)) in the range 0.12-0.16. The increase in pair hydrophobicity is measured by an increase in the depth of the first minimum in the potential of mean force (PMF) between two methane molecules. However, this enhanced hydrophobicity again weakens at higher DMSO concentrations. We find markedly unusual behavior of the pure binary mixture (in the same composition range) in the diffusion coefficient of DMSO and in the local composition fluctuation of water, We find that, in the said composition range, the average coordination number of the methyl groups (of distinct DMSO) varies between 2.4 and 2.6, indicating the onset of the formation of a chain-like extended connectivity in an otherwise stable tetrahedral network comprising of water and DMSO molecules. We propose that the enhanced pair hydrophobicity of the binary mixture at low DMSO concentrations is due to the participation of the two methane molecules in the local structural order and the emerging molecular associations in the water-DMSO mixture.

Interdiffusion study in binary gold-tin system

Solid state reactive diffusion in binary Au-Sn system has been studied using the diffusion couple consisting of pure elements Au and Sn annealed in the temperature range of 180-100 degrees C for 25 h Interdiffusion zone consists of four intermetallic phases Au5Sn, AuSn, AuSn2, and AuSn4 Activation energy for parabolic growth constant and integrated diffusivity for each phase has been calculated to indicate about the possible mechanism for diffusion controlled growth process Parabolic growth constant of individual phases has also been compared Kirkendall marker plane position has been indicated in the interdiffusion zone and furthermore the ratio of intrinsic diffusivities of species has also been determined. (C) 2010 Elsevier Ltd. All rights reserved.