Many key-value stores and database systems use log-structured merge-trees (LSM-trees) as their storage engines because of their excellent write performance. However, the read performance of LSM-trees is suboptimal due to the overlapping sorted runs. Most existing efforts rely on filters to reduce unnecessary I/Os, but filters fundamentally do not help locate items and often become the bottleneck of the system. We identify that the lack of efficient index is the root cause of subpar read performance in LSM-trees. In this paper, we propose Disco: a compact index for LSM-trees. Disco indexes all the keys in an LSM-tree, so a query does not have to search every run of the LSM-tree. It records compact key representations to minimize the number of key comparisons so as to minimize cache misses and I/Os for both point and range queries. Disco guarantees that both point queries and seeks issue at most one I/O to the underlying runs, achieving an I/O efficiency close to a B + -tree. Disco improves upon REMIX's pioneering multi-run index design with additional compact key representations to help improve read performance. The representations are compact so the cost of persisting Disco to disk is small. Moreover, while a traditional LSM-tree has to choose a more aggressive compaction policy that slows down write performance to have better read performance, a Disco-indexed LSM-tree can employ a write-efficient policy and still have good read performance. Experimental results show that Disco can save I/Os and improve point and range query performance by up to 220% over RocksDB while maintaining efficient writes.

The efficiency of concurrency control protocols plays a crucial role in transaction processing systems. However, when it comes to deterministic transactions (i.e., transactions with known read/write key sets), existing concurrency control protocols are not optimized to make the most of the determinism. They either force transactions to be aborted and retried, which negatively affects system throughput, or use a centralized scheduler to organize transactions in a way that avoids aborts, but with limited system scalability.In this paper, we present DecentSched, a highly efficient decentralized concurrency control protocol for deterministic transactions. DecentSched employs fine-grained queuing and a decentralized scheduling algorithm to enable serializable concurrent transaction execution with a high degree of parallelism. Extensive evaluation results show that DecentSched can outperform state-of-the-art concurrency control protocols in representative benchmarks.

Recent work in networking, storage and multi-threading has demonstrated improved performance and scalability by replacing kernel-mode interrupts with high-rate user-space polling. Typically, such polling is performed by a dedicated core. Compiler Interrupts (CIs) instead enable efficient, automatic high-rate polling on a shared thread, which performs other work between polls. CIs are instrumentation-based and light-weight, allowing frequent interrupts with little performance impact. For example, when targeting a 5,000 cycle interval, the median overhead of our fastest CI design is 4% vs. 800% for hardware interrupts, across programs in the SPLASH-2, Phoenix and Parsec benchmark suites running with 32 threads. We evaluate CIs on three systems-level applications: (a) kernel bypass networking with mTCP, (b) joint kernel bypass networking and CPU scheduling with Shenango, and (c) delegation, a message-passing alternative to locking, with FFWD. For each application, we find that CIs offer compelling qualitative and quantitative improvements over the current state of the art. For example, CI-based mTCP achieves ≈2× stock mTCP throughput on a sample HTTP application.

Deterministic multithreading (DMT) fundamentally requires total, deterministic ordering of synchronization operations on each synchronization variable, i.e. a partial ordering over all synchronization operations. In practice, prior DMT systems totally order all synchronization operations, regardless of synchronization variable; the result is severe performance degradation for highly concurrent applications using fine-grained synchronization. Motivated by this class of programs, we propose lazy determinism as a way to go beyond this total order bottleneck. Lazy determinism executes synchronization operations speculatively, and enforces determinism by subsequently validating the resulting order of operations. If an ordering violation is detected, part of the computation is restarted. By enforcing only the partial ordering required to guarantee determinism, lazy determinism increases the available parallelism during deterministic execution. We implement LazyDet via a pure-software runtime system accelerated by custom Linux kernel support. Our experiments with hash table benchmarks from Synchrobench show roughly an order of magnitude improvement in the performance of lock-based data structures compared to the state of the art in eager determinism. For benchmarks from PARSEC-2, SPLASH-2, and Phoenix, we demonstrate runtime improvements of up to 2× on the programs that challenge deterministic execution environments the most.

We revisit the question of delegation vs. synchronized access to shared memory, and show through analysis and demonstration that delegation can be much faster than locking under a range of common circumstances. Starting from first principles, we propose fast, fly-weight delegation (ffwd). The highly optimized design of ffwd allows it to significantly outperform prior work on delegation, while retaining the scalability advantage.

