The literature on blockchain-based databases is divided into permissioned blockchains and permissionless account-based blockchains. However, the former is not fully decentralized, and the latter suffers from challenges in scalability and practicality. We propose SpendableStore, a hybrid on/off-chain database that operates on top of permissionless UTXO-based blockchains as a novel approach to the problem of data decentralization. Our design integrates atomic data units into individual UTXOs to create a new blockchain concept called Spendable Data Objects that perform traditional CRUD operations. The integrity, immutability, and ownership of these Spendable Data Objects are safeguarded directly by the blockchain peer nodes, thus constraining the power of database administrators to achieve true data decentralization. We further support database transactions and propose an isolation mechanism called Future Now Snapshot Isolation to reason about transactional correctness in SpendableStore. We performed experiments on a major blockchain's Mainnet and observed up to 16x better throughput compared to a state-of-the-art blockchain-based database.

In database applications involving sensitive data, the dual imperatives of data confidentiality and provable (verifiable) query processing are important. This paper introduces PoneglyphDB, a database system that leverages non-interactive zero-knowledge proofs (ZKP) to support both confidentiality and provability. Unlike traditional databases, PoneglyphDB enhances confidentiality by ensuring that raw data remains exclusively with the host, while also enabling verifying the correctness of query responses by providing proofs to clients. The main innovation in this paper is proposing efficient ZKP designs (called circuits) for basic operations in SQL query processing. These basic operation circuits are then combined to form ZKP circuits for larger, more complex queries. PoneglyphDB's circuits are carefully designed to be efficient by utilizing advances in cryptography such as PLONKish-based circuits, recursive proof composition techniques, and designing with low-order polynomial constraints. We demonstrate the performance of PoneglyphDB with the standard TPC-H benchmark. Our experimental results show that PoneglyphDB can efficiently achieve both confidentiality and provability, outperforming existing state-of-the-art ZKP methods.

The problem of hotspots remains a critical challenge in high-contention workloads for concurrency control (CC) protocols. Traditional concurrency control approaches encounter significant difficulties under high contention, resulting in excessive transaction aborts and deadlocks. In this paper, we propose Brook-2PL , a novel two-phase locking (2PL) protocol that (1) introduces SLW-Graph for deadlock-free transaction execution, and (2) proposes partial transaction chopping for early lock release. Previous methods suffer from transaction aborts that lead to wasted work and can further burden the system due to their cascading effects. Brook-2PL addresses this limitation by statically analyzing a new graph-based dependency structure called SLW-Graph , enabling deadlock-free two-phase locking through predetermined lock acquisition. Brook-2PL also reduces contention by enabling early lock release using partial transaction chopping and static transaction analysis. We overcome the inherent limitations of traditional transaction chopping by providing a more flexible chopping method. Evaluation using both our synthetic online game store workload and the TPC-C benchmark shows that Brook-2PL significantly outperforms state-of-the-art CC protocols. Brook-2PL achieves an average speed-up of (2.86x) while reducing tail latency (p95) by (48%) in the TPC-C benchmark.

Data regulations like GDPR require systems to support data erasure but leave the definition of "erasure" open to interpretation. This ambiguity makes compliance challenging, especially in databases where data dependencies can lead to erased data being inferred from remaining data. We formally define a precise notion of data erasure that ensures any inference about deleted data, through dependencies, remains bounded to what could have been inferred before its insertion. We design erasure mechanisms that enforce this guarantee at minimal cost. Additionally, we explore strategies to balance cost and throughput, batch multiple erasures, and proactively compute data retention times when possible. We demonstrate the practicality and scalability of our algorithms using both real and synthetic datasets.

Integrating non-fungible tokens (NFTs) into decentralized user-facing applications like virtual worlds presents significant performance and security challenges. Traditional NFT marketplaces struggle with scalability and security, particularly when off-chain solutions are employed to enhance performance. To tackle these issues, we introduce DecentEdge (Decentralized Edge), a trusted off-chain NFT Marketplace (NFTM) designed to operate closer to the user at the edge. DecentEdge stands out by enabling concurrent, secure processing of multiple transactions on the same NFT off-chain, significantly boosting scalability. This is achieved through two key design ingredients: leveraging Trusted Execution Environments (TEEs) to secure off-chain operations, and implementing a Multi-Stage NFT transaction processing protocol. This protocol splits NFT transactions into off-chain and on-chain stages, effectively reducing the impact of on-chain latency in typical execution paths. However, this approach introduces potential conflicts between off-chain and on-chain stages, which we address with a carefully designed conflict resolution mechanism to ensure safety and security. Our experiments-conducted on a blockchain network-show that DecentEdge achieves over 300-fold throughput improvement when compared to the state-of-the-art NFTM, OpenSea.

