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.

EFFECT OF OFF-STOICHIOMETRY AND TERNARY ADDITIONS ON PLANAR FAULT ENERGIES IN Ni3Al

First principles calculations were done to evaluate the lattice parameter, cohesive energy and stacking fault energies of ordered gamma' (Ll(2)) precipitates in superalloys as a function of composition. It was found that addition of Ti and Ta lead to an increase in lattice parameter and decrease in cohesive energy, while Ni antisites had the opposite effect. Ta and Ti addition to stoichiometric Ni3Al resulted in an initial increase in the energies of APB((111)), CSF(111), APB((001)) and SISF(111). However, at higher concentrations, the fault energies decreased. Addition of Ni antisites decreased the energy of all four faults monotonically. A model based on nearest neighbor bonding was used for Ni-3(Al, Ta), Ni-3(Al, Ti) and Ni-3(Al, Ni) pseudo-binary systems and extended to pseudo- ternary Ni-3(Al, Ta, Ni) and Ni-3(Al, Ti, Ni) systems. Recipes were developed for predicting lattice parameters, cohesive energies and fault energies in pseudo- ternary systems on the basis of coefficients derived from simpler pseudobinary systems. The model predictions were found to be in good agreement with first principles calculations for lattice parameters, cohesive energies, and energies of APB((111)) and CSF(111).

Whales, dolphins, and porpoises of the western North Atlantic: a guide to their identification

This is an identification guide for cetaceans (whales, dolphins, and porpoises). It was designed to assist laypersons in identifying cetaceans encountered in the western North Atlantic Ocean and was intended for use by ongoing cetacean observer programs. This publication includes sections on identifying cetaceans at sea as well as stranded animals on shore. Species accounts are divided by body size and presence or lack of a dorsal fin. Appendices cover tags used on cetacean species; how to record and report cetacean observations at see and for stranded cetaceans; and a list of contacts for reporting cetacean strandings. (Document pdf contains 183 pages - file takes considerable time to open)

Remote Sensing of Giant Reed with QuickBird Satellite Imagery

QuickBird high resolution (2.8 m) satellite imagery was evaluated for distinguishing giant reed ( Arundo donax L.) infestations along the Rio Grande in southwest Texas. (PDF has 5 pages.)

Water Temperatures and Climatological Conditions South of New England, 1974-83

From 1974 through 1983, we conducted monitoring to provide the first long-term, year-round record of sea water temperatures south of New England from surface to bottom, and from nearshore to the continental slope. Expendable bathythermograph transects were made approximately monthly during the ten years by scientists and technicians from numerous institutions, working on research vessels that traversed the continental shelf off southern New England. Ten-year (1974-83) means and variability are presented for coastal and bottom water temperatures, for mid-shelf water column temperatures, and for some atmospheric and oceanographic conditions that may influence shelf and upper-slope water temperatures. Possible applications of ocean temperature monitoring to fishery ecology are noted. Some large departures from mean conditions are discussed; particularly notable during the decade were the response of water temperatures to the passage of Gulf Stream warm-core rings, and the magnitude and persistence of shelf-water cooling associated with air temperatures in three successive very cold winters (1976-77, 1977-78, and 1978-79). (PDF file contains 51 pages.)

Part I. Energy straggling of ^4He below 2.0 MeV in Al, Ni, Au and Pt. Part II. Studies of the Ti-W metallization system on Si

Part I.

In recent years, backscattering spectrometry has become an important tool for the analysis of thin films. An inherent limitation, though, is the loss of depth resolution due to energy straggling of the beam. To investigate this, energy straggling of ⁴He has been measured in thin films of Ni, Al, Au and Pt. Straggling is roughly proportional to square root of thickness, appears to have a slight energy dependence and generally decreases with decreasing atomic number of the adsorber. The results are compared with predictions of theory and with previous measurements. While Ni measurements are in fair agreement with Bohr's theory, Al measurements are 30% above and Au measurements are 40% below predicted values. The Au and Pt measurements give straggling values which are close to one another.

