Communications of the ACM
Research For Practice: Distributed Transactions and Networks as Physical Sensors
Credit: iStockPhoto.com
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.
About RfP
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 will 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.
Spanner: Google's globally distributed database. In Proceedings of Operating Systems Design and Implementation, 2012; 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.
Building consistent transactions with inconsistent replication. Symposium on Operating Systems Principles, 2015; 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.
Three recent research papers have made significant strides in reducing the coordination needed for distributed transactions, making them more efficient at every level.
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.
High-performance ACID via modular concurrency control. Symposium on Operating Systems Principles, 2015; 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.
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 waves, such as Wi-Fi.
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 non-contact 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.
See through walls with Wi-Fi! ACM SIGCOMM, 2013; 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 (that is, 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.
Whole-home gesture recognition using wireless signals. ACM MobiCom, 2013; 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 that increases as it gets closer and decreases 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.4GHz). 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., Miller, R.C.
Smart homes that monitor breathing and heart rate. In Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, 2015, 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 offer 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.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.