Transactional Application Protocol for Inconsistent Replication, or TAPIR, is a new protocol for linearizable distributed transactions built atop a new replication protocol that provides no consistency guarantees. TAPIR eliminates expensive coordination from the replication layer, yet provides the same transaction model and consistency semantics as existing transactional storage systems (e.g., Google's Spanner). It can commit transactions in a single round-trip, greatly improving both latency and throughput relative to existing systems.
Distributed systems are traditionally designed independently from the underlying network, making worst-case assumptions about its behavior. Such an approach is well-suited for the Internet, where one cannot predict what paths messages might take or what might happen to them along the way. However, many distributed applications are today deployed in data centers, where the network is more reliable, predictable, and extensible. We argue that in these environments, it is possible to co-design distributed systems with their network layer, and doing so can offer substantial benefits.
Modern datacenter applications struggle with the need to access thousands of servers while still providing a fast response time to the user. In these situations, the user's overall request is not complete until the slowest of the subrequests has completed, meaning that network services must offer not just low latency but predictable latency. We are developing operating system and application-level techniques for building systems with predictable response time.
Mobile/cloud applications are distributed over users' mobile devices and across back-end cloud servers around the world. As a consequence, application programmers now face deployment decisions that were visible only to designers of large-scale distributed systems in the past. These decisions include where data and computation should be located, what data should be replicated or cached and what data consistency level is needed. We are working on how to separate deployment from applications, while still giving application programmers control over performance trade-offs in the Sapphire project.
Arrakis is a new operating system that is designed around recent application and hardware trends: Applications are becoming so complex that they are miniature operating systems in their own right and are hampered by the existing OS protection model. On the hardware side, virtualization technologies and I/O devices have become increasingly sophisticated and take on more and more functions traditionally carried out by the operating system.
Existing gesture-recognition systems consume significant power and computational resources that limit how they may be used in low-end devices. We introduce AllSee, the first gesture-recognition system that can operate on a range of computing devices including those with no batteries. AllSee consumes three to four orders of magnitude lower power than state-of-the-art systems and can enable always-on gesture recognition for smartphones and tablets.
As computing devices become smaller and more numerous, powering them becomes more difficult; wires are often not feasible, and batteries add weight, bulk, cost, and require recharging/replacement that is impractical at large scales. Ambient backscatter communication solves this problem by leveraging existing TV and cellular transmissions, rather than generating their own radio waves. This novel technique enables ubiquitous communication where devices can communicate among themselves at unprecedented scales and in locations that were previously inaccessible.
WiSee is a novel interaction interface that leverages ongoing wireless transmissions in the environment (e.g., WiFi) to enable whole-home sensing and recognition of human gestures. Since wireless signals do not require line-of-sight and can traverse through walls, WiSee can enable whole-home gesture recognition using few wireless sources (e.g., a Wi-Fi router and a few mobile devices in the living room).
This project presents TIMO, the first WiFi receiver that can decode in the presence of high-power unknown cross-technology interference. Traditionally, researchers have addressed cross-technology interference by dynamically searching for and switching to unused frequencies. We approach the problem from a different perspective: can one operate in already used frequencies in the presence of potentially unknown interferers? We build a new cognitive framework for the unlicensed band which allows multi-antenna devices to work in used frequencies.
This project presents tamper-evident pairing, the first wireless pairing protocol that works in-band, with no pre-shared keys, and protects against MITM attacks. The main innovation is a new key exchange message constructed in a manner that ensures an adversary can neither hide the fact that a message was transmitted, nor alter its payload without being detected. Thus, any attempt by an adversary to interfere with the key exchange translates into the pairing devices detecting either invalid pairing messages or an unacceptable increase in the number of such messages.
Wireless communication has become an intrinsic part of modern implantable medical devices (IMDs). Recent work, however, has demonstrated that wireless connectivity can be exploited to compromise the confidentiality of IMDs’ transmitted data or to send unauthorized commands to IMDs—even commands that cause the device to deliver an electric shock to the patient. The key challenge in addressing these attacks stems from the difficulty of modifying or replacing already-implanted IMDs.
Collisions are a known problem in wireless networks. The existing approaches address this problem by designing techniques that avoid collisions. This project takes an alternate approach: Instead of trying to avoid collisions, lets embrace collisions. In particular, we present ZigZag decoding, a new WiFi receiver that decodes collisions. The core contribution of ZigZag is a new interference cancellation technique that does not make any assumptions of synchronization, large differences in power, or special codes.
In the future, new non-volatile memory technologies, such as phase-change memories and memristors, could change the assumptions underlying the design of current operating systems. We are examining the implications of new, fast non-volatile storage systems on OS mechanisms, functions, and properties, as described in our HotOS paper
. Faculty: Ceze and Levy.
We are pushing the limits of today’s distributed storage systems on several fronts. Scatter, a scalable peer-to-peer key-value storage system, preserves serializable consistency even under adverse conditions. Comet
is a distributed key-value store that lets clients inject snippets of code into storage elements, creating an active key-value store that greatly increases the power and range of applications that use distributed storage applications. Faculty: Anderson, Kohno, Krishnamurthy, Levy.
BotLab is a platform that continually monitors and analyzes the behavior of spam-oriented botnets. BoLab gathers multiple real-time streams of information about botnets taken from distinct perspectives. By combining and analyzing these streams, BoLab can produce accurate, timely, and comprehensive data about spam botnet behavior.
Increasing interconnectivity and data sharing can compromise data security and privacy. OneSwarm
is a peer-to-peer tool that provides users with explicit control over data privcy by letting them determine how data is to be shared. Instead of sharing data indiscriminately, data shared with OneSwarm can be made public, shared with friends, shared with some friends but not others, and so forth -- an approach we termed friend-to-friend (F2F) data sharing. Faculty: Anderson, Krishnamurthy.
Traceroute has long had a fundamental limitation that affects all these applications: it does not provide reverse path information. In this project, we address this longstanding limitation by building a reverse traceroute tool. Our tool provides the same information as traceroute, but for the reverse path, and it works in the same case as traceroute, when the user may lack control of the destination.
Computer systems are often difficult to understand and debug. A common way of gaining insight into a system's behavior is to inspect execution logs. Unfortunately, manual inspection of logs is an arduous process. We have developed a tool called Synoptic that helps developers by inferring a concise and accurate system model, in the form of a finite state machine, from execution logs. Synoptic processes the logs that most systems already produce, and it requires developers only to specify a set of regular expressions for parsing the logs. Synoptic models have been used to find new bugs, increase developer confidence in the correctness of their code, and help developers better understand their programs.
The SPARTA project (Static Program Analysis for Reliable Trusted Apps) is building a toolset to verify the security of mobile phone applications.
Current wireless networks do not meet the reasonable privacy expectations of their users. We are: exploring user perceptions and the current state of privacy, investigating link-layer protocols that preserve greater privacy ((SlyFi)
, tracking the personal information exposed by applications, and examining privacy at the wireless layer by shaping RF regions. Faculty: Wetherall, Kohno.
Mobile devices are easily lost or stolen, compromising data and privacy. We have designed a new file system for mobile devices, called Keypad, which provides an audit trail that indicates which files were (or were not) accessed following device loss and lets users disable file reading post-loss, even in the absence of network connectivity. A Keypad paper was presented at the EuroSys Conference, April 2011 and won the Best Student Paper Award. Faculty: Gribble, Kohno, Levy.
Nondeterministic execution inherent in multithreaded programs severely complicates debugging, testing, and replication. We have proposed a new OS abstraction, called Deterministic Process Groups (DPGs), to ensure fully deterministic (repeatable) execution of arbitrary, unmodified multithreaded programs. We have also developed dOS
, a Linux-based implementation of DPGs. Faculty: Ceze, Gribble.
The Web has evolved far beyond its original role as a hypertext document delivery system. Today's Web browser increasingly resembles an operating system, in that it executes rich, interactive programs that communicate with cloud-based services.