We observe that in many applications, the motion present in a scene is well characterized by a small number of (rigid) motion hypotheses. Based on this observation, we present rigid multi-motion optical flow (RMM). By restricting flow to one of several motion hypotheses, RMM produces more accurate optical flow than arbitrary motion models. We evaluate an algorithm based on RMM on a novel synthetic dataset, consisting of 12 photo-realistically rendered scenes containing rigid vehicular motion and a corresponding, exact, ground truth. On this dataset, we demonstrate a substantial advantage of RMM over general-purpose algorithms: going from 36% outliers with the DiscreteFlow algorithm, to 26% with ours, with a mean error reduction from 8.4px to 6.9px. We also perform qualitative evaluation on real-world imagery from traffic cameras.

In an online GPS tracking system, a fundamental trade-off exists between timeliness, the average time interval between a recorded change in location and a change in the reported location; accuracy, the average error between the actual location and the reported location; and uplink usage, the average amount of data used per second of tracking. While tracking efficiency has been addressed in the literature, our thrifty tracking system presents the first unified view of timeliness, accuracy, and uplink usage, allowing the user to specify desired targets for any two of these objectives, while optimizing the third. We also provide a closed-form characterization of this three-way trade-off, and demonstrate that our system converges to the predicted performance.

We present Consequence, a deterministic multi-threading library. Consequence achieves deterministic execution via store buffering and strict ordering of synchronization operations. To ensure high performance under a wide variety of conditions, the ordering of synch operations is based on a deterministic clock [25], and store buffering is implemented using version-controlled memory [23].

Every day, travelers use Public Transport Systems to reach their destinations. Public Transport Authorities generally use passive wayfinding devices, including ambient displays, to provide useful information for travelers, such as the number of vehicles in the vicinity of a stop and their estimated times of arrival. However, due to both the complexity of the transport networks and the lack of sophistication in the design of these displays, the information provided by these devices is limited. We present TransitTrace, a visualization that exploits interaction-free ambient displays to provide travelers with more detailed information and ultimately to help them to navigate the city using a Public Transport System. Specifically, the proposed design makes use of a novel animation strategy to aid travelers in route planning tasks. In this paper, we describe details about the system and visualization design of TransitTrace, as well as its initial implementation using transportation data provided by the City of Chicago.

We present Conversion, a multi-version concurrency control system for main memory segments. Like the familiar Subversion version control system for files, Conversion provides isolation between processes that each operate on their own working copy. A process retrieves and merges any changes committed to the trunk by calling update(), and a call to commit() pushes any local changes to the trunk.

A typical online GPS tracking system uses a cellular uplink to report the location of a device to a central server, and in a study based on 1.6 billion location updates we find at least 90% are sent with a fixed 1--300 second period. Through experiments with the cost of cellular data transmission we also find that every packet sent incurs significant overhead.

This paper describes a process for automatically inferring maps from large collections of opportunistically collected GPS traces. In this type of dataset, there is often a great disparity in terms of coverage. For example, a freeway may be represented by thousands of trips, whereas a residential road may only have a handful of observations. Additionally, while modern GPS receivers typically produce high-quality location estimates, errors over 100 meters are not uncommon, especially near tall buildings or under dense tree coverage. Combined, GPS trace disparity and error present a formidable challenge for the current state of the art in map inference. By tuning the parameters of existing algorithms, a user may choose to remove spurious roads created by GPS noise, or admit less-frequently traveled roads, but not both.

We address the problem of inferring road maps from large-scale GPS traces that have relatively low resolution and sampling frequency. Unlike past published work that requires high-resolution traces with dense sampling, we focus on situations with coarse granularity data, such as that obtained from thousands of taxis in Shanghai, which transmit their location as seldom as once per minute. Such data sources can be made available inexpensively as byproducts of existing processes, rather than having to drive every road with high-quality GPS instrumentation just for map building - and having to re-drive roads for periodic updates. Although the challenges in using opportunistic probe data are significant, successful mining algorithms could potentially enable the creation of continuously updated maps at very low cost.

Smartphones with Wi-Fi enabled periodically transmit Wi-Fi messages, even when not associated to a network. In one 12-hour trial on a busy road (average daily traffic count 37,000 according to the state DOT), 7,000 unique devices were detected by a single road-side monitoring station, or about 1 device for every 5 vehicles.

