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.

New strategies for the total synthesis of aza-propellane natural products

The propellane alkaloids comprise a large class of natural products that possess varying degrees of structural complexity and biological activity. The earliest of these to be isolated was acutumine, a chlorinated alkaloid that has been shown to exhibit selective T-cell cytotoxicity and antiamnesic properties. Alternatively, the hasubanan family of natural products has garnered considerable attention from the synthetic community in part due to its structural similarities to morphine. While these alkaloids have been the subject of numerous synthetic studies over the last forty years, very few enantioselective total syntheses have been reported to date.

As part of a research program directed towards the synthesis of various alkaloid natural products, we have developed a unified strategy for the preparation of the hasubanan and acutumine alkaloids. Specifically, a highly diastereoselective 1,2-addition of organometallic reagents to benzoquinone-derived tert-butanesulfinimines was established, which provides access to enantioenriched 4-aminocyclohexadienone products. This methodology enabled the enantioselective construction of functionalized dihydroindolones, which were found to undergo intramolecular Friedel-Crafts conjugate additions to furnish the propellane cores of several hasubanan alkaloids. As a result of these studies, the first enantioselective total syntheses of 8-demethoxyrunanine and cepharatines A, C, and D were accomplished in 9-11 steps from commercially available starting materials.

More recent efforts have focused on applying the sulfinimine methodology to the synthesis of a more structurally complex propellane alkaloid, acutumine. Extensive studies have determined that a properly functionalized dihydroindolone undergoes a photochemical [2+2] cycloaddition followed by a lactone fragmentation/Dieckmann cyclization to establish the carbocyclic framework of the natural product. The preparation of more appropriately oxidized propellane intermediates is currently under investigation, and is anticipated to facilitate our synthetic endeavors toward acutumine.

Applications of frequency modulation interference cancellers to multiaccess communications systems

Cancellation of interfering frequency-modulated (FM) signals is investigated with emphasis towards applications on the cellular telephone channel as an important example of a multiple access communications system. In order to fairly evaluate analog FM multiaccess systems with respect to more complex digital multiaccess systems, a serious attempt to mitigate interference in the FM systems must be made. Information-theoretic results in the field of interference channels are shown to motivate the estimation and subtraction of undesired interfering signals. This thesis briefly examines the relative optimality of the current FM techniques in known interference channels, before pursuing the estimation and subtracting of interfering FM signals.

The capture-effect phenomenon of FM reception is exploited to produce simple interference-cancelling receivers with a cross-coupled topology. The use of phase-locked loop receivers cross-coupled with amplitude-tracking loops to estimate the FM signals is explored. The theory and function of these cross-coupled phase-locked loop (CCPLL) interference cancellers are examined. New interference cancellers inspired by optimal estimation and the CCPLL topology are developed, resulting in simpler receivers than those in prior art. Signal acquisition and capture effects in these complex dynamical systems are explained using the relationship of the dynamical systems to adaptive noise cancellers.

FM interference-cancelling receivers are considered for increasing the frequency reuse in a cellular telephone system. Interference mitigation in the cellular environment is seen to require tracking of the desired signal during time intervals when it is not the strongest signal present. Use of interference cancelling in conjunction with dynamic frequency-allocation algorithms is viewed as a way of improving spectrum efficiency. Performance of interference cancellers indicates possibilities for greatly increased frequency reuse. The economics of receiver improvements in the cellular system is considered, including both the mobile subscriber equipment and the provider's tower (base station) equipment.

The thesis is divided into four major parts and a summary: the introduction, motivations for the use of interference cancellation, examination of the CCPLL interference canceller, and applications to the cellular channel. The parts are dependent on each other and are meant to be read as a whole.

Design strategies for ultra-high efficiency photovoltaics

While concentrator photovoltaic cells have shown significant improvements in efficiency in the past ten years, once these cells are integrated into concentrating optics, connected to a power conditioning system and deployed in the field, the overall module efficiency drops to only 34 to 36%. This efficiency is impressive compared to conventional flat plate modules, but it is far short of the theoretical limits for solar energy conversion. Designing a system capable of achieving ultra high efficiency of 50% or greater cannot be achieved by refinement and iteration of current design approaches.

