Tail latency is crucial as it impacts user satisfaction and service-level objectives (SLOs). However, geo-distributed databases have long struggled with this issue due to wide-area network access, resulting in tail latencies of several or even exceeding ten seconds. In this paper, we highlight that further optimizing atomic commit protocols does not help but hit a tail latency wall. Instead, making concurrency control and access method selection geo-aware can mitigate this issue. To this end, we present Bonspiel, a new geo-distributed database equipped with geo-aware concurrency control and access method selection. In our experiments, Bonspiel successfully caps the tail latency of TPC-C at 1.8 seconds. Remarkably, it achieves this while maintaining full generality - it is fully SQL-compliant and strongly consistent, with both average latency and system throughput remaining at the top of the field.

Optimizing distributed protocols has traditionally been a real pain, requiring experts to figure out where improvements can be made, along with rigorous correctness proofs and meticulous implementation. This paper presents a theory to systematize this process. The proposed theory can optimize any existing distributed protocols while preserving all their original quality attributes (e.g., generality, correctness). Crucially, applying the optimizations derived from this theory does not necessitate touching the original implementation --- all you need is just to bolt on a few new message adapters. Case studies demonstrate the effectiveness of this approach. For instance, applying the theory to optimize Spanner's atomic commit protocol results in a mere 4 new message adapters, but improving its latency by up to 51% and peak throughput by up to 56%.

Multi-step highway traffic flow prediction is crucial for intelligent transportation systems, and existing works have made significant advancements in this field. However, the physical structure, including path, distance, and node degree, is critical information in traffic networks and is often overlooked when encoding spatiotemporal dependencies. Meanwhile, the problem of prediction error propagation in multi-step flow forecasting is challenging to mitigate and can significantly impact overall forecasting performance. Moreover, traffic flows between toll and gantry stations in the highway network exhibit notable differences, leading to heterogeneous flow distributions. To overcome the above issues, a novel multi-task spatiotemporal network for highway traffic flow prediction (MT-STNet) is proposed, consisting of the encoder-decoder structure, a generative inference system, and multi-task learning. The spatiotemporal block with physical transformation is developed to construct both the encoder and decoder, integrating the physical structure information into modeling the highway network’s spatiotemporal dependencies. Additionally, the generative inference architecture is designed to extract the correlation between the historical- and target- sequences to generate the target hidden representations rather than a dynamic decoding way, avoiding multi-step prediction error propagation. Furthermore, because of traffic flow heterogeneity in the highway network, multi-task learning divides highway traffic flow prediction into three tasks, sharing the underlying traffic network and knowledge learned, thereby enhancing the prediction performance of each subtask. The evaluation experiments used monitoring data from a highway in Yinchuan City, Ningxia Province, China. The experimental results demonstrate that the performance of our proposed prediction model is better than that of the baseline methods.

We present Saguaro, a permissioned blockchain system designed specifically for edge computing networks. Saguaro leverages the hierarchical structure of edge computing networks to reduce the overhead of wide-area communication by presenting several techniques. First, Saguaro proposes coordinator-based and optimistic protocols to process cross-domain transactions with low latency where the lowest common ancestor of the involved domains coordinates the protocol or detects inconsistency. Second, data are collected over hierarchy enabling higher-level domains to aggregate their sub-domain data. Finally, transactions initiated by mobile edge devices are processed without relying on high-level fog and cloud servers. Our experimental results across a wide range of workloads demonstrate the scalability of Saguaro in supporting a range of cross-domain and mobile transactions.

Two-phase-commit (2PC) has been widely adopted for distributed transaction processing, but it also jeopardizes throughput by introducing two rounds of network communications and two durable log writes to a transaction's critical path. Despite the various proposals that eliminate 2PC such as deterministic database and access localization, 2PC remains the de facto standard since the alternatives often lack generality (e.g., requiring workloads without branches based on query results). In this paper, we present Primo, a distributed transaction protocol that supports a more general set of workloads without 2PC. Primo features write-conflict-free concurrency control that guarantees once a transaction enters the commit phase, no concurrency conflict (e.g., deadlock) would occur when installing the write-set — hence the prepare phase is no longer needed to account for any potential conflict from any partition. In addition, Primo further optimizes the transaction path using asynchronous group commit. With that, the durability delay is also taken off the transaction's critical path. Empirical results on Primo are encouraging – in YCSB and TPC-C, Primo attains 1.42× to 8.25× higher throughput than state-of-the-art general protocols including Sundial and COCO, while having similar latency as COCO which also employs group commit.

Private blockchain as a replicated transactional system shares many commonalities with distributed database. However, the intimacy between private blockchain and deterministic database has never been studied. In essence, private blockchain and deterministic database both ensure replica consistency by determinism. In this paper, we present a comprehensive analysis to uncover the connections between private blockchain and deterministic database. While private blockchains have started to pursue deterministic transaction executions recently, deterministic databases have already studied deterministic concurrency control protocols for almost a decade. This motivates us to propose Harmony, a novel deterministic concurrency control protocol designed for blockchain use. We use Harmony to build a new relational blockchain, namely HarmonyBC, which features low abort rates, hotspot resiliency, and inter-block parallelism, all of which are especially important to disk-oriented blockchain. Empirical results on Smallbank, YCSB, and TPC-C show that HarmonyBC offers 2.0x to 3.5x throughput better than the state-of-the-art private blockchains.

