%{search_type} search results

Interactive computing has redefined the way that humans approach and solve complex problems. However, the slowdown of Moore's law, coupled with the massive increase in data volume and sophistication, has prevented some applications from running interactively on microcomputers. Tasks such as video processing, software compilation & testing, 3D rendering, simulations, and data analytics have turned into batch jobs running on large clusters, limiting our ability to tinker, iterate, and collaborate. Meanwhile, by offering an ocean of heterogeneous computing resources, cloud computing has provided us with a unique opportunity to bring interactivity to such applications. This dissertation presents my experiences in creating new systems and abstractions for large-scale interactive computing, where users can execute a wide range of resource-intensive tasks with low latency. My thesis is that commodity cloud platforms can be utilized as an accessible supercomputer-by-the-second for interactive execution of large jobs. By leveraging granular cloud services, users can burst to tens of thousands of parallel computations on demand for short periods of time. I will discuss my experience building such applications for massively burst-parallel video processing, 3D path tracing, software builds, and other tasks. First, I describe ExCamera, a system for low-latency video processing using thousands of tiny threads. ExCamera's core contribution is a video encoder intended for fine-grained parallelism that allows computation to be split into thousands of tiny tasks without harming compression efficiency. Next, I discuss R2E2, a highly scalable path tracer for 3D scenes with high complexity. R2E2's main contribution is an architecture for performing low-latency path-tracing of terabyte-scale scenes using serverless computing nodes in the cloud. This design allows R2E2 to leverage the unique strengths of hyper-elastic cloud platforms (e.g., availability of many CPUs/memory in aggregate) and mitigates their limitations (e.g., low per-node memory capacity and high latency inter-node communication). Finally, drawing on the experience of building burst-parallel applications like ExCamera, I describe gg, a framework designed to facilitate the implementation of burst-parallel algorithms on serverless platforms. gg specifies an intermediate representation that allows a diverse class of applications to be abstracted from the computing and storage platform, and leverage common services for dependency management, straggler mitigation, and scheduling. Using gg IR, the developers express their applications in terms of the relationships between code and data, while the framework carries the burden of efficiently executing them

Networking algorithms often perform sequential decision making under uncertainty: They observe a network path and decide, e.g., how many packets to send or what to put in them. The Internet presents a particularly challenging setting: performance varies across several orders of magnitude and changes with time, control is decentralized, each node observes only a noisy sliver of the overall system, and accurate simulators do not exist. Despite the recent progress in applying machine learning (ML) to networking research, sequential decision problems on the Internet continue to rely on hand-designed algorithms. Slow adoption of ML in these scenarios can be attributed to the requirement that control algorithms be not just performant, but also practical: robust, generalizable, real-time, and resource-efficient. Lack of research platforms for studying ML approaches in the real world exacerbates the problem. This dissertation presents the platforms and algorithms we developed to achieve practical ML in the context of video streaming and congestion control. We describe Puffer, a free, publicly accessible website that live-streams television channels and operates as a randomized experiment of adaptive bitrate (ABR) algorithms. As of June 2020, Puffer has attracted 120,000 real users and streamed 60 years of video across the Internet. Using Puffer, we developed an ML-based ABR algorithm, Fugu, that robustly outperformed existing schemes by learning in situ, on real data from its actual deployment environment. Next, we describe Pantheon, a community "training ground" for Internet congestion-control research. It allows network researchers to benefit from and contribute to a common set of benchmark algorithms, a shared evaluation platform, and a public archive of results. Pantheon has assisted four algorithms from other research groups in publishing at NSDI 2018, ICML 2019, and SIGCOMM 2020. It also enabled our own ML-based congestion-control algorithm, Indigo, which was trained to imitate expert congestion-control algorithms we created in emulation and achieved good performance over the real Internet

Shuffle is the operation of exchanging arbitrary data among a group of servers, and it is a fundamental communication primitive in distributed computing. In particular, shuffle has been shown to be a fundamental bottleneck to the scalability of flash bursts, a radically new paradigm in datacenter computing. Flash bursts use a large number of servers but for very short time intervals (as little as one millisecond), which makes it possible to run large-scale data-intensive computation within a few milliseconds. Flash bursts present three significant challenges to the design of a shuffle algorithm. First, it cannot use a centralized scheduler. Second, it needs to be efficient even under interference from competing workloads. Finally, it must be applicable to large clusters that don't provide full bisection bandwidth. This thesis presents a clean-slate shuffle algorithm that achieves optimal performance cross a wide range of workloads even under the demanding conditions of flash bursts. This algorithm schedules messages as ensembles to match sender and receiver bandwidths decentrally; it overcommits receiver downlinks to maintain high network utilization; it uses pro rata sliding windows to enforce a weighted max-min fair sharing policy; finally, it uses a lightweight global scheduling scheme to manage the bottleneck links in the network core without knowledge of the underlying network topology.

