Spring 2008

Because most random mutations to functionally important regions of DNA reduce fitness, these changes usually disappear over time in a process known as negative selection. From its unusually high conservation between species, it is immediately evident that at least 5% of the human genome has been under negative selection during most of mammalian evolution, and is hence likely to be functionally important. Protein-coding genes and structural RNA genes stand out among the negatively selected regions because of their distinctive pattern of restricted DNA base substitutions, insertions and deletions. However, most of the DNA under negative selection in mammalian genomes, and indeed vertebrate genomes in general, does not appear to be part of protein-coding genes, and shares no sequence similarity with any DNA in the genomes of invertebrates. Experimental evidence suggests that many of these unclassified functional elements serve to regulate genes involved in embryonic development.

Overlaid on the background of negative selection, we occasionally see a short segment of widely conserved DNA that has rapidly changed in a particular lineage, suggesting possible positive selection for a modified function in that lineage. The most dramatic example of this in the last 5 million years of human evolution occurs in a previously unstudied RNA gene expressed in the developing cerebral cortex, known as Human Accelerated Region 1 (HAR1). This gene is turned on only in a select set of neurons, during the time in fetal development when these neurons orchestrate the formation of the substantially larger cortex of the human brain. It will be many years before the biology of such examples is fully understood, but right now we relish the opportunity to get a first peek at the molecular tinkering that transformed our animal ancestors into humans.

In particular, Bayesian methods, based on the work of Reverend Thomas Bayes in the 1700s, describe how probabilities can be used to represent the degrees of belief of a rational agent. Bayesian methods work best when they are applied to models that are flexible enough to capture to complexity of real-world data. Recent work on non-parametric Bayesian methods provides this flexibility. I will touch upon key developments in the field, including Gaussian processes, Dirichlet processes, and the Indian buffet process (IBP). Focusing on the IBP, I will describe how this can be used in a number of applications such as collaborative filtering, bioinformatics, cognitive modelling, independent components analysis, and causal discovery. Finally, I will outline the main challenges in the field: how to develop new models, new fast inference algorithms, and compelling applications.

This talk describes a more principled approach to stabilizing Internet routing. We identify general approaches to achieve stability, and quantify their inherent tradeoffs with other objectives via upper and lower bounds. I will describe Stable Route Selection (StaRS), a new approach which uses flexibility in route selection to improve stability without sacrificing availability. Simulation and experimental results show that StaRS improves stability and end-to-end reliability while deviating only slightly from preferred routes, and closely approaching our theoretical lower bound. These results indicate that StaRS is a promising, easily deployable way to safely stabilize Internet routing.

StaRS’s stability improvements are enabled by dramatic heterogeneity in route failure patterns. I will present the case that StaRS is an instance of a much more general principle: that heterogeneity — variation in reliability, processing speed, bandwidth, or other metrics — should quite often be viewed as an advantage. This thesis is supported by practical and theoretical results in a variety of settings including distributed hash tables, overlay multicast, and job scheduling.

This talk presents recent work on understanding, detecting, and exposing concurrency bugs. I will first present two techniques that detect concurrency bugs from the angle of programmers’ synchronization intention. The first one is AVIO (technology transfer to Intel). AVIO automatically infers programmers’ atomicity intentions from correct execution. It detects violations to the inferred intentions and reports concurrency bugs. The second technique is MUVI. MUVI automatically infers variable correlation relationship from the source code and detects unsynchronized concurrent accesses to correlated variables. During this talk, I will also briefly discuss some findings from our characteristics study of real-world concurrency bugs. These findings have motivated the above bug detection work and inspired us to improve concurrent program testing.

Much of the challenge in building secure applications stems from the fact that real systems are constantly evolving, and that most programmers are not security-conscious, resulting in code rife with bugs that cause security vulnerabilities. Instead of trying to fix all code, this talk will argue that we should protect data, by controlling how it can move through the system. The key insight is that data protection cuts across layers: any piece of data in an application can also be viewed as memory or files by the OS, or as physical pages by the hardware. Consequently, even data in buggy applications can be protected by the OS or by hardware, despite the latter two being at a much lower level of abstraction.

In particular, I will first describe how a low-level information flow control mechanism can be provided by a small OS kernel, hardware, or network protocol, and then show how the same mechanism can be used throughout the system to enforce security policies ranging from those traditionally found in Unix to those that can ensure the privacy of user data in a web server built from largely untrusted code.

