In edge computing, applications are usually delivered as services, each of which runs independently and cooperates to construct complicated applications. QoS (Quality of Service) monitoring is an important way to detect and locate faulty services. In a decentralized environment, QoS monitoring will face trust problem because it is difficult to guarantee the trustworthiness of monitoring results. This article builds a blockchain system for QoS monitoring. However, there are two challenges. First, although the blockchain consensus ensures the consistency of on-chain data among nodes, there is no guarantee that the monitoring data collected in the decentralized environment are authentic, because malicious nodes may report falsified data. Second, in order to handle service faults in time, the real-time query is usually required for obtaining monitoring data. But, blockchains suffer from inefficient querying, because the sequential data storage of blockchain is designed for write intensive applications at the expense of some read performance. To address these challenges, this article proposes a clustering-based algorithm for validating the authenticity of monitoring data collected in the decentralized environment, and proposes a probabilistic threshold query over blockchain, which supports efficient querying and guarantees the probability that the query results are correct is not less than a given threshold. This article implements the proposed blockchain system based on the blockchain platformHyperledger Fabricand the edge computing platformKubeEdge. The experiment results demonstrate the proposed blockchain system provides high-throughput and low-latency monitoring ability, and can efficiently obtain monitoring results close to real QoS data.

Although BFT(Byzantine Fault Tolerance) is one of the most distinctive features of a blockchain system, many permissioned blockchains adopt RAFT as their consensus protocols, which cannot tolerate any Byzantine nodes. This paper analyzes this phenomenon base on the hypothesis of Rational Man. We propose a new consistency requirement in terms of Nash equilibrium, called NE-consistency, which requires a blockchain to guarantee consistency given that all participants are rational when choosing their strategies. We prove that both PBFT and RAFT can satisfy NE-consistency by modeling a permissioned blockchain as a repeated game. Particularly, we prove that in the sole subgame perfect equilibrium of both PBFT and RAFT, all participants tend to be good to maximize their profits.

Blockchain technologies pave a promising way for implementing the inter-organizational processes. Most of the current research works translate the execution logic in the process models into the smart contracts, which can run independently on the blockchain without the outside process engine. However, the works usually suffer from the execution and storage costs, since the translation needs to be done when the processes are deployed. In this paper, we customize a process engine for executing the inter-organizational business processes via a blockchain-style procedure, i.e., checking the validity of transactions, adding the valid transactions into the blockchain through the consensus mechanism, and then updating the process states according to the committed transactions. And then, we build a blockchain system by embedding the customized process engine into the blockchain nodes. Moreover, in order to realize the interactions between the inter-organizational processes running on blockchain and the services outside blockchain, we propose a blockchain-based approach for service registration, binding and invocation, and design a lease-based concurrency control protocol to logically isolate transactions from each other when invoking the services simultaneously. Finally, we implement a prototype system based on a permissioned blockchain platform Hyperledger Fabric and a process engine Activiti. The experimental results show the proposed blockchain system can execute the inter-organizational processes correctly and efficiently.

Smart contracts (SCs) run on the distributed ledger technology (DLT) platform and can implement agreements between participants without a trusted third party. This paper uses the DLT and SC techniques to build distributed applications composed of existing services. In practice, there are many functionally-equivalent services on the Internet. To beat their competitors, the service providers usually offer flexible QoS and use dynamic pricing strategies. Moreover, the service providers can change at runtime, e.g., they may encounter problems so that their QoS drops suddenly. This makes achieving the optimization goal at runtime (e.g., the maximization of the utility) more difficult. To address this problem, first, this paper proposes an SC-based negotiation framework. The SCs can ensure that the transactions are automatically and reliably performed as agreed upon between the service requesters and providers. The DLTs can provide the reliable data of the requests and responses of the service requesters and providers to the SCs. In addition, the SCs can identify the troubled service providers, and find other service providers to replace them at runtime. Second, this paper proposes a Bayesian Nash equilibrium (BNE) of the service providers. In the BNE, the cost-efficient service providers offer the high QoS the service requester asks for and report their costs truthfully. This BNE enables the selection of the cost-efficient service providers and the achievement of the (near) maximization of the service requesters' utility. This paper implements the proposed negotiation framework on a DLT platform called Hyperledger Fabric. The experiment results demonstrate that the proposed approach outperforms the existing approaches and can adapt to the changes of the service providers.