Hardware component databases are vital resources in designing electronics. These databases store information about hardware components that allow designers to find the components they need. However, creating detailed hardware databases requires hundreds of thousands of hours of manual data entry. As a result, existing databases are often proprietary, incomplete, and may have sporadic human data entry errors. Knowledge base construction (KBC) systems help automate the process of creating and populating structured databases and have been applied effectively to many domains. Knowledge base construction techniques reduce dependency on human input, making it faster, easier, and cheaper to build these databases. This dissertation presents a machine-learning-based approach for creating hardware component databases directly from manufacturers' published component datasheets. Extracting data directly from datasheets is challenging for three reasons. First, the data is relational in nature; accurate interpretation relies on non-local context. Second, datasheets are filled with technical jargon. Third, datasheets are PDFs, a format that decouples visual locality from locality within the document. These challenges illuminate why human input is required, but human input is error-prone, time-consuming, and expensive. Instead of relying solely on human input, the approach of using a rich data model, weak supervision, data augmentation, and multi-task learning in this dissertation presents a more automated alternative. When utilized effectively, these machine-learning techniques create large knowledge bases cheaply and in just days. This dissertation consists of three parts. First, it presents Fonduer, a novel knowledge base construction system for richly formatted data based on a multimodal data model and weak supervision. It motivates Fonduer by studying the challenging properties of richly formatted data like the PDF datasheets electronics manufacturers use to publish component specifications. These insights lead to developing the building blocks necessary to enable automated information extraction from hardware datasheets. Fonduer is validated across various domains beyond only hardware datasheets by creating large knowledge bases in days. Second, this dissertation shows how Fonduer can be used to build hardware component knowledge bases in practice. The multimodal information that Fonduer captures provides signals utilized in training data generation and the augmentation of deep learning models for multi-task learning. An evaluation of this approach on datasheets of three types of components achieves an average quality of 0.77 F1—quality comparable to existing human-curated knowledge bases. Third, this dissertation demonstrates the utility of Fonduer with end-to-end applications and empirical results applied to real-world use cases. Two end-to-end applications, the enhancement of product catalogs with thumbnail images and the analysis of electrical characteristics, demonstrate that hardware component knowledge bases created in days make hardware component selection easier. Together, these results show three things. First, it is possible to automate the generation of hardware component knowledge bases. Second, these generated knowledge bases can be of higher quality than existing human-curated knowledge bases. Finally, these higher-quality knowledge bases open the door to innovative applications and tools for designing electronics

This thesis explores how RF backscatter can serve as an indispensable tool for designing low-power sensor networks. Low-power techniques allow sensors to be deployed where there is insufficient power or communication infrastructure for traditional sensor nodes. RF backscatter communication consumes an order of magnitude less power than even Bluetooth Low Energy. This dissertation presents three projects that advanced the state-of-the-art in sensing systems that harness RF backscatter. The first two projects, FreeRider and BackCam, describe systems that can backscatter commodity WiFi signals. Instead of having to invest in special-purpose transceivers, we can harness WiFi radios that are already ubiquitous. FreeRider is a backscatter communication platform designed to operate on top of existing ISM-band networks, like 802.11 WiFi. BackCam~\cite{backcam} extends this work by adding a camera sensor to the tag and implementing an edge-based control system. Using RF backscatter makes communication cheap, which allows us to push image processing to the edge. The next project, RayTag, demonstrates how pairing backscatter tags with radars makes the target signal 100-10,000x stronger in amplitude compared to the strongest clutter signal. This allows for simultaneous detection and identification of multiple targets, which is useful for a variety of sensing applications. To demonstrate the potential of RayTag, I show that deploying backscatter tags underground can be used to accurately measure soil moisture. Though I focus on the evaluation of sensing soil moisture, RayTag is not a single-purpose sensing system. Rather, RayTag can be used to enhance a number of existing sensing tasks (e.g. localization) or enable entirely new applications. To that end, this thesis also presents detailed evaluations beyond underground contexts, as well as multiple examples of constructing link budgets. This dissertation further explores a renewable power source for underground backscatter tags. Many backscatter communication systems can harvest their operating power via RF, but this is not practical for underground systems because wet soil attenuates RF too much for harvesting circuits to operate. One potential source of energy are microbes in the soil. Microbial fuel cells (MFCs), sometimes also known as mud or soil batteries, accept electrons that are a byproduct of redox reactions catalyzed by electrogenic microbes naturally occurring in soil. This creates a potential difference across the cathode and anode, which provides a low-cost renewable source of power. In the future, this could allow underground backscatter tags to have an indefinite lifetime