Metastable failure is a recent abstraction of a pattern of failures that occurs frequently in real-world distributed storage systems. In this paper, we propose a formal analysis and modeling of metastable failures in replicated storage systems. We focus on a foundational problem in distributed systems—the problem of consensus—to have an impact on a large class of systems. Our main contribution is the development of a queuing-based analytical model, MSF-Model, that can be used to characterize and predict metastable failures. MSF-Model integrates novel modeling concepts that allow modeling metastable failures, which was intractable to model prior to our work. We also perform real experiments to reproduce and validate our model. Our real experiments show that MSF-Model predicts metastable failures with high accuracy by comparing the real experiment with the predictions from the queuing-based model.

Abstract Blockchain and Decentralized Applications (DApps) are increasingly important for creating trust and transparency in data storage and computation. However, on-chain transactions are often costly and slow. To overcome this challenge, off-chain nodes can be used to store and compute data. Unfortunately, this introduces the risk of untrusted nodes. To address this, authenticated data structures have been proposed, however, this ignores the compute of data from the raw data. We tackle this challenge by introducing zk-Oracle, which provides an efficient and trusted compute and storage off-chain. There is a challenge in using zero-knowledge proofs (zk-proof for short), which is the large proof generation time. We aim to overcome it with novel designs in zk-Oracle. zk-Oracle builds on zk-proofs technologies to achieve two goals. First, the computation of data structures from raw data and the corresponding proof generation is improved in terms of performance. Second, the verification on-chain is inexpensive and fast. Our experiments show that we can speed up zk-proof generation by up to $$550 \times $$ 550 × faster than the baseline method.

Consensus is a fundamental problem in distributed systems, involving the challenge of achieving agreement among distributed nodes. It plays a critical role in various distributed data management problems. This tutorial aims to provide a comprehensive primer for data management researchers on the topic of consensus and its fundamental and modern applications in data management. We begin by exploring the basic principles of consensus, including the problem statement, system models, failure scenarios, and various consensus algorithms such as Paxos and its variants. The tutorial then delves into the applications of consensus in distributed data management, focusing on distributed atomic commitment and data replication. We explain how consensus is integral to these areas and present examples of research and industry work that apply consensus to data management. The tutorial extends to modern use cases of consensus in the evolving landscapes of edge-cloud systems and blockchain technology. We discuss how consensus mechanisms are being adapted and applied in these areas, highlighting their growing importance in emerging areas of data management. By exploring these cutting-edge applications, participants will gain insights into how consensus is shaping ongoing and future research on distributed data management. The tutorial builds on the authors' recent book "Consensus in Data Management: from Distributed Commit to Blockchain". The book will serve as the foundation and reading material for the tutorial. This tutorial targets data management researchers and practitioners to equip them with the knowledge and perspective needed to innovate in these emerging fields. This includes graduate students and junior researchers starting their careers in the area of distributed data management. Also, it includes researchers in other areas of data management who wish to explore the area of distributed data management with the goal of utilizing it in their own fields.

The interest in building blockchain Decentralized Applications (DApps) has been growing over the past few years. DApps are implemented as smart contracts which are programs that are maintained by a blockchain network. Building DApps, however, faces many challenges—most notably the performance and monetary overhead of writing to blockchain smart contracts. To overcome this challenge, many DApp developers have explored utilizingoff-chainresources—nodes outside of the blockchain network—to offload part of the processing and storage. In this paper, we propose RollStore, a data indexing solution for hybrid onchain-offchain DApps. RollStore provides efficiency in terms of reduced cost and latency, as well as security in terms of tolerating Byzantine (i.e., malicious) off-chain nodes. RollStore achieves this by: (1) a three-stage commitment strategy where each stage represents a point in a performance-security trade-off—i.e., the first stage is fast but less secure while the last stage is slower but more secure. (2) utilizing zero-knowledge (zk) proofs to enable the on-chain smart contract to verify off-chain operations with a small cost. (3) Combining Log-Structured Merge (LSM) trees and Merkle Mountain Range (MMR) trees to efficiently enable both access and verification of indexed data. We experimentally evaluate the cost and performance benefits of RollStore while comparing with BlockchainDB and BigChainDB.

Blockchain and Decentralized Applications (DApps) are increasingly important for creating trust and transparency in data storage and computation. However, on-chain transactions are often costly and slow. To overcome this challenge, off-chain nodes can be used to store and compute data. We tackle this challenge by introducing zk-Oracle, which provides an efficient and trusted compute and storage off-chain. zk-Oracle builds on zero-knowledge proof (zk-proof for short) technologies to achieve two goals. First, the computation of data structures from raw data and the corresponding proof generation is improved in terms of performance. Second, the verification on-chain is inexpensive and fast. Our experiments show that we can speed up zk-proof generation by up to 550 times faster than the baseline method.