I will demonstrate multiple modes of network customization that this design allows, including topology and buffering resources. This single polymorphic network fabric can be configured to mimic the topology and performance of optimally designed application-specific networks with no appreciable overhead. This network is not only a critical enabler of brick and mortar-based designs, but has broad applicability to any chip requiring an on-chip network. When used with brick and mortar, however, low-cost, high-performance custom chips can become a reality.

A key design principle of Mace is to separate each service algorithm from the implementation mechanics (serialization, dispatch, synchronization, etc.), debugging code (logging and property testing), and its utility services (lower-level services providing a specified interface). Our experience indicates that precisely because Mace imposes limits on the design structure of distributed systems, it supports the implementation of a wide variety of high-level supporting tools, including model checking, simulation, live debugging, and visualization.

Mace is fully operational, has been in development for four years, and has been used to build a wide variety of Internet-ready distributed systems. This talk will describe both the Mace programming language design and MaceMC, the first model checker that can find liveness violations in unmodified systems implementations.

I will first describe how we can build more robust systems using a new trusted primitive called Attested Append-Only Memory (A2M). We trade off assumptions on trusted components for improved Byzantine fault bounds of safety and liveness. I will then present a way of characterizing the complexity of general networked systems. I will describe a metric based on distributed state dependencies, and apply it to routing and classical distributed systems.

The Unmanaged Internet Architecture (UIA) is a suite of design principles and experimental protocols that provide robust, efficient global connectivity among mobile devices while relying for configuration only on simple, intuitive management concepts. UIA uses “personal names” rather than traditional global names as handles for accessing personal devices remotely. Users assign these personal names via an ad hoc device introduction process requiring no central allocation. Once assigned, personal names bind securely to the global identities of their target devices independent of network location. Each user manages one namespace, shared among all the user’s devices and always available on each device. Users can also name other users to share resources with trusted acquaintances. Devices with naming relationships automatically arrange connectivity when possible, both in ad hoc networks and using global infrastructure when available. We built a prototype implementation of UIA that demonstrates the utility and feasibility of these design principles. The prototype includes an overlay routing layer that leverages the user’s social network to provide robust connectivity in spite of network failures and asymmetries such as NATs, a new transport protocol implementing a novel stream abstraction that more effectively supports the highly parallelized and media-oriented applications demanded on mobile devices, and a flexible security framework based on proof-carrying authorization (PCA) that provides “plug-in” interoperability with existing secure naming and authentication systems.

Antiquity is a distributed storage system designed for these sorts of challenging environments. It maintains data securely, consistently, and with high availability in a dynamic wide-area environment. At the core of the system is a novel secure log structure that permits Antiquity to guarantee the integrity of stored data, even under extreme stress. Data is replicated on multiple servers in a manner that ensures that it can be retrieved later even when some replicas are inaccessible. Moreover, unlike prior fault-tolerant systems, the Antiquity fault-tolerance protocols can handle high levels of node churn, regenerating data on the fly when necessary to handle faults ranging from server outages to Byzantine (malicious) attacks.

Further, I will present SMFS, a remote mirroring solution targeted for settings where high-speed high-latency links connect a pair of datacenters. SMFS provides strong disaster tolerance guarantees with asynchronous performance-mirroring response times are more typical of high-speed LAN setting. Not only does the approach provide reliability through mirroring, but there are conditions under which it offers dramatic power savings. Longer term, we see SMFS and Antiquity as two examples of a family of innovative solutions addressing a range of demanding problems seen in turbulent, mission-critical, and power constrained settings.

First, I will present a hybrid transactional memory scheme. One major source of difficulty in writing parallel programs is implementing correct synchronization between threads. Locks are the most common synchronization mechanism but have a number of well-known pitfalls. Transactional memory is an alternative mechanism that makes parallel programming easier. Early transactional memory proposals were implemented either entirely in hardware or in software. Both approaches have their limitations. We proposed the first hybrid hardware/software transactional memory scheme that approaches the performance of a hardware scheme in the common case and gracefully falls back to a software scheme when a transaction exceeds the capability of the hardware.

Second, I will present an architectural proposal that supports fine grained parallelism. To harness the parallelism on a CMP, applications must expose their thread-level parallelism to the hardware. One common approach to doing this is to decompose a program into parallel “tasks” and allow an underlying software layer to schedule these tasks to different threads. Software task scheduling can provide good parallel performance as long as tasks are large compared to the software overheads. However, a significant number of RMS applications have small tasks for which software task schedulers achieve only limited parallel speedups. This work proposed a hardware technique to accelerate dynamic task scheduling on scalable CMPs. This proposal has relatively simple hardware and delivers close to optimal performance of a number of RMS benchmarks with fine-grained parallelism.