On erasure coding for distributed storage and streaming communications

The work presented in this thesis revolves around erasure correction coding, as applied to distributed data storage and real-time streaming communications.

First, we examine the problem of allocating a given storage budget over a set of nodes for maximum reliability. The objective is to find an allocation of the budget that maximizes the probability of successful recovery by a data collector accessing a random subset of the nodes. This optimization problem is challenging in general because of its combinatorial nature, despite its simple formulation. We study several variations of the problem, assuming different allocation models and access models, and determine the optimal allocation and the optimal symmetric allocation (in which all nonempty nodes store the same amount of data) for a variety of cases. Although the optimal allocation can have nonintuitive structure and can be difficult to find in general, our results suggest that, as a simple heuristic, reliable storage can be achieved by spreading the budget maximally over all nodes when the budget is large, and spreading it minimally over a few nodes when it is small. Coding would therefore be beneficial in the former case, while uncoded replication would suffice in the latter case.

Second, we study how distributed storage allocations affect the recovery delay in a mobile setting. Specifically, two recovery delay optimization problems are considered for a network of mobile storage nodes: the maximization of the probability of successful recovery by a given deadline, and the minimization of the expected recovery delay. We show that the first problem is closely related to the earlier allocation problem, and solve the second problem completely for the case of symmetric allocations. It turns out that the optimal allocations for the two problems can be quite different. In a simulation study, we evaluated the performance of a simple data dissemination and storage protocol for mobile delay-tolerant networks, and observed that the choice of allocation can have a significant impact on the recovery delay under a variety of scenarios.

Third, we consider a real-time streaming system where messages created at regular time intervals at a source are encoded for transmission to a receiver over a packet erasure link; the receiver must subsequently decode each message within a given delay from its creation time. For erasure models containing a limited number of erasures per coding window, per sliding window, and containing erasure bursts whose maximum length is sufficiently short or long, we show that a time-invariant intrasession code asymptotically achieves the maximum message size among all codes that allow decoding under all admissible erasure patterns. For the bursty erasure model, we also show that diagonally interleaved codes derived from specific systematic block codes are asymptotically optimal over all codes in certain cases. We also study an i.i.d. erasure model in which each transmitted packet is erased independently with the same probability; the objective is to maximize the decoding probability for a given message size. We derive an upper bound on the decoding probability for any time-invariant code, and show that the gap between this bound and the performance of a family of time-invariant intrasession codes is small when the message size and packet erasure probability are small. In a simulation study, these codes performed well against a family of random time-invariant convolutional codes under a number of scenarios.

Finally, we consider the joint problems of routing and caching for named data networking. We propose a backpressure-based policy that employs virtual interest packets to make routing and caching decisions. In a packet-level simulation, the proposed policy outperformed a basic protocol that combines shortest-path routing with least-recently-used (LRU) cache replacement.

Rate and Microstructure Effects on the Dynamics of Carbon Nanotube Foams

Soft hierarchical materials often present unique functional properties that are sensitive to the geometry and organization of their micro- and nano-structural features across different lengthscales. Carbon Nanotube (CNT) foams are hierarchical materials with fibrous morphology that are known for their remarkable physical, chemical and electrical properties. Their complex microstructure has led them to exhibit intriguing mechanical responses at different length-scales and in different loading regimes. Even though these materials have been studied for mechanical behavior over the past few years, their response at high-rate finite deformations and the influence of their microstructure on bulk mechanical behavior and energy dissipative characteristics remain elusive.

In this dissertation, we study the response of aligned CNT foams at the high strain-rate regime of 10² - 10⁴ s^-1. We investigate their bulk dynamic response and the fundamental deformation mechanisms at different lengthscales, and correlate them to the microstructural characteristics of the foams. We develop an experimental platform, with which to study the mechanics of CNT foams in high-rate deformations, that includes direct measurements of the strain and transmitted forces, and allows for a full field visualization of the sample’s deformation through high-speed microscopy.