Blockchain has recently amassed a lot of interest from researchers and practitioners. This is due to its ability to manage data in a decentralized, transparent and accountable manner. However, blockchain applications are limited in terms of compute and cost effectiveness. These limits led to smart contracts—programs that are processed by the blockchain network—being relatively simple, not taking advantage of complex computation methods. In this paper, we shed light on the design space of using machine learning in blockchain applications (we call this ML on Chain for short). Although a lot of work discusses the intersection of blockchain and ML, there is little clarity in mapping, understanding, and evaluating the various approaches in this space. This paper contributes to this new area by the following: (1) we introduce a taxonomy of ML on Chain. This taxonomy considers existing and future potential methods in this area and groups them based on their design characteristics. We consider in the taxonomy five off-chain approaches and a baseline on-chain approach. (2) we perform an extensive experimental evaluation of ML on Chain methods. We compare the different 5 groups of solutions across different settings and three ML model types: logistic regression, k-nearest neighbors and neural networks. (3) Using the taxonomy and experimental study, we provide insights about the current state and challenges of the ML on Chain space; we use this newfound understanding to discuss potential future approaches and provide suggestions to address ML on Chain challenges.

Byzantine fault tolerant (BFT) state machine replication (SMR) protocols that can tolerate up to$f$failures in a configuration of$n=3f+1$replicas cannot make any liveness guarantee once the number of faults surpasses f, even if some of these faults are benign crash faults. We argue that this weakness makes BFT protocols impractical in real-world deployments where faults accumulate over time. In this paper, we present a new reconfiguration mechanism, Phoenix, that builds on the pre-existing fault detection and reconfiguration mechanisms of BFT protocols to remove faulty replicas proactively using a trusted (but limited) configuration manager. We show that Phoenix can recover from$f_{B}$Byzantine faults and$f_{C}$crash faults, where$f_{C}\leq f_{B}$, if the system deploys$n=3f_{B}+f_{C}+1$replicas. If a synchronous network connection is guaranteed between replicas and the configuration manager during reconfiguration, a synchronous variant of Phoenix needs only$n=3f_{B}+1$replicas to achieve the same recoverability. To validate our approach, we implement Phoenix as an extension of the BFT-SMaRT library.

Modern edge applications demand novel solutions where edge applications do not have to rely on a single cloud provider (which cannot be in the vicinity of every edge device) or dedicated edge servers (which cannot scale as clouds) for processing compute-intensive tasks. A recent computing philosophy, Sky computing, proposes giving each user ability to select between available cloud providers.In this paper, we present our serverless-edge co-design, which extends the Sky computing vision. In our serverless-edge co-design, we expect edge devices to collaborate and spawn required number of serverless functions. This raises several key challenges: (1) how will this collaboration take place, (2) what if some edge devices are compromised, and (3) what if a selected cloud provider is malicious. Hence, we design ServerlessBFT, the first protocol to guarantee Byzantine fault-tolerant (Bft) transactional flow between edge devices and serverless functions. We present an exhaustive list of attacks and their solutions on our serverless-edge co-design. Further, we extensively benchmark our architecture on a variety of parameters.

Abstract Recently, non-volatile memory (NVM) technology has revolutionized the landscape of memory systems. With many advantages, such as non volatility and near zero standby power consumption, these byte-addressable memory technologies are taking the place of DRAMs. Nonetheless, they also present some limitations, such as limited write endurance, which hinders their widespread use in today’s systems. Furthermore, adjusting current data management systems to embrace these new memory technologies and all their potential is proving to be a nontrivial task. Because of this, a substantial amount of research has been done, from both the database community and the storage systems community, that tries to improve various aspects of NVMs to integrate these technologies into the memory hierarchy. In this work, which is the extended version of Kargar and Nawab (Proc. VLDB Endowment 14(12):3194–3197, 2021), we explore state-of-the-art work on deploying NVMs in database and storage systems communities and the ways their limitations are being handled within these communities. In particular, we focus on (1) the challenges that are related to high energy consumption, low write endurance and asymmetric read/write costs and (2) how these challenges can be solved using hardware and software solutions, especially by reducing the number of bit flips in write operations. We believe that this area has not gained enough attention in the data management community and this tutorial will provide information on how to integrate recent advances from the NVM storage community into existing and future data management systems.

Non-volatile memory (NVM) technologies are widely adopted in data storage solutions and battery-powered mobile and IoT devices. Wear-out and energy efficiency are two vital challenges facing the use of NVM. In Hamming Tree, we propose a software-level memory-aware solution that picks the memory segment of where a write operation is applied judiciously to minimize bit flipping. It has been shown that reducing bit flips leads to reducing energy consumption and improving write endurance. We performed real evaluations on an Optane memory device that show that Hamming Tree can achieve up to 67.8% reduction in energy consumption.

