Research for Practice

  Download PDF version of this article PDF

Research for Practice: Distributed Transactions and Networks as Physical Sensors

Expert-curated Guides to the Best of CS Research


Peter Bailis, Irene Zhang, Fadel Adib

Research for Practice continues in its fourth installment by bringing you a pair of paper selections on distributed transactions and sensing with the aid of physical networks.

First, Irene Zhang delivers a whirlwind tour of recent developments in distributed concurrency control. If you thought distributed transactions were prohibitively expensive, Irene’s selections may prompt you to reconsider: the use of atomic clocks, clever replication protocols, and new means of commit ordering all improve performance at scale.

Second, Fadel Adib provides a fascinating look at using computer networks as physical sensors. It turns out that the radio waves passing through our environment and bodies are subtly modulated as they do so. As Fadel’s selection shows, new techniques for sensing and interpreting these modulations allow us to perform tasks previously reserved for science fiction: seeing through walls, performing gesture recognition, and monitoring breathing.

As always, we have provided open access to the ACM Digital Library for the relevant citations from these selections so you can dig into and fully appreciate the research papers in each.

During the next several installments of Research for Practice, we’ll continue our journey through the varied landscape of computer science research areas. In the meantime, we welcome your continued feedback and suggestions for topics. Enjoy! —Peter Bailis

Distributed Transactions

By Irene Zhang

Distributed transactions make it easier for programmers to reason about the correctness of their applications in modern data centers, where both concurrency and failures happen at scale. Distributed storage systems and databases with ACID (atomicity, consistency, isolation, durability) guarantees help programmers by ensuring that operations from committed transactions are never lost, operations from concurrent transactions do not interleave, and all or none of the operations from a transaction persist, despite failures of application servers or storage servers.

Unfortunately, distributed transactions have long been thought to be prohibitively expensive. In modern storage systems, which partition data for scalability and replicate data for fault tolerance, distributed transactions need coordination at every level: on each storage server, across replicas, and across partitions.

Three recent research papers presented here have made significant strides in reducing the coordination needed for distributed transactions, making them more efficient at every level. The first reduces the cost of read-only transactions across geo-distributed data centers using atomic clocks. The second reduces the cost of read-write transactions across replicas by eliminating consistency from the replication protocol. The last reduces the cost of transactions on each storage server using a modular concurrency-control mechanism. Taken together, these papers demonstrate that it is possible to provide distributed transactions with low cost, even at Google scale.

High-performance Read-only Transactions with Atomic Clocks

Corbett, J. C., et al. 2012. Spanner: Google’s globally-distributed database. In Proceedings of Operating Systems Design and Implementation (OSDI);

http://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf.

Linearizable transactions are useful for programmers because they behave in a way that is easy to understand: there is a single global transaction ordering and it matches the order in which the transactions commit. Unfortunately, linearizable transactions are expensive, especially in a globally distributed system, because they require every transaction to coordinate with every other transaction, including read-only transactions.

Spanner gets around this problem by using loosely synchronized clocks. Every storage server synchronizes with an atomic clock in the data center, and they estimate the clock skew between servers based on the drift between the atomic clocks. Then Spanner assigns every read-write transaction a timestamp and waits out the clock skew to ensure that the timestamp is in the past, allowing read-only transactions to read at their local current time without any coordination. This technique comes with a caveat, however: if their estimate of the clock skew is off, Spanner no longer guarantees a linearizable transaction ordering.

High-performance Read-write Transactions with Unordered Replication

Zhang, I., et al. 2015. Building consistent transactions with inconsistent replication. Symposium on Operating Systems Principles (SOSP); https://homes.cs.washington.edu/~arvind/papers/tapir.pdf.

While Spanner makes read-only transactions less expensive, it does not reduce the cost of read-write transactions. This selection makes the observation that there is wasted work in existing databases when committing transactions: both the transaction protocol and the replication protocol enforce a strong ordering. Thus, it is possible to eliminate the coordination across replicas by using a completely unordered replication protocol and enforce only a linearizable ordering of committed transactions.

The paper introduces an unordered, consensus-based replication protocol, called inconsistent replication, and defines TAPIR (Transactional Application Protocol for Inconsistent Replication) to run on top of it. TAPIR also uses loosely synchronized clocks but as a performance optimization, not a correctness requirement, avoiding Spanner’s caveat. TAPIR represents one option in the design space, but many other possibilities also make for promising lines of research.

High-performance Transactions With Modular Concurrency Control

Xie, C., et al. 2015. High-performance ACID via modular concurrency control. Symposium on Operating Systems Principles (SOSP); http://sigops.org/sosp/sosp15/current/2015-Monterey/263-xie-online.pdf.

While much cross-server coordination has been eliminated, transactions can still require significant coordination at each storage server, increasing performance cost. For example, Spanner requires locking, which blocks concurrent transactions that access the same keys, and TAPIR requires optimistic concurrency control, which causes aborts under high contention.