In order to facilitate the introduction of transit tracking and arrival time prediction in smaller transit agencies, we investigate an automatic, smartphone-based system which we call EasyTracker. To use EasyTracker, a transit agency must obtain smartphones, install an app, and place a phone in each transit vehicle. Our goal is to require no other input.

EasyTracker is an automated system that assists small public or private transit agencies in deploying bus tracking and arrival time prediction. This demo will showcase how data from GPS sensors embedded in smartphones can be automatically processed in order to accurately estimate routes, bus stop locations, schedules, and make annotated maps with real-time bus tracking and arrival time predictions. We will also demonstrate a website portal which transit agencies can use to further interact with their bus transit systems.

A real-time travel time estimation system is demonstrated that uses Wi-Fi monitors deployed along surface streets to capture Wi-Fi packets from smartphones in passing vehicles. Travel time is estimated based on observations of the same vehicle by two or more monitors.

Real-time transit tracking is gaining popularity as a means for transit agencies to improve the rider experience. However, many transit agencies lack either the funding or initiative to provide such tracking services. In this paper, we describe a crowd-sourced alternative to official transit tracking, which we call cooperative transit tracking.

A transit navigation system is described that integrates real-time transit and user tracking with existing transit schedules to improve the transit riding experience.

Traffic delays and congestion are a major source of inefficiency, wasted fuel, and commuter frustration. Measuring and localizing these delays, and routing users around them, is an important step towards reducing the time people spend stuck in traffic. As others have noted, the proliferation of commodity smartphones that can provide location estimates using a variety of sensors---GPS, WiFi, and/or cellular triangulation---opens up the attractive possibility of using position samples from drivers' phones to monitor traffic delays at a fine spatiotemporal granularity. This paper presents VTrack, a system for travel time estimation using this sensor data that addresses two key challenges: energy consumption and sensor unreliability. While GPS provides highly accurate location estimates, it has several limitations: some phones don't have GPS at all, the GPS sensor doesn't work in "urban canyons" (tall buildings and tunnels) or when the phone is inside a pocket, and the GPS on many phones is power-hungry and drains the battery quickly. In these cases, VTrack can use alternative, less energy-hungry but noisier sensors like WiFi to estimate both a user's trajectory and travel time along the route. VTrack uses a hidden Markov model (HMM)-based map matching scheme and travel time estimation method that interpolates sparse data to identify the most probable road segments driven by the user and to attribute travel times to those segments. We present experimental results from real drive data and WiFi access point sightings gathered from a deployment on several cars. We show that VTrack can tolerate significant noise and outages in these location estimates, and still successfully identify delay-prone segments, and provide accurate enough delays for delay-aware routing algorithms. We also study the best sampling strategies for WiFi and GPS sensors for different energy cost regimes.

Cabernet is a system for delivering data to and from moving vehicles using open 802.11 (WiFi) access points encountered opportunistically during travel. Using open WiFi access from the road can be challenging. Network connectivity in Cabernet is both fleeting (access points are typically within range for a few seconds) and intermittent (because the access points do not provide continuous coverage), and suffers from high packet loss rates over the wireless channel. On the positive side, WiFi data transfers, when available, can occur at broadband speeds.

This paper investigates an application of mobile sensing: detecting and reporting the surface conditions of roads. We describe a system and associated algorithms to monitor this important civil infrastructure using a collection of sensor-equipped vehicles. This system, which we call the Pothole Patrol (P2), uses the inherent mobility of the participating vehicles, opportunistically gathering data from vibration and GPS sensors, and processing the data to assess road surface conditions. We have deployed P2 on 7 taxis running in the Boston area. Using a simple machine-learning approach, we show that we are able to identify potholes and other severe road surface anomalies from accelerometer data. Via careful selection of training data and signal features, we have been able to build a detector that misidentifies good road segments as having potholes less than 0.2% of the time. We evaluate our system on data from thousands of kilometers of taxi drives, and show that it can successfully detect a number of real potholes in and around the Boston area. After clustering to further reduce spurious detections, manual inspection of reported potholes shows that over 90% contain road anomalies in need of repair.

The Personal Commute Portal (PCP) is a Web-based traffic information system that provides a good driving direction and personalized route recommendation using historical and real-time traffic data obtained by a vehicular sensor network.