Emerging edge applications require both a fast response latency and complex processing. This is infeasible with-out expensive hardware that can process complex operations-such as object detection-within a short time. Many approach this problem by addressing the complexity of the models-via model compression, pruning and quantization-or compressing the input. In this paper, we propose a different perspective when addressing the performance challenges. Croesus is a multi-stage approach to edge-cloud systems that provides the ability to find the balance between accuracy and performance. Croesus consists of two stages (that can be generalized to multiple stages): an initial and a final stage. The initial stage performs the compu-tation in real-time using approximate/best-effort computation at the edge. The final stage performs the full computation at the cloud, and uses the results to correct any errors made at the initial stage. In this paper, we demonstrate the implications of such an approach on a video analytics use-case and show how multi-stage processing yields a better balance between accuracy and performance. Moreover, we study the safety of multi-stage transactions via two proposals: multi-stage serializability (MS-SR) and multi-stage invariant confluence with Apologies (MS-IA).

Online deep learning (ODL) has become an important methodology for modeling time-based performance of computer systems. An open problem is the intelligent selection of features from raw workload traces of computer systems. The best methods are overly sensitive to noisy data, causing frequent feature changes and re-training. Using all available features inflates training time and introduces model artifacts if some features should have been dropped. We present WinnowML, a method for automatically determining the most relevant feature subset for a predictive time-series model. WinnowML combines existing feature ranking algorithms and a history of each feature’s ranking to iteratively rank a feature set to lower prediction error and maximize long term relevance. From this ranked feature set, the most relevant and stable subset is selected to train a model. Experimentally, we show how WinnowML can lower a model’s mean absolute relative error up to 42% on average compared to the closest performing approach. Additionally, we lower the fluctuation in feature ranking and selection up to 65%. We also demonstrate how to combine WinnowML and a model search tool to provide improvements in performance of up to 14.5% when compared to using all the feature available.

Non-volatile memory (NVM) technologies suffer from limited write endurance. To address this challenge, we propose Predict and Write (PNW), a K/V-store that uses a clustering-based machine learning approach to extend the lifetime of NVMs. PNW decreases the number of bit flips for PUT/UPDATE operations by determining the best memory location an updated value should be written to. PNW leverages the indirection level of K/V-stores to freely choose the target memory location for any given write based on its value. PNW organizes NVM addresses in a dynamic address pool clustered by the similarity of the data values they refer to. We show that, by choosing the right target memory location for a given PUT/UPDATE operation, the number of total bit flips and cache lines can be reduced by up to 85% and 56% over the state of the art.

We tackle one of the fundamental data management challenges in edge-cloud computing, the problem of data indexing. We propose Cooperative LSM (CooLSM), a distributed Log-Structured Merge Tree that is designed to overcome the unique challenges of edge-cloud indexing such as machine and workload heterogeneity and the communication latency asymmetry between the edge and the cloud. To tackle these challenges, CooLSM deconstructs the LSM tree [23] into its basic parts. This deconstruction allows a better distribution and placement of resources across edge and cloud devices. For example, append-specific functionality is managed at the edge to ensure appending and serving data in real-time, whereas resource-intensive operations such as compaction and querying is managed at the cloud where more compute resources are available.

We propose WedgeChain, a data store that spans both edge and cloud nodes (an edge-cloud system). WedgeChain consists of a logging layer and a data indexing layer. In this study, we encounter two challenges: (1) edge nodes are untrusted and potentially malicious, and (2) edge-cloud coordination is expensive. WedgeChain tackles these challenges by the following proposals: (1) Lazy (asynchronous) certification: where data is committed at the untrusted edge and then lazily certified at the cloud node. This lazy certification method takes advantage of the observation that an untrusted edge node is unlikely to act maliciously if it knows it will be detected (and punished) eventually. Our lazy certification method guarantees that malicious acts (i.e., lying) are eventually detected. (2) Data-free certification: our lazy certification method only needs to send digests of data to the cloud-instead of sending all data to the cloud-which enables saving network and cloud resources and reduce costs. (3) LSMerkle: we extend a trusted index (mLSM [32]) to enable indexing data at the edge while utilizing lazy and data-free certification.

Recently, Non-Volalile Memory (NVM) technology has revolutionized the landscape or memory systems. With many advantages, such as non volatility and near zero standby power consumption, these byte-addressable memory technologies are taking the place of DRAMs. Nonetheless, they also present some limitations, such as limited write endurance, which hinders their widespread use in today's systems. Furthermore, adjusting current data management systems to embrace these new memory technologies and all their potential is proving to be a nontrivial task. Because of this, a substantial amount of research has been done, from both the database community and the storage systems community, that tries to improve various aspects of NVMs to integrate these technologies into the memory hierarchy. In this tutorial we survey state-of-the-art work on deploying NVMs in database and storage systems communities and the ways their limitations are being handled within these communities. In particular, we focus on the challenges that are related to low write endurance and extending the lifetime of NVM devices.

This errata article discusses and corrects a minor error in our work published in VLDB 2019. The discrepancy specifically pertains to Algorithms 3 and 4. The algorithms presented in the paper are biased towards a commit decision in a specific failure scenario. We explain the error using an example before correcting the algorithm.