On-Line Analytical Processing (OLAP) enables powerful analytics by quickly computing aggregate values of numerical measures over multiple hierarchical dimensions for massive datasets. However, many types of source data, e.g., from GPS, sensors, and other measurement devices, are intrinsically inaccurate (imprecise and/or uncertain) and thus OLAP cannot be readily applied. In this paper, we address the resulting data veracity problem in OLAP by proposing the concept of probabilistic data cubes. Such a cube is comprised of a set of probabilistic cuboids which summarize the aggregated values in the form of probability mass functions (pmfs in short) and thus offer insights into the underlying data quality and enable confidence-aware query evaluation and analysis. However, the probabilistic nature of data poses computational challenges as even simple operations are #P-hard under the possible world semantics. Even worse, it is hard to share computations among different cuboids, as aggregation functions that are distributive for traditional data cubes, e.g., SUM and COUNT, become holistic in probabilistic settings. In this paper, we propose a complete set of techniques for probabilistic data cubes, from cuboid aggregation, over cube materialization, to query evaluation. For aggregation, we focus on how to maximize the sharing of computation among cells and cuboids. We present two aggregation methods: convolution and sketch-based. The two methods scale down the time complexities of building a probabilistic cuboid to polynomial and linear, respectively. Each of the two supports both full and partial data cube materialization. Then, we devise a cost model which guides the aggregation methods to be deployed and combined during the cube materialization. We further provide algorithms for probabilistic slicing and dicing queries on the data cube. Extensive experiments over real and synthetic datasets are conducted to show that the techniques are effective and scalable.

The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. We study how the Voronoi diagram can be used for uncertain spatial data, which are inherent in scientific and business applications. Specifically, we propose the Uncertain-Voronoi diagram (or UV-diagram), which divides the data space into disjoint “UV-partitions”. Each UV-partition $$P$$ is associated with a set $$S$$ of objects, such that any point $$q$$ located in $$P$$ has the set $$S$$ as its nearest neighbor with nonzero probabilities. The UV-diagram enables queries that return objects with nonzero chances of being the nearest neighbor (NN) of a given point $$q$$ . It supports “continuous nearest-neighbor search”, which refreshes the set of NN objects of $$q$$ , as the position of $$q$$ changes. It also allows the analysis of nearest-neighbor information, for example, to find out the number of objects that are the nearest neighbors of any point in a given area. A UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation of a UV-diagram, by using a set of UV-cells. A UV-cell of an object $$o$$ is the extent $$e$$ for which $$o$$ can be the nearest neighbor of any point $$q \in e$$ . We study how to speed up the derivation of UV-cells by considering its nearby objects. We also use the UV-cells to design the UV-index, which supports different queries, and can be constructed in polynomial time. We have performed extensive experiments on both real and synthetic data to validate the efficiency of our approaches.

Given a set of lists, where items of each list are sorted by the ascending order of their values, the objective of this paper is to figure out the common items that appear in all of the lists efficiently. This problem is sometimes known as common items extraction from sorted lists. To solve this problem, one common approach is to scan all items of all lists sequentially in parallel until one of the lists is exhausted. However, we observe that if the overlap of items across all lists is not high, such sequential access approach can be significantly improved. In this paper, we propose two algorithms, MergeSkip and MergeESkip, to solve this problem by taking the idea of skipping as many items of lists as possible. As a result, a large number of comparisons among items can be saved, and hence the efficiency can be improved. We conduct extensive analysis of our proposed algorithms on one real dataset and two synthetic datasets with different data distributions. We report all our findings in this paper.

This paper presents a reference framework, called BUD, to manage a large shared bank of unstructured data. This paper lists several important issues on managing or maintaining the unstructured data in BUD. BUD stores and manages the ever-growing unstructured data by introducing a novel technique called free-table, which is a conceptual view for end-users and a physical entity maintained by transactional storage manager of BUD. Free-table is cell-oriented but not column-oriented as relational table. It can store various types of unstructured data in cell with different versions. Additionally, we study two cases, VMP and PXRDB, to show that our proposal is feasible and tractable.

The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. In this paper, we study how the Voronoi diagram can be used on uncertain data, which are inherent in scientific and business applications. In particular, we propose the Uncertain-Voronoi Diagram (or UV-diagram in short). Conceptually, the data space is divided into distinct ¿UV-partitions¿, where each UV-partition P is associated with a set S of objects; any point q located in P has the set S as its nearest neighbor with non-zero probabilities. The UV-diagram facilitates queries that inquire objects for having non-zero chances of being the nearest neighbor of a given query point. It also allows analysis of nearest neighbor information, e.g., finding out how many objects are the nearest neighbors in a given area. However, a UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation for UV-partitions, and develop an adaptive index for the UV-diagram. This index can be constructed in polynomial time. We examine how it can be extended to support other related queries. We also perform extensive experiments to validate the effectiveness of our approach.