For decades, developers have been productive writing software by composing optimized libraries and functions written by other developers. Though hardware trends have evolved significantly over this time---with the ending of Moore's law, the increasing ubiquity of parallelism, and the emergence of new accelerators---many of the common interfaces for composing software have nevertheless remained unchanged since their original design. This lack of evolution is causing serious performance consequences in modern applications. For example, the growing gap between memory and processing speeds means that applications that compose even hand-tuned libraries can spend more time transferring data through main memory between individual function calls than they do performing computations. This problem is even worse for applications that interface with new hardware accelerators such as GPUs. Though application writers can circumvent these bottlenecks manually, these optimizations come at the expense of programmability. In short, the interfaces for composing even optimized software modules are no longer sufficient to best use the resources of modern hardware. This dissertation proposes designing new interfaces for efficient software composition on modern hardware by leveraging algebraic properties intrinsic to software APIs to unlock new optimizations. We demonstrate this idea with three new composition interfaces. The first interface, Weld, uses a functional intermediate representation (IR) to capture the parallel structure of data analytics workloads underneath existing APIs, and enables powerful data movement optimizations over this IR to optimize applications end-to-end. The second, called split annotations (SAs), also focuses on data movement optimization and parallelization, but uses annotations on top of existing functions to define an algebra for specifying how data passed between functions can be partitioned and recombined to enable cross-function pipelining. The third, called raw filtering, optimizes data loading in data-intensive systems by redefining the interface between data parsers and query engines to improve CPU efficiency. Our implementations of these interfaces have shown substantial performance benefits in rethinking the interface between software modules. More importantly, they have also shown the limitations of existing established interfaces. Weld and SAs show that a new interface can accelerate data science pipelines by over 100x in some cases in multicore environments, by enabling data movement optimizations such as pipelining on top of existing libraries such as NumPy and Pandas. We also show that Weld can be used to target new parallel accelerators, such as vector processors and GPUs, and that SAs can enable these speedups even on black-box libraries without any library code modification. Finally, the I/O optimizations in raw filtering show over 9x improvements in end-to-end query execution time in distributed systems such as Spark SQL when processing semi-structured data such as JSON

Communication performance is a critical factor when building distributed systems; communication costs can account for a non-trivial fraction of an application's service time. This has motivated many advances in raw communication performance, including both increased throughput and decreased latency. Unfortunately, these efforts ignore a more fundamental drain on communication performance: today's most common communication patterns, which result from the use of Remote Procedure Calls (RPCs), are inefficient and create otherwise unnecessary communication. With a more flexible communication pattern, it is possible to eliminate unnecessary communication, reduce the number of network hops, and ultimately improve the end-to-end latency of distributed executions. To that end, this dissertation presents Distributed Procedure Call (DPC), a new communication primitive designed to support a "multi-hop" communication pattern for distributed systems. Multi-hop communication breaks the one-to-one mapping between requests and responses in traditional RPCs. With DPC, a server can delegate a request to one or more additional servers before responses are sent, forming a tree of requests. This allows DPC to reduce latency by eliminating messages and network hops. Compared to RPC, DPC can reduce end-to-end communication latency by 18% to 49% in a variety of applications without harming throughput. DPC makes it easy for applications to take advantage of multi-hop communication. DPC's simple and general-purpose abstraction allows applications to dynamically form distributed executions. Behind this abstraction, the DPC protocol manages the multi-hop communication, matching request and response messages, and providing DPC completion and failure detection. Furthermore, DPC can be implemented as a library. This shields applications from the complexities of multi-hop communication and allows applications to focus on the logic of their distributed execution. DPC gives developers a new tool to build and optimize distributed systems

