Coding for information storage

Storage systems are widely used and have played a crucial rule in both consumer and industrial products, for example, personal computers, data centers, and embedded systems. However, such system suffers from issues of cost, restricted-lifetime, and reliability with the emergence of new systems and devices, such as distributed storage and flash memory, respectively. Information theory, on the other hand, provides fundamental bounds and solutions to fully utilize resources such as data density, information I/O and network bandwidth. This thesis bridges these two topics, and proposes to solve challenges in data storage using a variety of coding techniques, so that storage becomes faster, more affordable, and more reliable.

We consider the system level and study the integration of RAID schemes and distributed storage. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code and are located in a (distributed) network. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With r redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In Part I we will show that the lower bound of 1/2 is achievable and that the result can be generalized to codes with arbitrary number of parities and optimal rebuilding.

We consider the device level and study coding and modulation techniques for emerging non-volatile memories such as flash memory. In particular, rank modulation is a novel data representation scheme proposed by Jiang et al. for multi-level flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. It eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. In order to decrease the decoding complexity, we propose two variations of this scheme in Part II: bounded rank modulation where only small sliding windows of cells are sorted to generated permutations, and partial rank modulation where only part of the n cells are used to represent data. We study limits on the capacity of bounded rank modulation and propose encoding and decoding algorithms. We show that overlaps between windows will increase capacity. We present Gray codes spanning all possible partial-rank states and using only ``push-to-the-top'' operations. These Gray codes turn out to solve an open combinatorial problem called universal cycle, which is a sequence of integers generating all possible partial permutations.

How resources control aggression in Drosophila

How animals use sensory information to weigh the risks vs. benefits of behavioral decisions remains poorly understood. Inter-male aggression is triggered when animals perceive both the presence of an appetitive resource, such as food or females, and of competing conspecific males. How such signals are detected and integrated to control the decision to fight is not clear. Here we use the vinegar fly, Drosophila melanogaster, to investigate the manner in which food and females promotes aggression.

In the first chapter, we explore how food controls aggression. As in many other species, food promotes aggression in flies, but it is not clear whether food increases aggression per se, or whether aggression is a secondary consequence of increased social interactions caused by aggregation of flies on food. Furthermore, nothing is known about how animals evaluate the quality and quantity of food in the context of competition. We show that food promotes aggression independently of any effect to increase the frequency of contact between males. Food increases aggression but not courtship between males, suggesting that the effect of food on aggression is specific. Next, we show that flies tune the level of aggression according to absolute amount of food rather than other parameters, such as area or concentration of food. Sucrose, a sugar molecule present in many fruits, is sufficient to promote aggression, and detection of sugar via gustatory receptor neurons is necessary for food-promoted aggression. Furthermore, we show that while food is necessary for aggression, too much food decreases aggression. Finally, we show that flies exhibit strategies consistent with a territorial strategy. These data suggest that flies use sweet-sensing gustatory information to guide their decision to fight over a limited quantity of a food resource.

Following up on the findings of the first chapter, we asked how the presence of a conspecific female resource promotes male-male aggression. In the absence of food, group-housed male flies, who normally do not fight even in the presence of food, fight in the presence of females. Unlike food, the presence of females strongly influences proximity between flies. Nevertheless, as group-housed flies do not fight even when they are in small chambers, it is unlikely that the presence of female indirectly increases aggression by first increasing proximity. Unlike food, the presence of females also leads to large increases in locomotion and in male-female courtship behaviors, suggesting that females may influence aggression as well as general arousal. Female cuticular hydrocarbons are required for this effect, as females that do not produce CH pheromones are unable to promote male-male aggression. In particular, 7,11-HD––a female-specific cuticular hydrocarbon pheromone critical for male-female courtship––is sufficient to mediate this effect when it is perfumed onto pheromone-deficient females or males. Recent studies showed that ppk23⁺ GRNs label two population of GRNs, one of which detects male cuticular hydrocarbons and another labeled by ppk23 and ppk25, which detects female cuticular hydrocarbons. I show that in particular, both of these GRNs control aggression, presumably via detection of female or male pheromones. To further investigate the ways in which these two classes of GRNs control aggression, I developed new genetic tools to independently test the male- and female-sensing GRNs. I show that ppk25-LexA and ppk25-GAL80 faithfully recapitulate the expression pattern of ppk25-GAL4 and label a subset of ppk23⁺ GRNs. These tools can be used in future studies to dissect the respective functions of male-sensing and female-sensing GRNs in male social behaviors.

Finally, in the last chapter, I discuss quantitative approaches to describe how varying quantities of food and females could control the level of aggression. Flies show an inverse-U shaped aggressive response to varying quantities of food and a flat aggressive response to varying quantities of females. I show how two simple game theoretic models, “prisoner’s dilemma” and “coordination game” could be used to describe the level of aggression we observe. These results suggest that flies may use strategic decision-making, using simple comparisons of costs and benefits.

In conclusion, male-male aggression in Drosophila is controlled by simple gustatory cues from food and females, which are detected by gustatory receptor neurons. Different quantities of resource cues lead to different levels of aggression, and flies show putative territorial behavior, suggesting that fly aggression is a highly strategic adaptive behavior. How these resource cues are integrated with male pheromone cues and give rise to this complex behavior is an interesting subject, which should keep researchers busy in the coming years.

Industrial democracy

Since the beginning of human relations, some of the more ambitious and more capable members of society have by various means found and practiced methods of exploiting the efforts of their fellowmen to their own personal interest. These individuals have been naturally gifted at organization and control and have been able to dominate their slower, less mentally active associates. It is a cumulative process, once having been started the act of further subjugation becoming easier and easier as the clever person gets more and more control over the other.