Predicting how long a trip will take may allow travelers plan ahead, save money, and avoid traffic congestion. The journey time estimation model should take into account three crucial factors: (1) individual travel preference, (2) dynamic spatio-temporal correlations, and (3) the association between long-term speed forecast and travel time estimate. In order to overcome these challenges, this study proposes a unique parallel architecture called the multi-task spatio-temporal attention network (MT-STAN) to estimate journey times. To extract the dynamic spatio-temporal correlations of the road network, we first develop a traffic speed prediction model based on spatio-temporal block and bridge transformer networks, combining the road, timestamp, and traffic speed information into hidden states. Second, we offer a personalized model for estimating journey times that makes use of cross-network, holistic attention, and semantic transformer. In this approach, travel preferences extraction through cross-network, holistic attention permits correlations between the dynamic road network’s hidden states and individual journey characteristics, which are subsequently transformed into global semantics by the semantic transformer; preferences and semantics are integrated during the estimate phase. Finally, a multi-task learning component is included, which combines both traffic speed prediction and individual journey time estimate, via the sharing of underlying network parameters and the improvement of the contextual semantic knowledge of the latter job. Evaluation experiments are carried out using a highway dataset collected in Yinchuan City, Ningxia Province, China. The proposed prediction model outperforms state-of-the-art baseline approaches in experiments.

The impressive accuracy of deep neural networks (DNNs) has created great demands on practical analytics over video data. Although efficient and accurate, the latest video analytic systems have not supported analytics beyond selection and aggregation queries. In data analytics, Top-K is a very important analytical operation that enables analysts to focus on the most important entities. In this demonstration, we present Everest, the first system that supports efficient and accurate Top-K video analytics. Everest ranks and identifies the most interesting frames/clips from videos with probabilistic guarantees. Furthermore, it supports user-defined functions to rank frames/clips based on different semantics using different deep vision models. Everest leverages techniques from computer vision, uncertain databases, and Top-K query processing to return results quickly.

Deterministic databases are able to run transactions efficiently in a distributed setting with minimal coordination. Research has shown many benefits from having determinism, from more lightweight database replication, to no/cheaper distributed commit, to high throughput during live migration. Besides those known applications, permissioned blockchain can also be viewed as an application of the deterministic database with security added. A permissioned blockchain maintains a fully-replicated database, where each replica is synchronized by getting blocks of updates. Early permissioned blockchains run a consensus protocol (e.g., PBFT) to agree on the input and rely on the replicas to execute the transactions serially to uphold determinism. Fabric allows concurrent transaction executions but rely on running consensus to agree on the read-write-sets and broadcasting them, which incurs an excessive volume of network traffic. Deterministic concurrency control combines the best of both worlds. It enables solving consensus on the small input, and each replica is able to execute transactions independently with high concurrency. Although powerful, contemporary deterministic databases are still primitive because they support only one isolation level -- Serializable. Furthermore, many deterministic concurrency control schemes are overly pessimistic and cause many unnecessary transaction aborts. These factors motivate us to design DCC, a suite of better deterministic concurrency control schemes, not only for Serializable but also for practical isolation levels beyond Serializable.

The impressive accuracy of deep neural networks (DNNs) has created great demands on practical analytics over video data. Although efficient and accurate, the latest video analytic systems have not supported analytics beyond selection and aggregation queries. In data analytics, Top-K is a very important analytical operation that enables analysts to focus on the most important entities. In this paper, we present Everest, the first system that supports efficient and accurate Top-K video analytics. Everest ranks and identifies the most interesting frames/moments from videos with probabilistic guarantees. Everest is a system built with a careful synthesis of deep computer vision models, uncertain data management, and Top-K query processing. Evaluations on real-world videos and the latest Visual Road benchmark show that Everest achieves between 14.3x to 20.6x higher efficiency than baseline approaches with high result accuracy.

In applications such as network monitoring and sensor measurements, massive amounts of data arrive as a high-rate stream and real-time analytic over the stream data is required. Maintaining a succinct sketch over the data stream has been a dominant approach to support analysis in those applications. Recent applications, however, demand more sophisticated types of analytics such as range-counting. Unfortunately, state-of-the-art sketches perform poorly when facing range-counting as none of them was designed to support range-counting at the outset. In this paper, we aim to fill the gap and present RC-Sketch, a sketch that supports range-counting over rapid data stream. Empirical results show that RC-Sketch outperforms the state-of-the-art in range-count accuracy with comparable throughput.

Recent years, many applications have been driven advances by the use of Machine Learning (ML). Nowadays, it is common to see industrial-strength machine learning jobs that involve millions of model parameters, terabytes of training data, and weeks of training. Good efficiency, i.e., fast completion time of running a specific ML training job, therefore, is a key feature of a successful ML system. While the completion time of a long-running ML job is determined by the time required to reach model convergence, that is also largely influenced by the values of various system settings. In this paper, we contribute techniques towards building self-tuning parameter servers. Parameter Server (PS) is a popular system architecture for large-scale machine learning systems; and by self-tuning we mean while a long-running ML job is iteratively training the expert-suggested model, the system is also iteratively learning which system setting is more efficient for that job and applies it online. Our techniques are general enough to various PS-style ML systems. Experiments on TensorFlow show that our techniques can reduce the completion times of a variety of long-running TensorFlow jobs from 1.4× to 18×.