The distributed database system Callas seeks to reduce this cost by grouping transactions based on performance characteristics and applying a concurrency-control mechanism that is best suited for each group. This is made possible through a novel two-tiered concurrency-control mechanism that locks across groups and leaves each one free to use any concurrency-control mechanism, including transaction chopping. The cool thing about the technique is that it can be applied to nondistributed databases as well, although it has the most impact in a distributed system and could probably even be recursively nested for more complex workloads.

Decreasing Costs are a reality

We need to rehabilitate the reputation of distributed transactions. They are powerful tools for application programmers, yet most avoid them because of their perceived cost. While transactional storage will always have a fundamental performance overhead, especially in a distributed environment, these papers show that the overhead need not be exorbitant. Even better, each of these papers points to a promising avenue of research to further reduce the cost of distributed transactions in practical ways, hinting at the possibility that someday programmers will no longer have to choose between distributed transactions and performance.

Networks as Physical Sensors

By Fadel Adib

Can Wi-Fi signals allow us to see through walls? For many years, humans have fantasized about X-ray vision and played with the concept in comic books and sci-fi films. This section highlights recent research that has unlocked the exciting potential of wireless signals and expanded the role of wireless networks, enabling them to deliver new services ranging from seeing through walls to noncontact sensing of heartbeats. To do so, this new research bridges state-of-the-art wireless techniques with human-computer interaction.

The concepts underlying this new line of research build on basic physical principles of RF (radio frequency) waves such as Wi-Fi. Specifically, as these waves travel in the wireless medium, they bounce off different objects—including the human body—before arriving at a receiver; hence, they carry information about the environment. The following selection of papers demonstrates how to extract and analyze this information, allowing wireless networks to be used as physical sensors.

Seeing through walls with Wi-Fi

Adib, F., Katabi, D. 2013. See through walls with Wi-Fi! ACM SIGCOMM;http://people.csail.mit.edu/fadel/papers/wivi-paper.pdf.

The first paper shows that Wi-Fi signals can extend our senses, allowing us to see moving objects through walls and behind closed doors. In particular, such signals can be used to identify the number of people in a closed room and their relative locations. The basic idea is similar to radar and sonar imaging. Specifically, when faced with a nonmetallic wall, a fraction of the wireless signal would traverse the wall, reflect off objects and humans, and come back imprinted with a signature of what is inside a closed room. To convince yourself that Wi-Fi signals traverse walls, just recall how you can receive Wi-Fi from another room.

The main challenge of using Wi-Fi signals to see through a wall is that the wall’s reflection is very powerful. In fact, the wall’s reflection is 10,000-100,000 times stronger than any reflection coming from behind the wall. As a result, the wall’s reflection will overwhelm the Wi-Fi device and prevent it from detecting any minute reflection coming from behind it. This behavior is analogous to how someone looking at the sun cannot see an airplane in the sky at the same time. The sun’s light would overwhelm the person’s eyes and prevent them from seeing the airplane, just as the wall’s reflection would overwhelm the Wi-Fi receiver and prevent it from detecting reflections from behind it.

To overcome this problem, the authors of this paper leverage recent advances in MIMO (multiple-input, multiple-output) communications. In MIMO, multiple antenna systems can encode their transmissions so that the signal is nulled (i.e., sums up to zero) at a particular receive antenna. MIMO systems use this capability to eliminate the interference of unwanted receivers. In contrast, this paper proposes the use of nulling to eliminate reflections from static objects, including the wall. By eliminating the wall’s reflection, the proposed system can start registering the minute reflections from behind it. It analyzes these reflections to coarsely track the motion of a person behind a wall and count the number of people in a closed room.

Gesture Recognition with Wi-Fi

Pu, Q., Gupta, S., Gollakota, S., Patel, S. 2013. Whole-home gesture recognition using wireless signals. ACM MobiCom; https://homes.cs.washington.edu/~gshyam/Papers/wisee.pdf.

This paper takes Wi-Fi-based motion tracking to another level: it shows how to use Wi-Fi reflections to recognize human gestures. Specifically, over the past few years there has been a growing interest in gesture-based user interfaces. Past gesture-based interfaces, however, required the person either to be directly in front of a sensor (like the Xbox Kinect) or to wear or carry a device (such as Nintendo Wii). In contrast, this paper shows how to perform gesture recognition throughout an entire home without requiring the user to hold or wear any sensor. It does so by relying on Wi-Fi signals.

To capture information about gestures using wireless signals, this research relies on the Doppler effect. The canonical example of Doppler is the pitch of an ambulance siren increasing as it gets closer and decreasing as it moves farther away. The authors leverage this concept using Wi-Fi signals.

In particular, Wi-Fi signals are transmitted at a carrier frequency (around 2.4 GHz). A forward movement causes a small increase in this frequency (by a few hertz) and a backward movement causes a small decrease in this frequency. The authors observe that human gestures are typically composed of forward-backward movements. By zooming in on the frequency changes in the reflected signal and decomposing them into small movements, they show how to recognize human gestures. They use this capability to enable users to control appliances throughout their homes by performing in-air gestures.