We propose the first practical solution to the longstanding problem of secure wireless routing in the presence of colluding attackers. Our secure routing protocol, Sprout, continuously tries new routes to the destination. Routes are probabilistically generated, with complete disregard for performance metrics. This makes Sprout uniquely resilient to attack: it cannot be tempted by shortcuts. In order to avoid compromised routes, and to ensure good overall performance, the quality of each active route is monitored by means of signed end-to-end acknowledgments. The amount of traffic sent on each route is adjusted accordingly. Sprout effectively mitigates the vast majority of known routing layer attacks, even when under assault from a large number of colluding attackers. Experiments on our 31-node testbed demonstrates the real-world performance of Sprout in terms of packet delivery ratio, round-trip times and TCP throughput. Our security analysis and simulation results show that Sprout is able to quickly find working paths in networks of hundreds of nodes and dozens or more attackers. For example, in a network of 200 nodes and an astounding 64 attackers, Sprout, on average, found a successful route within less than 10 attempts. Yet, in benign settings, Sprout provides TCP throughput within 15% of the shortest path throughput Overall, Sprout consistently delivers high, reliable performance in benign as well as hostile environments.

In a wormhole attack, wireless transmissions are recorded at one location and replayed at another, creating a virtual link under attacker control. Proposed counter-measures to this attack use tight clock synchronization, specialized hardware, or overhearing, making them difficult to realize in practice. TrueLink is a timing based countermeasure to the wormhole attack. Using TrueLink, a node i can verify the existence of a direct link to an apparent neighbor, j. Verification of a link i harr j operates in two phases. In the rendezvous phase, the nodes exchange nonces alphajand betai. This is done with tight timing constraints, within which it is impossible for attackers to forward the exchange between distant nodes. In the authentication phase, i and j transmit a signed message (alphaj,betai), mutually authenticating themselves as the originator of their respective nonce. TrueLink does not rely on precise clock synchronization, GPS coordinates, overhearing, geometric inconsistencies, or statistical methods. It can be implemented using only standard IEEE 802.11 hardware with a minor backwards compatible firmware update. TrueLink is meant to be used together with a secure routing protocol. Such protocols require an authentication mechanism, which will also be used by TrueLink. TrueLink is virtually independent of the routing protocol used. Our performance evaluation shows that TrueLink provides effective protection against potentially devastating wormhole attacks.

There is a fair amount of evidence that mesh (static multihop wireless) networks are gaining popularity, both in the academic literature and in the commercial space. Nonetheless, none of the prior work has evaluated the feasibility of applications on mesh through the use of deployed networks and real user traffic. The state of the art is the use of deployed testbeds with synthetic traces consisting of random traffic patterns.In this paper, we evaluate the feasibility of a mesh network for an all-wireless office using traces of office users and an actual 21-node multi-radio mesh testbed in an office area. Unlike previous mesh studies that have examined routing design in detail, we examine how different office mesh design choices impact the performance of user traffic. From our traces of 11 users spanning over a month, we identify 3 one hour trace periods with different characteristics and evaluate network performance for them. In addition, we consider different user-server placement, different wireless hardware, different wireless settings and different routing metrics.We find that our captured traffic is significantly different from the synthetic workloads typically used in the prior work. Our trace capture and replay methodology allows us to directly quantify the feasibility of office meshes by measuring the additional delay experienced by individual transactions made by user applications. Performance on our mesh network depends on the routing metric chosen, the user-server placement and the traffic load period. The choice of wireless hardware and wireless settings has a significant impact on performance under heavy load and challenging placement. Ultimately we conclude that for our traces and deployed system, under most conditions, all-wireless office meshes are feasible. In most cases, individual transactions incur under 20ms of additional delay over the mesh network. We believe this is an acceptable delay for most applications where a wired network to every machine is not readily available. We argue that our results are scalable to a network of over 100 users.

We show that the use of dynamic addressing can enable scalable routing in ad hoc networks. It is well known that the current ad hoc protocol suites do not scale to work efficiently in networks of more than a few hundred nodes. Most current ad hoc routing architectures use flat static addressing and thus, need to keep track of each node individually, creating a massive overhead problem as the network grows. Could dynamic addressing alleviate this problem? To begin to answer this question, we provide an initial design of a routing layer based on dynamic addressing, and evaluate its performance. Each node has a unique permanent identifier and a transient routing address, which indicates its location in the network at any given time. The main challenge is dynamic address allocation in the face of node mobility. We propose mechanisms to implement dynamic addressing efficiently. Our initial evaluation suggests that dynamic addressing is a promising approach for achieving scalable routing in meganode ad hoc networks.