We synthesize various CNT foams (e.g., vertically aligned CNT (VACNT) foams, helical CNT foams, micro-architectured VACNT foams and VACNT foams with microscale heterogeneities) and show that the bulk functional properties of these materials are highly tunable either by tailoring their microstructure during synthesis or by designing micro-architectures that exploit the principles of structural mechanics. We also develop numerical models to describe the bulk dynamic response using multiscale mass-spring models and identify the mechanical properties at length scales that are smaller than the sample height.

The ability to control the geometry of microstructural features, and their local interactions, allows the creation of novel hierarchical materials with desired functional properties. The fundamental understanding provided by this work on the key structure-function relations that govern the bulk response of CNT foams can be extended to other fibrous, soft and hierarchical materials. The findings can be used to design materials with tailored properties for different engineering applications, like vibration damping, impact mitigation and packaging.

Influence of money upon the social organization

The extraordinary importance that has been attached to money throughout the ages may be appreciated when such modern writers as Alexander Delmar suggest that the history of money is the history of civilization. While this view is not accepted by most writers of the subject, all are nevertheless agreed that money plays a role of enormous importance in the affairs of men. Even in the classics are found quotations which stress this importance of the pecuniary unit upon ethical as well as economic standards.

Organization and function of the phage Lambda chromosome

The process of prophage integration by phage λ and the function and structure of the chromosomal elements required for λ integration have been studied with the use of λ deletion mutants. Since att^φ, the substrate of the integration enzymes, is not essential for λ growth, and since att^φ resides in a portion of the λ chromosome which is not necessary for vegetative growth, viable λ deletion mutants were isolated and examined to dissect the structure of att^φ.

Deletion mutants were selected from wild type populations by treating the phage under conditions where phage are inactivated at a rate dependent on the DNA content of the particles. A number of deletion mutants were obtained in this way, and many of these mutants proved to have defects in integration. These defects were defined by analyzing the properties of Int-promoted recombination in these att mutants.

The types of mutants found and their properties indicated that att^φ has three components: a cross-over point which is bordered on either side by recognition elements whose sequence is specifically required for normal integration. The interactions of the recognition elements in Int-promoted recombination between att mutants was examined and proved to be quite complex. In general, however, it appears that the λ integration system can function with a diverse array of mutant att sites.

The structure of att^φ was examined by comparing the genetic properties of various att mutants with their location in the λ chromosome. To map these mutants, the techniques of heteroduplex DNA formation and electron microscopy were employed. It was found that integration cross-overs occur at only one point in att^φ and that the recognition sequences that direct the integration enzymes to their site of action are quite small, less than 2000 nucleotides each. Furthermore, no base pair homology was detected between att^φ and its bacterial analog, att^B. This result clearly demonstrates that λ integration can occur between chromosomes which have little, if any, homology. In this respect, λ integration is unique as a system of recombination since most forms of generalized recombination require extensive base pair homology.

An additional study on the genetic and physical distances in the left arm of the λ genome was described. Here, a large number of conditional lethal nonsense mutants were isolated and mapped, and a genetic map of the entire left arm, comprising a total of 18 genes, was constructed. Four of these genes were discovered in this study. A series of λdg transducing phages was mapped by heteroduplex electron microscopy and the relationship between physical and genetic distances in the left arm was determined. The results indicate that recombination frequency in the left arm is an accurate reflection of physical distances, and moreover, there do not appear to be any undiscovered genes in this segment of the genome.

SteelConverter and Caltech VirtualShaker: Rapid Nonlinear Cloud-Based Structural Model Conversion and Analysis

STEEL, the Caltech created nonlinear large displacement analysis software, is currently used by a large number of researchers at Caltech. However, due to its complexity, lack of visualization tools (such as pre- and post-processing capabilities) rapid creation and analysis of models using this software was difficult. SteelConverter was created as a means to facilitate model creation through the use of the industry standard finite element solver ETABS. This software allows users to create models in ETABS and intelligently convert model information such as geometry, loading, releases, fixity, etc., into a format that STEEL understands. Models that would take several days to create and verify now take several hours or less. The productivity of the researcher as well as the level of confidence in the model being analyzed is greatly increased.