Monitoring Breathing and Heart Rate using Wireless Signals

Adib, F., Mao, H., Kabelac, Z., Katabi, D., R. C. Miller, R. C. 2015. Smart homes that monitor breathing and heart rate; Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems: 837-846; http://witrack.csail.mit.edu/vitalradio/content/vitalradio-paper.pdf.

The final paper in this selection shows that we can capture and monitor human breathing and heart rates by relying on wireless reflections off the human body. To do so, the authors exploit the fact that wireless signals are affected by any movement in the environment, including chest movements caused by breathing and bodily movements caused by heartbeats.

The main challenge in extracting these minute movements is that they are easily overwhelmed by any other sources of motion in the environment. To overcome this challenge, the paper first localizes each user in the environment, then zooms in on the signal reflected from each user and analyzes variations in the user’s reflection to extract breathing and heart rate. By isolating a user’s reflection, it effectively eliminates other sources of interference, including noise or extraneous motion in the environment, which may otherwise mask the minute variations caused by the user’s vital signs. This allows multiple users’ breathing and heart rates to be monitored using wireless signals, even if the users are behind a wall.

Where do we go from here?

These papers present a few instances of a broader set of functionalities that future wireless networks will provide. These networks will likely expand beyond communications and deliver services such as indoor localization, sensing, and control. The papers presented here demonstrate advanced forms of wireless-based sensing to track humans, capture their gestures, and monitor their vital signs even when they do not carry a wireless device. This area of research is still nascent, and only time will tell how much further these techniques can go.

Peter Bailis is an assistant professor of computer science at Stanford University. His research in the Future Data Systems group (futuredata.stanford.edu/) focuses on the design and implementation of next-generation data-intensive systems. He received a Ph.D. from UC Berkeley in 2015 and an A.B. from Harvard in 2011, both in computer science.

Irene Zhang is a Ph.D. student at the University of Washington, where she works with Hank Levy and Arvind Krishnamurthy in the Computer Systems Lab. Her current research focuses on systems for large-scale, distributed applications, including distributed runtime systems and transactional storage systems. Before starting her Ph.D., she received bachelor’s and master’s degrees in computer science from MIT.

Fadel Adib is an assistant professor at the MIT Media Lab. He works on wireless networks and sensing systems. His research has been identified as one of the 50 ways MIT has transformed computer science over the past 50 years. His work has also been featured in news media including the BBC, NBC, CBS, the Washington Post, the Boston Globe, and The Guardian. Adib was named to the Forbes’ list of 30 under 30 and MIT Technology Review’s list of the world’s top 35 innovators under 35. Before joining the MIT faculty, Adib received his Ph.D. from MIT and his bachelor's degree from the American University of Beirut.

Copyright © 2016 held by owner/author. Publication rights licensed to ACM.

acmqueue

Originally published in Queue vol. 14, no. 5
Comment on this article in the ACM Digital Library





More related articles:

Geoffrey H. Cooper - Device Onboarding using FDO and the Untrusted Installer Model
Automatic onboarding of devices is an important technique to handle the increasing number of "edge" and IoT devices being installed. Onboarding of devices is different from most device-management functions because the device's trust transitions from the factory and supply chain to the target application. To speed the process with automatic onboarding, the trust relationship in the supply chain must be formalized in the device to allow the transition to be automated.


Brian Eaton, Jeff Stewart, Jon Tedesco, N. Cihan Tas - Distributed Latency Profiling through Critical Path Tracing
Low latency is an important feature for many Google applications such as Search, and latency-analysis tools play a critical role in sustaining low latency at scale. For complex distributed systems that include services that constantly evolve in functionality and data, keeping overall latency to a minimum is a challenging task. In large, real-world distributed systems, existing tools such as RPC telemetry, CPU profiling, and distributed tracing are valuable to understand the subcomponents of the overall system, but are insufficient to perform end-to-end latency analyses in practice.


David Crawshaw - Everything VPN is New Again
The VPN (virtual private network) is 24 years old. The concept was created for a radically different Internet from the one we know today. As the Internet grew and changed, so did VPN users and applications. The VPN had an awkward adolescence in the Internet of the 2000s, interacting poorly with other widely popular abstractions. In the past decade the Internet has changed again, and this new Internet offers new uses for VPNs. The development of a radically new protocol, WireGuard, provides a technology on which to build these new VPNs.


Yonatan Sompolinsky, Aviv Zohar - Bitcoin’s Underlying Incentives
Incentives are crucial for the Bitcoin protocol’s security and effectively drive its daily operation. Miners go to extreme lengths to maximize their revenue and often find creative ways to do so that are sometimes at odds with the protocol. Cryptocurrency protocols should be placed on stronger foundations of incentives. There are many areas left to improve, ranging from the very basics of mining rewards and how they interact with the consensus mechanism, through the rewards in mining pools, and all the way to the transaction fee market itself.





© ACM, Inc. All Rights Reserved.