For decades, legal and policy analysis of data privacy issues have tended to be informed by factual assumptions rather than rigorous empirics. The motivation for this dissertation is to recast these assumptions into a set of empirical computer science research questions. Decision makers are, in essence, relying on a set of heuristics to analyze data privacy issues. Are the assumptions behind those heuristics accurate, and what are the consequences of applying those heuristics? The first chapter of this dissertation examines third-party web tracking and advertising, an area that has vexed policymakers in both the United States and Europe. The chapter contributes new methodologies for measuring web tracking, including instrumenting an ordinary web browser and simulating user activity (FourthParty) and collecting tracking-related data directly from ordinary users (BrowserSurvey). The results include new perspectives on the web tracking marketplace, identification of numerous non-cookie tracking technologies, and evidence of inconsistent performance and usability from consumer control mechanisms. The chapter also presents a new design for privacy-preserving third-party advertising (Tracking Not Required) that would provide a specific privacy guarantee, would not require modifying browsers, and would be externally auditable. The second chapter analyzes the distinction between metadata and content, a concept that is foundational to surveillance law and policy in the United States and worldwide. The chapter contributes a new crowdsourcing methodology for studying telephone metadata privacy. It then uses a crowdsourced dataset to demonstrate that telephone metadata is densely interconnected, susceptible to re-identification, and enables highly sensitive inferences. The third chapter assesses data territoriality, another surveillance distinction that is shared by the United States and across the globe. Results from simulated browsing activity indicate that data territoriality is a poor fit for modern web architecture; Americans unknowingly send a large volume of domestic online activity outside the United States, and foreign citizens send a large volume of (from their perspective) domestic online activity into the United States. The conclusion considers the relationship between the computer science community and policymaking about data privacy. It suggests how computer scientists can and must play a greater role in government decision making, to ensure that policy and law reflect the best available privacy science.

Many large-scale key-value storage systems sacrifice features like secondary indexing and/or strong consistency in favor of scalability or performance. This limits the ease and efficiency of application development on such systems. Implementing secondary indexing in a large-scale memory based system is challenging because the goals for low latency, high scalability, strong consistency and high availability often conflict with each other. This dissertation shows how a large-scale key-value storage system can be extended to provide secondary indexes while meeting those goals. The resulting architecture is called Scalable Low-Latency Indexes for a Key-Value Store, or SLIK. It extends a standard key-value store to enable multiple secondary keys for each object and allows lookups and range queries on these keys via secondary indexes. SLIK allows indexes to be partitioned and distributed independently of the data in tables in order to ensure scalability. Locating objects and corresponding index entries on different servers can lead to potential consistency issues. However, SLIK provides strong consistency guarantees using a lightweight ordered write approach. While SLIK stores indexes in DRAM to enable low latency, it ensures that the index information is durable and quickly recovered using backups in case of crashes. This design was implemented in RAMCloud, a distributed in-memory key-value storage system. This implementation performs indexed reads in 11--13 μs and writes in 30--37 μs, which is approximately twice the latency of basic non-indexed reads and writes in RAMCloud. It supports indexes spanning thousands of nodes, and yields linear scalability for throughput.

The Internet of Things describes the phenomenon of connecting low-resource edge devices to the Internet. This phenomenon, while exciting, uncovers safety, performance, and flexibility challanges for the low-resource computers. In particular, the microcontrollers that power these devices lack some of the hardware features and memory resources that enable multiprogrammable systems. Accordingly, microcontroller-based operating systems have not provided important features like fault isolation, dynamic memory allocation, and flexible concurrency. However, the Internet of Things changes these devices into software platforms, rather than single purpose devices, requiring multiprogramming features. This dissertation describes Tock, a new operating system for low-power platforms, that takes advantage of the limited hardware-protection mechanisms of contemporary microcontrollers as well as the type-safe features of the Rust programming language to provide a multiprogramming environment for microcontrollers. Tock isolates software faults, provides memory protection, and efficiently manages memory for dynamic application workloads written in any language. It achieves this while retaining the dependability requirements of long-running applications. The trade-off between extensibility, safety, and performance is long standing in operating systems. More specifically, prior systems in the research have attempted to use language type safety to replace, or augment, hardware-based isolation mechanisms in the kernel. However, these systems used garbage collected languages, generally viewed as too resource-heavy for kernel programming in production systems. Tock's use of Rust shows that, given a type-safe language with sufficient control of memory and processor resources, language-based approaches can be _more_ efficient than hardware. Moreover, Tock's use in academia and industry show that this approach is practical in real-world deployments.

In the past decade, systems that use probabilistic proofs in real-world applications have seen explosive growth. These systems build upon some of the crown jewels of theoretical computer science---interactive proofs, probabilistically checkable proofs, and zero-knowledge proofs---to solve problems of trust and privacy in a wide range of settings. This dissertation describes three built systems that answer questions ranging from "how can we build trustworthy hardware that uses untrusted components?" to "how can we improve the concrete efficiency of zero-knowledge proof systems?" Along the way, it discusses the pervasive challenges of efficiency, expressiveness, and scalability in this research area; one approach to addressing these challenges; and future directions that promise to bring this exciting technology to bear on an even wider range of applications