It has always been a major goal of Caltech to spread the knowledge created here to other universities. However, due to the complexity of STEEL it was difficult for researchers or engineers from other universities to conduct analyses. While SteelConverter did help researchers at Caltech improve their research, sending SteelConverter and its documentation to other universities was less than ideal. Issues of version control, individual computer requirements, and the difficulty of releasing updates made a more centralized solution preferred. This is where the idea for Caltech VirtualShaker was born. Through the creation of a centralized website where users could log in, submit, analyze, and process models in the cloud, all of the major concerns associated with the utilization of SteelConverter were eliminated. Caltech VirtualShaker allows users to create profiles where defaults associated with their most commonly run models are saved, and allows them to submit multiple jobs to an online virtual server to be analyzed and post-processed. The creation of this website not only allowed for more rapid distribution of this tool, but also created a means for engineers and researchers with no access to powerful computer clusters to run computationally intensive analyses without the excessive cost of building and maintaining a computer cluster.

In order to increase confidence in the use of STEEL as an analysis system, as well as verify the conversion tools, a series of comparisons were done between STEEL and ETABS. Six models of increasing complexity, ranging from a cantilever column to a twenty-story moment frame, were analyzed to determine the ability of STEEL to accurately calculate basic model properties such as elastic stiffness and damping through a free vibration analysis as well as more complex structural properties such as overall structural capacity through a pushover analysis. These analyses showed a very strong agreement between the two softwares on every aspect of each analysis. However, these analyses also showed the ability of the STEEL analysis algorithm to converge at significantly larger drifts than ETABS when using the more computationally expensive and structurally realistic fiber hinges. Following the ETABS analysis, it was decided to repeat the comparisons in a software more capable of conducting highly nonlinear analysis, called Perform. These analyses again showed a very strong agreement between the two softwares in every aspect of each analysis through instability. However, due to some limitations in Perform, free vibration analyses for the three story one bay chevron brace frame, two bay chevron brace frame, and twenty story moment frame could not be conducted. With the current trend towards ultimate capacity analysis, the ability to use fiber based models allows engineers to gain a better understanding of a building’s behavior under these extreme load scenarios.

Following this, a final study was done on Hall’s U20 structure [1] where the structure was analyzed in all three softwares and their results compared. The pushover curves from each software were compared and the differences caused by variations in software implementation explained. From this, conclusions can be drawn on the effectiveness of each analysis tool when attempting to analyze structures through the point of geometric instability. The analyses show that while ETABS was capable of accurately determining the elastic stiffness of the model, following the onset of inelastic behavior the analysis tool failed to converge. However, for the small number of time steps the ETABS analysis was converging, its results exactly matched those of STEEL, leading to the conclusion that ETABS is not an appropriate analysis package for analyzing a structure through the point of collapse when using fiber elements throughout the model. The analyses also showed that while Perform was capable of calculating the response of the structure accurately, restrictions in the material model resulted in a pushover curve that did not match that of STEEL exactly, particularly post collapse. However, such problems could be alleviated by choosing a more simplistic material model.

I. Baryon-antibaryon phase transition at high temperature. II. Inclusive virtual photon-hadron reactions in the parton model

Part I

Present experimental data on nucleon-antinucleon scattering allow a study of the possibility of a phase transition in a nucleon-antinucleon gas at high temperature. Estimates can be made of the general behavior of the elastic phase shifts without resorting to theoretical derivation. A phase transition which separates nucleons from antinucleons is found at about 280 MeV in the approximation of the second virial coefficient to the free energy of the gas.

Part II

The parton model is used to derive scaling laws for the hadrons observed in deep inelastic electron-nucleon scattering which lie in the fragmentation region of the virtual photon. Scaling relations are obtained in the Bjorken and Regge regions. It is proposed that the distribution functions become independent of both q² and ν where the Bjorken and Regge regions overlap. The quark density functions are discussed in the limit x→1 for the nucleon octet and the pseudoscalar mesons. Under certain plausible assumptions it is found that only one or two quarks of the six types of quarks and antiquarks have an appreciable density function in the limit x→1. This has implications for the quark fragmentation functions near the large momentum boundary of their fragmentation region. These results are used to propose a method of measuring the proton and neutron quark density functions for all x by making measurements on inclusively produced hadrons in electroproduction only. Implications are also discussed for the hadrons produced in electron-positron annihilation.