In emerging applications such as location-based services, sensor monitoring and biological management systems, the values of the database items are naturally imprecise. For these uncertain databases, an important query is the Probabilistic k-Nearest-Neighbor Query (k-PNN), which computes the probabilities of sets of k objects for being the closest to a given query point. The evaluation of this query can be both computationally- and I/O-expensive, since there is an exponentially large number of k object-sets, and numerical integration is required. Often a user may not be concerned about the exact probability values. For example, he may only need answers that have sufficiently high confidence. We thus propose the Probabilistic Threshold k-Nearest-Neighbor Query (T-k-PNN), which returns sets of k objects that satisfy the query with probabilities higher than some threshold T. Three steps are proposed to handle this query efficiently. In the first stage, objects that cannot constitute an answer are filtered with the aid of a spatial index. The second step, called probabilistic candidate selection, significantly prunes a number of candidate sets to be examined. The remaining sets are sent for verification, which derives the lower and upper bounds of answer probabilities, so that a candidate set can be quickly decided on whether it should be included in the answer. We also examine spatially-efficient data structures that support these methods. Our solution can be applied to uncertain data with arbitrary probability density functions. We have also performed extensive experiments to examine the effectiveness of our methods.

In applications like location-based services, sensor monitoring and biological databases, the values of the database items are inherently uncertain in nature. An important query for uncertain objects is the probabilistic nearest-neighbor query (PNN), which computes the probability of each object for being the nearest neighbor of a query point. Evaluating this query is computationally expensive, since it needs to consider the relationship among uncertain objects, and requires the use of numerical integration or Monte-Carlo methods. Sometimes, a query user may not be concerned about the exact probability values. For example, he may only need answers that have sufficiently high confidence. We thus propose the constrained nearest-neighbor query (C-PNN), which returns the IDs of objects whose probabilities are higher than some threshold, with a given error bound in the answers. The C-PNN can be answered efficiently with probabilistic verifiers. These are methods that derive the lower and upper bounds of answer probabilities, so that an object can be quickly decided on whether it should be included in the answer. We have developed three probabilistic verifiers, which can be used on uncertain data with arbitrary probability density functions. Extensive experiments were performed to examine the effectiveness of these approaches.

Uncertain or imprecise data are pervasive in applications like location-based services, sensor monitoring, and data collection and integration. For these applications, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with statistical confidence. Given that a limited amount of resources is available to "clean" the database (e.g., by probing some sensor data values to get their latest values), we address the problem of choosing the set of uncertain objects to be cleaned, in order to achieve the best improvement in the quality of query answers. For this purpose, we present the PWS-quality metric, which is a universal measure that quantifies the ambiguity of query answers under the possible world semantics. We study how PWS-quality can be efficiently evaluated for two major query classes: (1) queries that examine the satisfiability of tuples independent of other tuples (e.g., range queries); and (2) queries that require the knowledge of the relative ranking of the tuples (e.g., MAX queries). We then propose a polynomial-time solution to achieve an optimal improvement in PWS-quality. Other fast heuristics are presented as well. Experiments, performed on both real and synthetic datasets, show that the PWS-quality metric can be evaluated quickly, and that our cleaning algorithm provides an optimal solution with high efficiency. To our best knowledge, this is the first work that develops a quality metric for a probabilistic database, and investigates how such a metric can be used for data cleaning purposes.

In location-based services, it is common for a user to issue a query based on his/her current position. One such example is "find the available cabs within two miles of my current location". Very often, the query issuers' locations are imprecise due to measurement error, sampling error, or message delay. They may also want to protect their privacy by providing a less precise location. In this paper, we study the efficiency of queries that return probabilistic guarantees for location data with uncertainty. We classify this query into two types, based on whether the data (1) has no uncertainty (e.g., shops and restaurants), or (2) has a controlled degree of uncertainty (e.g., moving vehicles). Based on this classification, we develop three methods to improve the computational and I/O performance. The first method expands the query range based on the query issuer's uncertainty. The second idea exchanges the roles of query and data. The third technique exploits the fact that users may only be interested in answers with probabilities higher than some threshold. Experimental simulation over a realistic dataset reveals that our approaches improve the query performance significantly.