The size and complexity of large storage systems, such as high-performance computing (HPC) systems, inhibit rapid effective restructuring of data layouts to maintain performance as workloads shift. To address this issue, we have developed Geomancy, a tool that models the placement of data within a distributed storage system and reacts to drops in performance. Our approach to optimizing throughput offers benefits for storage systems such as avoiding potential bottlenecks and increasing overall I/O throughput from 11% to 30%.

According to YouTube statistics [1], more than 400 hours of content is uploaded to its platform every minute. At this rate, it is estimated that it would take more than 70 years of continuous watch time in order to view all content on YouTube, assuming no more content is uploaded. This raises great challenges when attempting to actively process and analyze video content.

The basic structure of the LSM[3] tree consists of four levels (we are considering only 4 levels), L0 in memory, and L1 to L3 in the disk. Compaction in L0/L1 is done through tiering, and compaction in the rest of the tree is done through leveling. Cooperative-LSM (C-LSM) is implemented by deconstructing the monolithic structure of LSM[3] trees to enhance the scalability of LSM trees by utilizing the resources of multiple machines in a more flexible way. The monolithic structure of LSM[3] tree lacks flexibility, and the only way to deal with an increased load on is to re-partition the data and distribute it across nodes.

Wide-area Edge Database (WedgeDB) span globally and store data closer to the users. We term this the Global Edge Data management problem. In such an environment, aspects such as data storage, retrieval, transaction processing, and protection from malicious actors need to be addressed by any data management system that aims to consider itself a viable solution. Although blockchain technology (both permissioned and permissionless) has provided a way to address these concerns, transaction processing in these environments is still challenging. WedgeDB is an attempt to address these security problems in edge-cloud data systems [2].

The byzantine fault-tolerance model captures a wide-range of failures—common in real-world scenarios—such as ones due to malicious attacks and arbitrary software/hardware errors. We propose Blockplane, a middleware that enables making existing benign systems tolerate byzantine failures. This is done by making the existing system use Blockplane for durability and as a communication infrastructure. Blockplane proposes the following: (1) A middleware and communication infrastructure to make an entire benign protocol byzantine fault-tolerant, (2)A hierarchical locality-aware design to minimize the number of wide-area messages, (3) A separation of fault-tolerance concerns to enable designs with higher performance.

Providing security and privacy for the Internet of Things (IoT) applications while ensuring a minimum level of performance requirements is an open research challenge. Recently, blockchain offers a promising solution to overcome the current peer-to-peer networks limitations. In the context of IoT, Byzantine fault tolerance (BFT)-based consensus protocols are used due to the energy efficiency advantage over other consensus protocols. The consensus process in BFT is done by electing a group of authenticated nodes. The elected nodes will be responsible for ensuring the data blocks' integrity through defining a total order on the blocks and preventing the concurrently appended blocks from containing conflicting data. However, the blockchain consensus layer contributes the most performance overhead. Therefore, a performance study needs to be conducted especially for the IoT applications that are subject to maximum delay constraints. In this paper, we obtain a mathematical expression to calculate the end-to-end delay with different network configurations, i.e., number of network hops and replica machines. We validate the proposed analytical model with simulation. Our results show that the unique characteristics of IoT traffic have an undeniable impact on the end-to-end delay requirement.

Data storage in the Cloud needs to be scalable and fault-tolerant. Atomic commitment protocols such as Two Phase Commit (2PC) provide ACID guarantees for transactional access to sharded data and help in achieving scalability. Whereas consensus protocols such as Paxos consistently replicate data across different servers and provide fault tolerance. Cloud based datacenters today typically treat the problems of scalability and fault-tolerance disjointedly. In this work, we propose a unification of these two different paradigms into one framework called Consensus and Commitment (C&C) framework. The C&C framework can model existing and well known data management protocols as well as propose new ones. We demonstrate the advantages of the C&C framework by developing a new atomic commitment protocol, Paxos Atomic Commit (PAC), which integrates commitment with recovery in a Paxos-like manner. We also instantiate commit protocols from the C&C framework catered to different Cloud data management techniques. In particular, we propose a novel protocol, Generalized PAC (G-PAC) that integrates atomic commitment and fault tolerance in a cloud paradigm involving both sharding and replication of data. We compare the performance of G-PAC with a Spanner-like protocol, where 2PC is used at the logical data level and Paxos is used for consistent replication of logical data. The experimental results highlight the benefits of combining consensus along with commitment into a single integrated protocol.

In this paper, we propose Dynamic Paxos (DPaxos), a Paxos-based consensus protocol to manage access to partitioned data across globally-distributed datacenters and edge nodes. DPaxos is intended to implement a State Machine Replication component in data management systems for the edge. DPaxos targets the unique opportunities of utilizing edge computing resources to support emerging applications with stringent mobility and real-time requirements such as Augmented and Virtual Reality and vehicular applications. The main objective of DPaxos is to reduce the latency of serving user requests, recovering from failures, and reacting to mobility. DPaxos achieves these objectives by a few proposed changes to the traditional Paxos protocol. Most notably, DPaxos proposes a dynamic allocation of quorums ( i.e. , groups of nodes) that are needed for Paxos Leader Election. Leader Election quorums in DPaxos are smaller than traditional Paxos and expand only in the presence of conflicts.