Part II.

MeV backscattering spectrometry and X-ray diffraction are used to investigate the behavior of sputter-deposited Ti-W mixed films on Si substrates. During vacuum anneals at temperatures near 700°C for several hours, the metallization layer reacts with the substrate. Backscattering analysis shows that the resulting compound layer is uniform in composition and contains Ti, Wand Si. The Ti:W ratio in the compound corresponds to that of the deposited metal film. X-ray analyses with Reed and Guinier cameras reveal the presence of the ternary Ti_xW_(1-x)Si₂ compound. Its composition is unaffected by oxygen contamination during annealing, but the reaction rate is affected. The rate measured on samples with about 15% oxygen contamination after annealing is linear, of the order of 0.5 Å per second at 725°C, and depends on the crystallographic orientation of the substrate and the dc bias during sputter-deposition of the Ti-W film.

Au layers of about 1000 Å thickness were deposited onto unreacted Ti-W films on Si. When annealed at 400°C these samples underwent a color change,and SEM micrographs of the samples showed that an intricate pattern of fissures which were typically 3µm wide had evolved. Analysis by electron microprobe revealed that Au had segregated preferentially into the fissures. This result suggests that Ti-W is not a barrier to Au-Si intermixing at 400°C.

Algebraic Techniques in Coding Theory: Entropy Vectors, Frames, and Constrained Coding

The study of codes, classically motivated by the need to communicate information reliably in the presence of error, has found new life in fields as diverse as network communication, distributed storage of data, and even has connections to the design of linear measurements used in compressive sensing. But in all contexts, a code typically involves exploiting the algebraic or geometric structure underlying an application. In this thesis, we examine several problems in coding theory, and try to gain some insight into the algebraic structure behind them.

The first is the study of the entropy region - the space of all possible vectors of joint entropies which can arise from a set of discrete random variables. Understanding this region is essentially the key to optimizing network codes for a given network. To this end, we employ a group-theoretic method of constructing random variables producing so-called "group-characterizable" entropy vectors, which are capable of approximating any point in the entropy region. We show how small groups can be used to produce entropy vectors which violate the Ingleton inequality, a fundamental bound on entropy vectors arising from the random variables involved in linear network codes. We discuss the suitability of these groups to design codes for networks which could potentially outperform linear coding.

The second topic we discuss is the design of frames with low coherence, closely related to finding spherical codes in which the codewords are unit vectors spaced out around the unit sphere so as to minimize the magnitudes of their mutual inner products. We show how to build frames by selecting a cleverly chosen set of representations of a finite group to produce a "group code" as described by Slepian decades ago. We go on to reinterpret our method as selecting a subset of rows of a group Fourier matrix, allowing us to study and bound our frames' coherences using character theory. We discuss the usefulness of our frames in sparse signal recovery using linear measurements.

The final problem we investigate is that of coding with constraints, most recently motivated by the demand for ways to encode large amounts of data using error-correcting codes so that any small loss can be recovered from a small set of surviving data. Most often, this involves using a systematic linear error-correcting code in which each parity symbol is constrained to be a function of some subset of the message symbols. We derive bounds on the minimum distance of such a code based on its constraints, and characterize when these bounds can be achieved using subcodes of Reed-Solomon codes.

Decoding cosets of first-order Reed-Muller code

Proper encoding of transmitted information can improve the performance of a communication system. To recover the information at the receiver it is necessary to decode the received signal. For many codes the complexity and slowness of the decoder is so severe that the code is not feasible for practical use. This thesis considers the decoding problem for one such class of codes, the comma-free codes related to the first-order Reed-Muller codes.

A factorization of the code matrix is found which leads to a simple, fast, minimum memory, decoder. The decoder is modular and only n modules are needed to decode a code of length 2ⁿ. The relevant factorization is extended to any code defined by a sequence of Kronecker products.

The problem of monitoring the correct synchronization position is also considered. A general answer seems to depend upon more detailed knowledge of the structure of comma-free codes. However, a technique is presented which gives useful results in many specific cases.