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.

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.

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×.