The efficient processing of video streams is a key component in many emerging Internet of Things (IoT) and edge applications, such as Virtual and Augmented Reality (V/AR) and self-driving cars. These applications require real-time high-throughput video processing. This can be attained via a collaborative processing model between the edge and the cloud---called an Edge-Cloud model . To this end, many approaches were proposed to optimize the latency and bandwidth consumption of Edge-Cloud video processing, especially for Neural Networks (NN)-based methods. In this demonstration. We investigate the efficiency of these NN techniques, how they can be combined, and whether combining them leads to better performance. Our demonstration invites participants to experiment with the various NN techniques, combine them, and observe how the underlying NN changes with different techniques and how these changes affect accuracy, latency and bandwidth consumption.

Cloud-based data-intensive applications have to process high volumes of transactional and analytical requests on large-scale data. Businesses base their decisions on the results of analytical requests, creating a need for real-time analytical processing. We propose Janus, a hybrid scalable cloud datastore, which enables the efficient execution of diverse workloads by storing data in different representations. Janus manages big datasets in the context of datacenters, thus supporting scaling out by partitioning the data across multiple servers. This requires Janus to efficiently support distributed transactions. In order to support the different datacenter requirements, Janus also allows diverse partitioning strategies for the different representations. Janus proposes a novel data movement pipeline to continuously ensure up to date data between the different representations. Unlike existing multi-representation storage systems and Change Data Capture (CDC) pipelines, the data movement pipeline in Janus supports partitioning and handles both distributed transactions and diverse partitioning strategies. In this paper, we focus on supporting Online Transaction Processing (OLTP) and Online Analytical Processing (OLAP) workloads, and hence use row and column-oriented representations, which are the most efficient representations for these workloads. Our evaluations over Amazon AWS illustrate that Janus can provide real-time analytical results, in addition to processing high-throughput transactional workloads.

Variety of data has led to the fall of the "One size fits all" paradigm in databases. Applications now store data in multiple data representations, rather than just storing the data in a single relational database. However, applications only provide consistency semantics at the boundaries of a single datastore, corresponding to specific representation. This can lead to semantically inconsistent executions, which can have undesirable consequences for the application users. We propose, Typhon, a multi-representation data processing framework, which defines consistency semantics across multiple representations. Typhon introduces the notion of entities, which link the data present in diverse representations, and defines implicit causal guarantees, which capture the logical order intended by the application user. Typhon lays the foundation of a consistency model for multi-representation data, over which applications can build their protocols and reason about the consistency semantics of their existing solutions. We then propose a protocol, Cerberus, which provides implicit causal guarantees defined by Typhon's multi-representation consistency framework. Our evaluations show that Cerberus's performance is close to the solution providing no consistency guarantees across multiple representations, and outperforms baseline locking protocols providing Typhon's consistency guarantees across multiple data representations.

Internet of Things (IoT) applications like smart cars, smart cities and wearables are becoming widespread and are the future of the Internet. One of the major challenges for IoT applications is efficiently processing, storing and analyzing the continuous stream of incoming data from a large number of connected sensors. We propose a multi-representation based data processing architecture for IoT applications. The data is stored in multiple representations, like rows, columns, graphs which provides support for diverse application demands. A unifying update mechanism based on deterministic scheduling is used to update the data representations, which completely removes the need for data transfer pipelines like ETL (Extract, Transform and Load). The combination of multiple representations, and the deterministic update mechanism, provides the ability to support real-time analytics and caters to IoT applications by minimizing the latency of operations like computing pre-defined aggregates.

Global-scale data management (GSDM) empowers systems by providing higher levels of fault-tolerance, read availability, and efficiency in utilizing cloud resources. This has led to the emergence of global-scale data management and event processing. However, the Wide-Area Network (WAN) latency separating datacenters is orders of magnitude larger than typical network latencies, and this requires a reevaluation of many of the traditional design trade-offs of data management systems. Therefore, data management problems must be revisited to account for the new design space. In this tutorial, we survey recent developments in GSDM focusing on identifying fundamental challenges and advancements in addition to open research opportunities.

Technology trends suggest that byte-addressable nonvolatile memory (NVM) will supplant many uses of DRAM over the coming decade, raising the prospect of inexpensive recovery from power failures and similar faults. Ensuring the consistency of persistent state remains nontrivial, however, in the presence of volatile caches; cached values can "leak" back to persistent memory in arbitrary order. To ensure consistency, existing persistent memory algorithms use expensive, explicit write-back instructions to force each value back to memory before performing a dependent write, thereby incurring significant run-time overhead. To reduce this overhead, we present a new design paradigm that we call periodic persistence. In a periodically persistent data structure, updates are made "in place," but can safely leak back to memory in any order, because only those updates that are known to be valid will be heeded during recovery. To guarantee forward progress, we periodically force a write-back of all dirty data in the cache, ensuring that all "sufficiently old" updates have indeed become persistent, at which point they become semantically visible to the recovery process. As an example of periodic persistence, we present a transactional hash map, Dalí, together with an informal proof of safety (buffered durable linearizability). Experiments with a prototype implementation suggest that periodic persistence can offer substantially better performance than either file-based or incrementally persistent (per-access write-back) alternatives.

