Blockchain technology offers an intelligent amalgamation of distributed ledger, Peer-to-Peer (P2P), cryptography, and smart contracts to enable trustworthy applications without any third parties. Existing blockchain systems have successfully either resolved the scalability issue by advancing the distributed consensus protocols from the control plane, or complemented the security issue by updating the block structure and encryption algorithms from the data plane. Yet, we argue that the underlying P2P network plane remains as an important but unaddressed barrier for accelerating the overall blockchain system performance, which can be discussed from how fast and reliable the network is. In order to improve the blockchain network performance about enabling fast and reliable broadcast, we establish a trust-enhanced blockchain P2P topology which takes transmission rate and transmission reliability into consideration. Transmission rate reflects blockchain network speed to disseminate transactions and blocks, and transmission reliability reveals whether transmission rate changes drastically on unreliable network connection. This paper presents BlockP2P-EP, a novel trust-enhanced blockchain topology to accelerate transmission rate and meanwhile retain transmission reliability. BlockP2P-EP first operates the geographical proximity sensing clustering, which leverages K-Means algorithm for gathering proximity peer nodes into clusters. It follows by the hierarchical topological structure that ensures strong connectivity and small diameter based on node attribute classification. Then we propose establishing trust-enhanced network topology. On top of the trust-enhanced blockchain topology, BlockP2P-EP conducts the parallel spanning tree broadcast algorithm to enable fast data broadcast among nodes both intra-and inter-clusters. Finally, we adopt an effective node inactivation detection method to reduce network load. To verify the validity of BlockP2P-EP protocol, we carefully design and implement a blockchain network simulator. Evaluation results show that BlockP2P-EP can exhibit promising network performance in terms of transmission rate and transmission reliability compared to Bitcoin and Ethereum.

This paper studies the core maintenance problem for dynamic graphs which requires to update each vertex's core number with the insertion/deletion of vertices/edges. The state-of-the-art algorithms can either process one edge associated to a vertex in each iteration [14] or can only process one superior edge associated to the vertex in each iteration [25]. Thus for high superior-degree vertices insertions/deletions, these algorithms become very inefficient. We discovered a new structure called joint edge set whose insertions/deletions only make each vertex's core number change is at most 1. The joint edge set mainly contains all the superior edges associated with the high superior-degree vertices as long as these vertices are 3-hop independent.Our algorithms can process all edges in the joint edge set in one iteration and thus can greatly reduce the processing time. The results of extensive experiments conducted on various types of real-world, temporal and synthetic graphs illustrate that the proposed algorithms achieve good efficiency, stability and scalability. Specifically, the new algorithms can outperform the single-edge processing algorithms up to 4 orders of magnitude. Compared with the state-of-the art parallel algorithms in [14] and [25], our algorithms show a significant speedup up to 60x in the processing time.

Real-world stream data with skewed distributions raises unique challenges to distributed stream processing systems. Existing stream workload partitioning schemes usually use a "one size fits all" design, which leverages either a shuffle grouping or a key grouping strategy for partitioning the stream workloads among multiple processing units, leading to notable problems of unsatisfied system throughput and processing latency. In this paper, we show that the key grouping based schemes result in serious load imbalance and low computation efficiency in the presence of data skewness while the shuffle grouping schemes are not scalable in terms of memory space. We argue that the key to efficient stream scheduling is the popularity of the stream data. We propose PStream, a popularity-aware differentiated distributed stream processing system which assigns the hot keys using shuffle grouping while assigns rare ones using key grouping. PStream leverages a novel light-weighted probabilistic counting scheme for efficiently identifying the hot keys in dynamic real-time streams. We implement PStream and conduct comprehensive experiments using large-scale traces from real-world systems to evaluate the performance of this design. Results show that PStream achieves a 2.3x improvement in terms of processing throughput and reduces the processing latency by 64% compared to existing designs.

Efficient event stream dissemination is a challenging problem in large-scale Online Social Network (OSN) systems due to the costly inter-server communications caused by the per-user view data storage. To solve the problem, previous schemes mainly explore the structures of social graphs to reduce the inter-server traffic. Based on the observation of high cluster coefficients in OSNs, a state-of-the-art social piggyback scheme can save redundant messages by exploiting an intrinsic hub-structure in an OSN graph for message piggybacking. Essentially, finding the best hub-structure for piggybacking is equivalent to finding a variation of the densest sub-graph. The existing scheme computes the best hub-structure by iteratively removing the node with the minimum weighted degree. Such a scheme incurs a worst computation cost of $O(n^2)$ , making it not scalable to large-scale OSN graphs. Using alternative hub-structure instead of the best hub-structure can speed up the piggyback assignment. However, they greatly sacrifice the communication efficiency of the assignment schedule. Different from the existing designs, in this work, we propose a QuickPoint algorithm, which removes a fraction of nodes in each iteration in finding the best hub-structure. We mathematically prove that QuickPoint converges in $O(log_a n)(a > 1)$ iterations in finding the best hub-structure for efficient piggyback. We implement QuickPoint in parallel atop Pregel, a vertex-centric distributed graph processing platform. Comprehensive experiments using large-scale data from Twitter and Flickr show that our scheme is 38.8× more efficient compared to existing schemes.

Many real-time applications in consumer electronics rely on stream band join as a fundamental operation. With two streams, the band join operation targets at obtaining the pairs of tuples which are separately included in the two streams and have close values within a user specified range. Range partitioning keeps tuples with close values in a partition. For band join, the cost of employing range partitioning is less join cost than that of employing other partitioning strategies. However, the distribution of real-world data from consumer electronics over the range is skewed, causing severe load imbalance among instances in the distributed system that employs existing static range partitioning. Load migration can alleviate the load imbalance. For range partitioning, the migration has two kinds of objectives. Migrating load to the instance with adjacent partition controls the number of partitions. However, it causes an unacceptable high cost for migrating span multiple instances. While directly migrating a split partition to the lightest instance is low cost. However, it leads to an uncontrollable number of partitions. The system for consumer electronic applications cannot tolerate high migration cost and an uncontrollable number of partitions, which result in high latency and low throughput. In this work, we propose an adaptive range partitioning strategy to ensure a controllable number of partitions and load balancing with low cost. We implement Nereus, a distributed stream band join system. Nereus designs a migration benefit model using queuing theory measure, which integrates the benefits of partition’s change and load balancing. Such a design can obtain the most beneficial migration, which achieves low migration cost and an appropriate number of partitions. We conduct comprehensive experiments using large-scale datasets from real-world applications to evaluate this design. The results show that Nereus improves the throughput by 51% and reduces the processing latency by 99%, compared to existing designs.