This thesis takes a systems approach to designing a photovoltaic system capable of 50% efficient performance using conventional diode-based solar cells. The effort began with an exploration of the limiting efficiency of spectrum splitting ensembles with 2 to 20 sub cells in different electrical configurations. Incorporating realistic non-ideal performance with the computationally simple detailed balance approach resulted in practical limits that are useful to identify specific cell performance requirements. This effort quantified the relative benefit of additional cells and concentration for system efficiency, which will help in designing practical optical systems.

Efforts to improve the quality of the solar cells themselves focused on the development of tunable lattice constant epitaxial templates. Initially intended to enable lattice matched multijunction solar cells, these templates would enable increased flexibility in band gap selection for spectrum splitting ensembles and enhanced radiative quality relative to metamorphic growth. The III-V material family is commonly used for multijunction solar cells both for its high radiative quality and for the ease of integrating multiple band gaps into one monolithic growth. The band gap flexibility is limited by the lattice constant of available growth templates. The virtual substrate consists of a thin III-V film with the desired lattice constant. The film is grown strained on an available wafer substrate, but the thickness is below the dislocation nucleation threshold. By removing the film from the growth substrate, allowing the strain to relax elastically, and bonding it to a supportive handle, a template with the desired lattice constant is formed. Experimental efforts towards this structure and initial proof of concept are presented.

Cells with high radiative quality present the opportunity to recover a large amount of their radiative losses if they are incorporated in an ensemble that couples emission from one cell to another. This effect is well known, but has been explored previously in the context of sub cells that independently operate at their maximum power point. This analysis explicitly accounts for the system interaction and identifies ways to enhance overall performance by operating some cells in an ensemble at voltages that reduce the power converted in the individual cell. Series connected multijunctions, which by their nature facilitate strong optical coupling between sub-cells, are reoptimized with substantial performance benefit.

Photovoltaic efficiency is usually measured relative to a standard incident spectrum to allow comparison between systems. Deployed in the field systems may differ in energy production due to sensitivity to changes in the spectrum. The series connection constraint in particular causes system efficiency to decrease as the incident spectrum deviates from the standard spectral composition. This thesis performs a case study comparing performance of systems over a year at a particular location to identify the energy production penalty caused by series connection relative to independent electrical connection.

Strategies for the Stereoselective Synthesis of Carbon Quaternary Centers via Transition Metal-Catalyzed Alkylation of Enolate Compounds

Notwithstanding advances in modern chemical methods, the selective installation of sterically encumbered carbon stereocenters, in particular all-carbon quaternary centers, remains an unsolved problem in organic chemistry. The prevalence of all-carbon quaternary centers in biologically active natural products and pharmaceutical compounds provides a strong impetus to address current limitations in the state of the art of their generation. This thesis presents four related projects, all of which share in the goal of constructing highly-congested carbon centers in a stereoselective manner, and in the use of transition-metal catalyzed alkylation as a means to address that goal.

The first research described is an extension of allylic alkylation methodology previously developed in the Stoltz group to small, strained rings. This research constitutes the first transition metal-catalyzed enantioselective α-alkylation of cyclobutanones. Under Pd-catalysis, this chemistry affords all–carbon α-quaternary cyclobutanones in good to excellent yields and enantioselectivities.

Next is described our development of a (trimethylsilyl)ethyl β-ketoester class of enolate precursors, and their application in palladium–catalyzed asymmetric allylic alkylation to yield a variety of α-quaternary ketones and lactams. Independent coupling partner synthesis engenders enhanced allyl substrate scope relative to allyl β-ketoester substrates; highly functionalized α-quaternary ketones generated by the union of our fluoride-triggered β-ketoesters and sensitive allylic alkylation coupling partners serve to demonstrate the utility of this method for complex fragment coupling.

Lastly, our development of an Ir-catalyzed asymmetric allylic alkylation of cyclic β-ketoesters to afford highly congested, vicinal stereocenters comprised of tertiary and all-carbon quaternary centers with outstanding regio-, diastereo-, and enantiocontrol is detailed. Implementation of a subsequent Pd-catalyzed alkylation affords dialkylated products with pinpoint stereochemical control of both chiral centers. The chemistry is then extended to include acyclic β-ketoesters and similar levels of selective and functional group tolerance are observed. Critical to the successful development of this method was the employment of iridium catalysis in concert with N-aryl-phosphoramidite ligands.