Trends detection in social networks is possible via a multitude of models with different characteristics. These models are pre-defined and rigid which creates the need to expose the social network graph to data scientists to introduce the human-element in trends detection. However, inspecting large social network graphs visually is tiresome. We tackle this problem by providing effective graph summarizations aimed at the application of geo-correlated trends detection in social networks.

Global-scale data management (GSDM) empowers systems by providing higher levels of fault-tolerance, read availability, and efficiency in utilizing cloud resources. This has led to the emergence of global-scale data management and event processing. However, the Wide-Area Network (WAN) latency separating data is orders of magnitude larger than conventional network latencies, and this requires a reevaluation of many of the traditional design trade-offs of data management systems. Therefore, data management problems must be revisited to account for the new design space. In this tutorial we survey recent developments in GSDM focusing on identifying fundamental challenges and advancements in addition to open research opportunities.

Geo-replication is the process of maintaining copies of data at geographically dispersed datacenters for better availability and fault-tolerance. The distinguishing characteristic of geo-replication is the large wide-area latency between datacenters that varies widely depending on the location of the datacenters. Thus, choosing which datacenters to deploy a cloud application has a direct impact on the observable response time. We propose an optimization framework that automatically derives a geo-replication placement plan with the objective of minimizing latency. By running the optimization framework on real placement scenarios, we learn a set of placement optimizations for geo-replication. Some of these optimizations are surprising while others are in retrospect straight-forward. In this demonstration, we highlight the geo-replication placement optimizations through the DB-Risk game. DB-Risk invites players to create different placement scenarios while experimenting with the proposed optimizations. The placements created by the players are tested on real cloud deployments.

Web-based applications face unprecedented workloads demanding the processing of a large number of events reaching to the millions per second. That is why developers are increasingly relying on scalable cloud platforms to implement cloud applications. Chariots exposes a shared log to be used by cloud applications. The log is essential for many tasks like bookkeeping, recovery, and debugging. Logs offer linearizability and simple append and read operations of immutable records to facilitate building complex systems like stream processors and transaction managers. As a cloud platform, Chariots offers fault-tolerance, persistence, and high-availability, transparently. Current shared log infrastructures suffer from the bottleneck of serializing log records through a centralized server which limits the throughput to that of a single machine. We propose a novel distributed log store, called the Fractal Log Store (FLStore), that overcomes the bottleneck of a single-point of contention. FLStore maintains the log within the datacenter. We also propose Chariots, which provides multi-datacenter replication for shared logs. In it, FLStore is leveraged as the log store. Chariots maintains causal ordering of records in the log and has a scalable design that allows elastic expansion of resources.

Preserving the integrity of application data across updates in the presence of failure is an essential function of computing systems, and byte-addressable non-volatile memory (NVM) broadens the range of fault-tolerance strategies that implement it. NVM invites database systems to manipulate durable data directly via load and store instructions, but overheads due to the widely used mechanisms that ensure consistent recovery from failures impair performance, e.g., the logging overheads of transactions. We introduce the concept of Timely Sucient Persistence (TSP) mechanisms, which is relevant to both conventional and emerging computer architectures. For a broad spectrum of faulttolerance requirements, satisfactory TSP mechanisms typically involve lower overheads during failure-free operation than their non-TSP counterparts; hardware and OS support can facilitate TSP mechanisms. We present TSP variants of programs representing two very di↵erent classes of sharedmemory multi-threaded software that store application data in persistent heaps: The first employs conventional mutexes for isolation, and TSP substantially reduces the overhead of a fault-tolerance mechanism based on fine-grained logging. The second class of software employs lock-free and wait-free algorithms; remarkably, TSP is very easy to retrofit onto a non-resilient design and enjoys zero runtime overhead .E xtensive experiments confirm that TSP yields robust crash resilience with substantially reduced overhead.

Transaction time databases can be put to a number of valuable uses, auditing, regulatory compliance, readable backups, and enabling multi-version concurrency control. While additional storage for retaining multiple versions is unavoidable, compression and the declining cost of disk storage largely removes that impediment to supporting multi-version data. Not clear has been whether effective indexing of historical versions, can be achieved at high performance. The current paper shows how temporal indexing can exploit the latch-free infrastructure provided for the Bw-tree by the LLAMA cache/storage subsystem to support high performance. Further, it demonstrates how the LLAMA mapping table can be exploited to simultaneously enable migration of historical data, e.g. to cloud storage, while overcoming the index node time splitting difficulty that has arisen in the past when historical nodes are migrated.

Cross datacenter replication is increasingly being deployed to bring data closer to the user and to overcome datacenter outages. The extent of the influence of wide-area communication on serializable transactions is not yet clear. In this work, we derive a lower-bound on commit latency. The sum of the commit latency of any two datacenters is at least the Round-Trip Time (RTT) between them. We use the insights and lessons learned while deriving the lower-bound to develop a commit protocol, called Helios, that achieves low commit latencies. Helios actively exchanges transaction logs (history) between datacenters. The received logs are used to decide whether a transaction can commit or not. The earliest point in the received logs that is needed to commit a transaction is decided by Helios to ensure a low commit latency. As we show in the paper, Helios is theoretically able to achieve the lower-bound commit latency. Also, in a real-world deployment on five datacenters, Helios has a commit latency that is close to the optimal.

The past decade has witnessed an increasing adoption of cloud database technology, which provides better scalability, availability, and fault-tolerance via transparent partitioning and replication, and automatic load balancing and fail-over. However, only a small number of cloud databases provide strong consistency guarantees for distributed transactions, despite decades of research on distributed transaction processing, due to practical challenges that arise in the cloud setting, where failures are the norm, and human administration is minimal. For example, dealing with locks left by transactions initiated by failed machines, and determining a multi-programming level that avoids thrashing without under-utilizing available resources, are some of the challenges that arise when using lock-based transaction processing mechanisms in the cloud context. Even in the case of optimistic concurrency control, most proposals in the literature deal with distributed validation but still require the database to acquire locks during two-phase commit when installing updates of a single transaction on multiple machines. Very little theoretical work has been done to entirely eliminate the need for locking in distributed transactions, including locks acquired during two-phase commit. In this paper, we re-design optimistic concurrency control to eliminate any need for locking even for atomic commitment, while handling the practical issues in earlier theoretical work related to this problem. We conduct an extensive experimental study to evaluate our approach against lock-based methods under various setups and workloads, and demonstrate that our approach provides many practical advantages in the cloud context.

Web service providers have been using NoSQL datastores to provide scalability and availability for globally distributed data at the cost of sacrificing transactional guarantees. Recently, major web service providers like Google have moved towards building storage systems that provide ACID transactional guarantees for globally distributed data. For example, the newly published system, Spanner, uses Two-Phase Commit and Two-Phase Locking to provide atomicity and isolation for globally distributed data, running on top of Paxos to provide fault-tolerant log replication. We show in this paper that it is possible to provide the same ACID transactional guarantees for multi-datacenter databases with fewer cross-datacenter communication trips, compared to replicated logging. Instead of replicating the transactional log, we replicate the commit operation itself, by running Two-Phase Commit multiple times in different datacenters and using Paxos to reach consensus among datacenters as to whether the transaction should commit. Doing so not only replaces several inter-datacenter communication trips with intra-datacenter communication trips, but also allows us to integrate atomic commitment and isolation protocols with consistent replication protocols to further reduce the number of cross-datacenter communication trips needed for consistent replication; for example, by eliminating the need for an election phase in Paxos. We analyze our approach in terms of communication trips to compare it against the log replication approach, then we conduct an extensive experimental study to compare the performance and scalability of both approaches under various multi-datacenter setups.

We present a framework for concurrency control and availability in multi-datacenter datastores. While we consider Google's Megastore as our motivating example, we define general abstractions for key components, making our solution extensible to any system that satisfies the abstraction properties. We first develop and analyze a transaction management and replication protocol based on a straightforward implementation of the Paxos algorithm. Our investigation reveals that this protocol acts as a concurrency prevention mechanism rather than a concurrency control mechanism. We then propose an enhanced protocol called Paxos with Combination and Promotion (Paxos-CP) that provides true transaction concurrency while requiring the same per instance message complexity as the basic Paxos protocol. Finally, we compare the performance of Paxos and Paxos-CP in a multi-datacenter experimental study, and we demonstrate that Paxos-CP results in significantly fewer aborted transactions than basic Paxos.

We propose TMAC, a timestamp-ordered MAC protocol for Wireless Mesh Networks (WMNs). TMAC extends CSMA/CA by scheduling data packets based on their age. Prior to transmitting a data packet, a transmitter broadcasts a request control message appended with a timestamp to a selected list of neighbors. It can proceed with the transmission only if it receives a sufficient number of grant control messages from these neighbors. A grant message indicates that the associated data packet has the lowest timestamp of all the packets pending transmission at the local transmit queue. We demonstrate that a loose ordering of timestamps among neighboring nodes is sufficient for enforcing local fairness, subsequently leading to flow rate fairness in a multi-hop WMN. We show that TMAC can be implemented using the control frames in IEEE 802.11 stack, and thus can be easily integrated in existing 802.11-based WMNs. Our simulation results show that TMAC achieves excellent resource allocation fairness while maintaining over 90% of maximum link capacity in parking lot and large grid topologies.