Detecting fake accounts (also called Sybils) is a fundamental security problem in online social networks (OSNs). Existing feature-based or social-graph-based approaches suffer from the key limitations: they can only leverage either node feature or graph structure properties such as fast-mixing and conductance, but not both. To overcome this shortcoming, we explore the introduction of recent advancements in deep neural networks for graph-structured data into Sybil detection field. These types of models enable integrating both user-level activities and graph-level structures for a new generation of feature-and-graph-based detection mechanisms. However, we find that although applying Graph Convolutional Networks (GCNs) are effective against naïve attacks, they are vulnerable to adversarial attacks in which fake accounts alter local edges and features with patterns to resemble real users. In this paper, we present TrustGCN, a Sybil-resilient defense algorithm that combines the idea of social-graph-based defense with GCN. TrustGCN first assigns trust scores to nodes based on the landing probability of short random walks that starts from known real accounts. As this short, supervised random walk is likely to stay within the subgraph consisting of real accounts, most real accounts receive higher trust scores than fakes. Then it introduces these trust scores as edge weights and adopts graph convolution operations to aggregate features of local graph neighborhoods over this weighted graph for classification. In this way, we prevent Sybil partners with low trust scores from contributing to the feature aggregation for a target node, thus is more robust against adverse manipulations of the attackers. Our experiment on real data demonstrates that TrustGCN significantly outperforms GCN in the robustness. To the best of our knowledge, this is the first attempt to combine social-graph-based defenses with graph neural networks into a unified model, paving the way for the robust feature-and-graph-based detection mechanisms.

Today, multi-GPU training has become a common practice for deep learning workloads. The performance of a training job could be affected significantly by both the GPU connectivity in the system topology and the computation-communication pattern of the job. This highlights the necessity of the awareness of jobs’ performance characteristics for cluster schedulers to improve both job and cluster efficiency.In this paper, we propose an online resource-performance model for deep learning training jobs on GPU clusters. This model can estimate the training speed as a function of any given resource setting (i.e., the number and locality of GPUs) for a specific job. The model is based on systematic modeling of the system topology and the communication patterns of individual jobs with online fitting on a sample set of profiled performance data. Experiments show that our performance model achieves 94% prediction accuracy on average (up to 99.9%). Additionally, a large-scale simulation on a real production trace demonstrates that our model helps a typical scheduling algorithm decrease average job completion time by 3.4x and makespan by 1.7x.

Inspired by the successes of convolutional neural networks (CNN) in computer vision, the convolutional operation has been moved beyond low-dimension grids (e.g., images) to high-dimensional graph-structured data (e.g., web graphs, social networks), leading to graph convolutional network (GCN). And GCN has been gaining popularity due to its success in real-world applications such as recommendation, natural language processing, etc. Because neural network and graph propagation have high computation complexity, GPUs have been introduced to both neural network training and graph processing. However, it is notoriously difficult to perform efficient GCN computing on data parallel hardware like GPU due to the sparsity and irregularity in graphs. In this paper, we present PCGCN, a novel and general method to accelerate GCN computing by taking advantage of the locality in graphs. We experimentally demonstrate that real-world graphs usually have the clustering property that can be used to enhance the data locality in GCN computing. Then, PCGCN proposes to partition the whole graph into chunks according to locality and process subgraphs with a dual-mode computing strategy which includes a selective and a full processing methods for sparse and dense subgraphs, respectively. Compared to existing state-of-the-art implementations of GCN on real-world and synthetic datasets, our implementation on top of TensorFlow achieves up to 8.8× speedup over the fastest one of the baselines.

Finding top-k items in data streams is a fundamental problem in data mining. Existing algorithms that can achieve unbiased estimation suffer from poor accuracy. In this paper, we propose a new sketch, WavingSketch, which is much more accurate than existing unbiased algorithms. WavingSketch is generic, and we show how it can be applied to four applications: finding top-k frequent items, finding top-k heavy changes, finding top-k persistent items, and finding top-k Super-Spreaders. We theoretically prove that WavingSketch can provide unbiased estimation, and then give an error bound of our algorithm. Our experimental results show that, compared with the state-of-the-art, WavingSketch has 4.50 times higher insertion speed and up to 9 x 106 times (2 x 104 times in average) lower error rate in finding frequent items when memory size is tight. For other applications, WavingSketch can also achieve up to 286 times lower error rate. All related codes are open-sourced and available at Github anonymously.

Today's companies and organizations build GPU clusters for efficient deep learning training (DLT). However, the inherent heterogeneity of DLT workloads makes it challenging to perform efficient scheduling of the GPUs. On one hand, DLT jobs typically exhibit diverse performance sensitivity to GPU locality; the scheduler should allocate GPUs with appropriate degree of locality for better performance and utilization. On the other hand, DLT jobs are also diverse in terms of size and duration, which can lead to severe cluster fragmentation and less chance for finding GPUs with good locality. In this paper, we present SCHED2, a GPU cluster scheduler that leverages deep reinforcement learning (DRL) to perform smart locality- aware scheduling of DLT jobs. This is achieved by a novel design which captures both jobs' locality- sensitivity and cluster fragmentation condition in the whole learning stack, i.e., from job and cluster state definitions to the neural network architecture. Through this awareness, the DRL model can adjust its scheduling decisions dynamically and adaptively, to react to individual jobs' different locality-sensitivity and changing cluster fragmentation level. Experiments using realistic workloads demonstrate that SCHED2 reduces average JCT by 4.6x and makespan by 2.1x, compared to heuristic-based schedulers.

Existing state machine replication protocols are confronting two major challenges in geo-replication: (1) limited performance caused by load imbalance, and (2) severe performance degradation in heterogeneous environments or under high-contention workloads. This paper presents a new semi-decentralized approach to addressing both the challenges at the same time. Our protocol, SDPaxos, divides the task of a replication protocol into two parts: durably replicating each command across replicas without global order, and ordering all commands to enforce the consistency guarantee. We decentralize the process of replicating commands, which accounts for the largest proportion of load, to provide high performance. In contrast, we centralize the process of ordering commands, which is lightweight but needs a global view, for better performance stability against heterogeneity or contention. The key novelty lies in that SDPaxos achieves the optimal one-round-trip latency under realistic configurations, despite the two separated steps, replicating and ordering, which are both based on Paxos. We also design a recovery protocol to do rapid failover under failures, and a series of optimizations to boost performance. We show via a prototype implementation the significant advantage of SDPaxos on both throughput and latency, facing different environments and workloads.

Online video service has become an emerging application of Internet, playing an important and indispensable role in our daily life. Aiming at relieving the heavy burden on CDN servers, many video service providers deploy a hybrid CDN-P2P system. To minimize the cost of the "last mile delivery" of CDN servers, the system should be able to dispatch video files that receive a large amount of view requests during peak hours to P2P network in advance. However, to accurately predict whether a video will gain popularity is difficult due to the uncertainty of people's viewing tendency. In this paper, we reveal the correlation between the popularity of videos in the daytime and the popularity in peak hours at night based on statistics collected in a real-world large commercial VoD system. Based on our findings, we propose Adaptive Time-Dependent Push Strategy (ATDPS), a scalable push strategy that implements adaptive time-dependent techniques in the hybrid CDN-P2P system. A deep neural network is leveraged to predict the demand of hot videos during peak hours at night. Besides, the system adaptively adjusts the time-dependent strategy of pushing the content of hot videos to the P2P network according to the seed scarcity of the videos in different time periods. Simulations over historical data and pilot deployment on smart routers show that our ATDPS can significantly decrease the addressed bandwidth consumption at peak hours.

Cloud storage services, such as Dropbox, iCloud Drive, Google Drive, and Microsoft OneDrive, have greatly facilitated users' synchronizing files across heterogeneous devices. Among them, Dropbox-like services are particularly beneficial owing to the delta sync functionality that strives towards greater network-level efficiency. However, when delta sync trades computation overhead for network-traffic saving, the tradeoff could be highly unfavorable under some typical workloads. We refer to this problem as the abuse of delta sync. To address this problem, we propose DeltaCFS, a novel file sync framework for cloud storage services by learning from the design of conventional NFS (Network File System). Specifically, we combine delta sync with NFS-like file RPC in an adaptive manner, thus significantly cutting computation overhead on both the client and server sides while preserving the network-level efficiency. DeltaCFS also enables a neat design for guaranteeing causal consistency and fine-grained version control of files. In our FUSE-based prototype system (which is open-source), DeltaCFS outperforms Dropbox by generating up to 11x less data transfer and up to 100x less computation overhead under concerned workloads.

Graph processing systems have been widely used in enterprises like online social networks to process their daily jobs. With the fast growing of social applications, they have to efficiently handle massive concurrent jobs. However, due to the inherent design for a single job, existing systems incur great inefficiency in terms of memory usage, execution and fault tolerance. Motivated by this issue, in this paper we introduce Seraph, a graph processing system that enables efficient job-level parallelism. Seraph is designed based on a decoupled computation model, which decouples both the runtime job data and the computation logic. Decoupling the runtime data allows multiple concurrent jobs to share graph structure data in memory, which fundamentally increases job-level concurrency and reduces fault tolerance overhead. Decoupling computation logic could extend scheduling space, which benefits both execution performance and memory consumption. Seraph adopts a copy-on-write semantic to isolate the graph mutation of concurrent jobs, and a lazy snapshot protocol to generate consistent graph snapshots for jobs submitted at different time. Based on the decoupled model, it provides unified programming interfaces for both synchronous and asynchronous graph applications. Moreover, Seraph implements a lightweight checkpoint mechanism which can tremendously reduce the fault tolerance overhead. The evaluation results show that Seraph significantly outperforms popular systems (such as Giraph, Spark, GraphX and PowerLyra) in both memory usage and job completion time, when executing concurrent graph jobs.

Distributed machine learning is becoming increasingly popular for large scale data mining on large scale cluster. To mitigate the interference of straggler machines, recent distributed machine learning systems support flexible model consistency, which allows worker using a local stale model to compute model update without waiting for the newest model, while limiting the asynchronous step in a certain bound to guarantee the algorithm correctness. However, bounded asynchronous computing can not tolerate consistent straggler. We explore that the root cause of this problem derives from the worker driven parallel training mechanism in existing systems. To address the straggler problem fundamentally and fully leverage the asynchronous efficiency, we propose a novel trigger driven parallel training mechanism, where model server proactively triggers to collect updates from workers instead of passively receiving them, which can inherently avoid the coordinating issue among workers. Besides, we devise a dynamic load balancing strategy to make the sampling frequency of each data equal. Furthermore, bounded asynchronous computing is introduced to achieve the algorithm efficiency, as well as the convergence guarantee. Finally, we integrate the above techniques into a distributed machine learning system called Squirrel. Squirrel provides simple programming interface and can easily deploy machine learning algorithms on distributed cluster. In comparison with traditional worker driven parallel training mechanism, trigger driven mechanism can improve up to 4x faster convergence speed of machine learning algorithm.

Online social networks (OSNs) suffer from the creation of fake accounts that introduce fake product reviews, malware and spam. Existing defenses focus on using the social graph structure to isolate fakes. However, our work shows that Sybils could befriend a large number of real users, invalidating the assumption behind social-graph-based detection. In this paper, we present VoteTrust, a scalable defense system that further leverages user-level activities. VoteTrust models the friend invitation interactions among users as a directed, signed graph, and uses two key mechanisms to detect Sybils over the graph: a voting-based Sybil detection to find Sybils that users vote to reject, and a Sybil community detection to find other colluding Sybils around identified Sybils. Through evaluating on Renren social network, we show that VoteTrust is able to prevent Sybils from generating many unsolicited friend requests. We also deploy VoteTrust in Renen, and our real experience demonstrates that VoteTrust can detect large-scale collusion among Sybils.

In order to process very large graphs, existing graph processing systems, such as Pregel and Giraph, usually partition and distribute the graph computation on large number of nodes (i.e., workers). However, due to the heterogeneity of computing clusters (e.g., nodes with various bandwidth or CPU resource), blindly increasing the number of workers for a job may even degrade the overall performance. In this paper, we address the question of how to distribute the graph computation over the heterogeneous cluster to maximize performance. Based on the practical constraints of current systems, we address this problem in two scenarios. For systems using hash-based partition method (for avoiding the overhead of indexing and searching vertex), we propose a coarse-grained mechanism to greedily select suitable worker set to execute the job. For systems allowing arbitrary graph partition, we further propose a heterogeneity-aware streaming graph partitioning model that can assign workload in fine-grained level. We implement the scheduling mechanisms as a general middleware which can be easily adopted in existing graph computing systems. Our experiments on both university lab cluster (46 machines) and EC2 cluster (100 instances) show that, the proposed framework can significantly improve the execution performance. Compared with the default configurations (i.e., using the whole set of workers and hash-based graph partition), our framework can reduce the overall execution time by 55.9% for lab cluster and 44.7% for EC2 cluster respectively.

GraM is an efficient and scalable graph engine for a large class of widely used graph algorithms. It is designed to scale up to multicores on a single server, as well as scale out to multiple servers in a cluster, offering significant, often over an order-of-magnitude, improvement over existing distributed graph engines on evaluated graph algorithms. GraM is also capable of processing graphs that are significantly larger than previously reported. In particular, using 64 servers (1,024 physical cores), it performs a PageRank iteration in 140 seconds on a synthetic graph with over one trillion edges, setting a new milestone for graph engines.

Putting computers into low power mode (e.g., suspend-to-RAM) could potentially save significant amount of power when the computers are not in use. Unfortunately, this is often infeasible in practice because data stored on the computers (i.e., directly attached disks, DAS) might need to be accessed by others. Separating storage from computation by attaching storage on the network (e.g., NAS and SAN) could potentially solve this problem, at the cost of lower performance, more network congestion, increased peak power consumption, and higher equipment cost. Though DAS does not suffer these problems, it is not flexible for power saving. In this paper, we present DSwitch, an architecture that, depending on the workload, allows a disk to be attached either directly or through network. We design flexible workload migration based on DSwitch, and show that a wide variety of applications in both data center and home/office settings can be well supported. The experiments demonstrate that our prototype DSwitch achieves a power savings of 91.9% to 97.5% when a disk is in low power network attached mode, while incurring no performance degradation and minimal power overhead when it is in high performance directly attached mode.

Cloud storage services allow files to be synchronized among multiple users or devices easily. To minimize the amount of network traffic, these services utilize incremental data synchronization techniques. However, little is known about their particular mechanisms and corresponding efficiency. In this paper, we focus on Dropbox, the most popular cloud storage service, as a case study. We examine the bandwidth consumption on the Dropbox client under typical synchronization scenarios, and find that Dropbox wastes a lot of traffic due to matching unrelated chunks to compute incremental changes. More seriously, when file conflicts among clients, Dropbox directly downloads the whole file instead of the incremental changes. To solve these problems, we design and implement an efficient incremental synchronization system named Minbox. MinBox employs an efficient locality-sensitive hash for better similar chunk matching. Moreover, Minbox could forward the incremental changes during confliction by maintaining the relation of conflicting files. In comparison with Dropbox, Minbox significantly reduces network traffic and resolves file conflict with little overhead.

Recent trend in cloud computing demands vast and ever increasing storage capacity for data centers. For many cloud service providers, much of the storage capacity demand is driven by cold and archival data, such as user uploaded contents, system logs, and backups. In this paper, we describe UStore, a hard disk based storage system designed for such workloads. We make the assumption that most data centers are already populated with computer servers and networking gears, and propose a solution to attach additional disks to these servers reliably at extremely low cost. The main component of UStore is a novel fat tree interconnect fabric to connect hard disks to existing servers and network infrastructure. To reduce cost, UStore leverages the mature commodity USB 3.0 technology to build the fabric, which has extremely low amortized cost per disk while still providing sufficient throughput to satisfy cold and archival workload. The software of the UStore system abstracts the system's physical topology and provides a consistent view of the storage capacity to the upper layer services such as distributed file systems or backup services. In a sense, UStore can be regarded as external USB hard disks designed for data centers.

Nowadays, more and more enterprises and organizations are hosting their data into the cloud, in order to reduce the IT maintenance cost and enhance the data reliability. However, facing the numerous cloud vendors as well as their heterogenous pricing policies, customers maywell be perplexed with which cloud(s) are suitable for storing their data and what hosting strategy is cheaper.The general status quo is that customers usually put their data into a single cloud (which is subject to the vendor lock-in risk) and then simply trust to luck. Based on comprehensive analysis of various state-of-the-art cloud vendors, this paper proposes a novel data hosting scheme (named CHARM) which integrates two key functions desired. The first is selecting several suitable clouds and an appropriate redundancy strategy to store data with minimized monetary cost and guaranteed availability. The second is triggering a transition process to re-distribute data according to the variations of data access pattern and pricing of clouds. We evaluate the performance of CHARM using both trace-driven simulations and prototype experiments. The results show that compared with the major existing schemes, CHARM not only saves around 20 percent of monetary cost but also exhibits sound adaptability to data and price adjustments.

Cloud services and other online applications are having imperative requirements on wide service coverage, fast content delivery and more importantly low monetary investment. To this end, online relay networks that consist of widespread free edge-servers (edge-ORN for short) are emerging to compete with traditional Content Delivery Networks (CDNs). With an ever-increasing amount of traffic, edge-ORN is now in urgent need of high-effective traffic engineering (TE) solutions. This paper presents a first TE study for this new type of network. In specific, we develop a lightweight TE method which jointly optimizes user-perceived latency and inter-autonomous system traffic. Three major contributions are made: 1) determine the right TE scheme for edge-ORN scenario; 2) correctly formulate and model the TE problem; 3) develop a fast yet efficient algorithm to solve the model, making it applicable to large-scale edge-ORNs. Experiments on a real-world trace show that, our method significantly outperforms other TE methods, achieving near-optimal TE effect. Furthermore, the method takes short computation time, which is of essential importance for edge-ORNs performing timely TE.

Graph processing systems have been widely used in enterprises like online social networks to process their daily jobs. With the fast growing of social applications, they have to efficiently handle massive concurrent jobs. However, due to the inherent design for single job, existing systems incur great inefficiency in memory use and fault tolerance. Motivated by this, in this paper we introduce Seraph, a graph processing system that enables efficient job-level parallelism. Seraph is designed based on a decoupled data model, which allows multiple concurrent jobs to share graph structure data in memory. Seraph adopts a copy-on-write semantic to isolate the graph mutation of concurrent jobs, and a lazy snapshot protocol to generate consistent graph snapshots for jobs submitted at different time. Moreover, Seraph adopts an incremental checkpoint/regeneration model which can tremendously reduce the overhead of checkpointing. We have implemented Seraph, and the evaluation results show that Seraph significantly outperforms popular systems (such as Giraph and Spark) in both memory usage and job completion time, when executing concurrent graph jobs.

Cloud storage services such as Dropbox, Google Drive, and Microsoft OneDrive provide users with a convenient and reliable way to store and share data from anywhere, on any device, and at any time. The cornerstone of these services is the data synchronization (sync) operation which automatically maps the changes in users' local filesystems to the cloud via a series of network communications in a timely manner. If not designed properly, however, the tremendous amount of data sync traffic can potentially cause (financial) pains to both service providers and users.

Sybil accounts are fake identities created to unfairly increase the power or resources of a single malicious user. Researchers have long known about the existence of Sybil accounts in online communities such as file-sharing systems, but they have not been able to perform large-scale measurements to detect them or measure their activities. In this article, we describe our efforts to detect, characterize, and understand Sybil account activity in the Renren Online Social Network (OSN). We use ground truth provided by Renren Inc. to build measurement-based Sybil detectors and deploy them on Renren to detect more than 100,000 Sybil accounts. Using our full dataset of 650,000 Sybils, we examine several aspects of Sybil behavior. First, we study their link creation behavior and find that contrary to prior conjecture, Sybils in OSNs do not form tight-knit communities. Next, we examine the fine-grained behaviors of Sybils on Renren using clickstream data. Third, we investigate behind-the-scenes collusion between large groups of Sybils. Our results reveal that Sybils with no explicit social ties still act in concert to launch attacks. Finally, we investigate enhanced techniques to identify stealthy Sybils. In summary, our study advances the understanding of Sybil behavior on OSNs and shows that Sybils can effectively avoid existing community-based Sybil detectors. We hope that our results will foster new research on Sybil detection that is based on novel types of Sybil features.

Online social networks (OSNs) currently face a significant challenge by the existence and continuous creation of fake user accounts (Sybils), which can undermine the quality of social network service by introducing spam and manipulating online rating. Recently, there has been much excitement in the research community over exploiting social network structure to detect Sybils. However, they rely on the assumption that Sybils form a tight-knit community, which may not hold in real OSNs. In this paper, we present VoteTrust, a Sybil detection system that further leverages user interactions of initiating and accepting links. VoteTrust uses the techniques of trust-based vote assignment and global vote aggregation to evaluate the probability that the user is a Sybil. Using detailed evaluation on real social network (Renren), we show VoteTrust's ability to prevent Sybils gathering victims (e.g., spam audience) by sending a large amount of unsolicited friend requests and befriending many normal users, and demonstrate it can significantly outperform traditional ranking systems (such as TrustRank or BadRank) in Sybil detection.

Nowadays, content sharing using P2P networks is one of the most important Internet applications. As these networks gain more popularity, boosting the propagation of newly-uploaded objects becomes critically important. Rapid propagation would enable networks to protect object availability against seed departure, and make themselves the ideal distribution platform for user-generated content. Through real experience, we find that even adopting a simple word-of-mouth exchange can enhance content spread, especially by exposing users to diverse content and speeding up the propagation of objects with high potential demand. To further exploit such benefits, a more intelligent exchange approach is needed to balance propagation speed and diversity through the ever-growing amount of objects. Hence, we propose a lightweight peer selection algorithm, PROB (PROportional random Browse). PROB adopts a model-driven approach to optimize the expected downloading throughput while maintaining diversity. Moreover, it achieves the balance in a stateless and probabilistic manner, thus reducing complexity and enabling practical deployment. Our trace based simulation and real deployment demonstrate that PROB can significantly speedup content spread compared with random/deterministic approaches.

Content distribution on today's Internet operates primarily in two modes: server-based and peer-to-peer (P2P). To leverage the advantages of both modes while circumventing their key limitations, a third mode: peer-to-server/peer (P2SP) has emerged in recent years. Although P2SP can provide efficient hybrid server-P2P content distribution, P2SP generally works in a closed manner by only utilizing its private owned servers to accelerate its private organized peer swarms. Consequently, P2SP still has its limitations in both content abundance and server bandwidth. To this end, the fourth mode (or says a generalized mode of P2SP) has appeared as "open-P2SP" that integrates various third-party servers, contents, and data transfer protocols all over the Internet into a large, open, and federated P2SP platform. In this paper, based on a large-scale commercial open-P2SP system named "QQXuanfeng" , we investigate the key challenging problems, practical designs and real-world performances of open-P2SP. Such "white-box" study of open-P2SP provides solid experiences and helpful heuristics to the designers of similar systems.

Popular online social networks (OSNs) like Facebook and Twitter are changing the way users communicate and interact with the Internet. A deep understanding of user interactions in OSNs can provide important insights into questions of human social behavior and into the design of social platforms and applications. However, recent studies have shown that a majority of user interactions on OSNs are latent interactions , that is, passive actions, such as profile browsing, that cannot be observed by traditional measurement techniques. In this article, we seek a deeper understanding of both active and latent user interactions in OSNs. For quantifiable data on latent user interactions, we perform a detailed measurement study on Renren, the largest OSN in China with more than 220 million users to date. All friendship links in Renren are public, allowing us to exhaustively crawl a connected graph component of 42 million users and 1.66 billion social links in 2009. Renren also keeps detailed, publicly viewable visitor logs for each user profile. We capture detailed histories of profile visits over a period of 90 days for users in the Peking University Renren network and use statistics of profile visits to study issues of user profile popularity, reciprocity of profile visits, and the impact of content updates on user popularity. We find that latent interactions are much more prevalent and frequent than active events, are nonreciprocal in nature, and that profile popularity is correlated with page views of content rather than with quantity of content updates. Finally, we construct latent interaction graphs as models of user browsing behavior and compare their structural properties, evolution, community structure, and mixing times against those of both active interaction graphs and social graphs.

Hybrid cloud-P2P content distribution (“CloudP2P”) provides a promising alternative to the conventional cloud-based or peer-to-peer (P2P)-based large-scale content distribution. It addresses the potential limitations of these two conventional approaches while inheriting their advantages. A key strength of CloudP2P lies in the so-called bandwidth multiplier effect: by appropriately allocating a small portion of cloud (server) bandwidth Sito a peer swarm i (consisting of users interested in the same content) to seed the content, the users in the peer swarm - with an aggregate download bandwidth Di- can then distribute the content among themselves; we refer to the ratio Di/Sias the bandwidth multiplier (for peer swarm i). A major problem in the design of a CloudP2P content distribution system is therefore how to allocate cloud (server) bandwidth to peer swarms so as to maximize the overall bandwidth multiplier effect of the system. In this paper, using real-world measurements, we identify the key factors that affect the bandwidth multipliers of peer swarms and thus construct a fine-grained performance model for addressing the optimal bandwidth allocation problem (OBAP). Then we develop a fast-convergent iterative algorithm to solve OBAP. Both trace-driven simulations and prototype implementation confirm the efficacy of our solution.

Despite the increasing popularity, Internet video streaming to mobile devices is still challenging. In particular, there has been a format and resolution "gap" between Internet videos and mobile devices, so mobile users have high demand on video transcoding to facilitate their specific devices. However, as a computation-intensive work, video transcoding is greatly challenged by the limited battery capacity of mobile devices. In this paper we propose and implement "Cloud Transcoder", which utilizes an intermediate cloud platform to bridge the "gap" via its special and practical designs. Specifically, Cloud Transcoder only requires the user to upload a video request rather than the video content. After getting the video request, Cloud Transcoder downloads the original video from the Internet, transcodes it on the user's demand, and transfers the transcoded video back to the user with a high data rate via the intra-cloud data transfer acceleration. Therefore, the mobile device only consumes energy in the last step - fast retrieving the transcoded video from the cloud. Running logs of our real-deployed system confirm the efficacy of Cloud Transcoder.

Social trust and recommendation services are the most popular social rating systems today for service providers to learn about the social opinion or popularity of a product, item, or service, such as a book on Amazon, a seller on eBay, a story on Digg or a movie on Netflix. Such social rating systems are very convenient and offer alternative learning environments for decision makers, but they open the door for attackers to manipulate the social rating systems by selfishly promoting or maliciously demoting certain items. Although a fair amount of effort has been made to understand various risks and possible defense mechanisms to counter such attacks, most of the existing work to date has been devoted to studying specific types of attacks and their countermeasures. In this article, we argue that vulnerabilities in social rating systems and their countermeasures should be examined and analyzed in a systematic manner. We first give an overview of the common vulnerabilities and attacks observed in some popular social rating services. Next, we describe three types of attack strategies in two types of social rating systems, including a comprehensive theoretical analysis of their attack effectiveness and attack costs. Three context-aware countermeasures are then presented: (i) hiding user-item relationships, (ii) using confidence weight to distinguish popular and unpopular items, and (iii) incorporating time windows in trust establishment. We also provide an in-depth discussion on how these countermeasures can be used effectively to improve the robustness and trustworthiness of the social rating services.

P2P file-sharing systems have been suffering from file unavailability or poor download speed due to lack of file replicas. As a result, to download rare files, users are typically forced to pay long online waiting time (i.e., always-on strategy), which is unacceptable for most users. To get over this, several commercial P2P systems launch an offline download service, employing stable and high-capacity servers to take over the downloads. Thus users can log off and wait offline. While offline download shows a notable trend of growing popular, there has been little insight into its detailed QoS (i.e., success ratio and download time) provision and QoS characteristics. Through trace-driven simulation study, this paper quantitatively reveals the potential QoS provision of offline download, confirming that it can achieve high download success ratio (over 90%) with tolerable waiting time (less than 2 days in most cases). We further find that the retrieval of rare file is dramatically affected by any single replica's participation or leave, resulting in wildly fluctuated download time. The wild fluctuation prevents users from well perceiving the expected QoS of their offline downloads, leading to poor user experience. Motivated by this, we develop a QoS prediction method for offline download. Experiments show that the prediction achieves high accuracy and precision. Finally, we implement a prototype of offline download service, called SimpleOD, and present our experience of the QoS provision and the prediction performance in practice.

Sybil accounts are fake identities created to unfairly increase the power or resources of a single user. Researchers have long known about the existence of Sybil accounts in online communities such as file-sharing systems, but have not been able to perform large scale measurements to detect them or measure their activities. In this paper, we describe our efforts to detect, characterize and understand Sybil account activity in the Renren online social network (OSN). We use ground truth provided by Renren Inc. to build measurement based Sybil account detectors, and deploy them on Renren to detect over 100,000 Sybil accounts. We study these Sybil accounts, as well as an additional 560,000 Sybil accounts caught by Renren, and analyze their link creation behavior. Most interestingly, we find that contrary to prior conjecture, Sybil accounts in OSNs do not form tight-knit communities. Instead, they integrate into the social graph just like normal users. Using link creation timestamps, we verify that the large majority of links between Sybil accounts are created accidentally, unbeknownst to the attacker. Overall, only a very small portion of Sybil accounts are connected to other Sybils with social links. Our study shows that existing Sybil defenses are unlikely to succeed in today's OSNs, and we must design new techniques to effectively detect and defend against Sybil attacks.

Video content distribution dominates the Internet traffic. The state-of-the-art techniques generally work well in distributing popular videos, but do not provide satisfactory content distribution service for unpopular videos due to low data health or low data transfer rate. In recent years, the worldwide deployment of cloud utilities provides us with a novel perspective to consider the above problem. We propose and implement the cloud download scheme, which achieves high-quality video content distribution by using cloud utilities to guarantee the data health and enhance the data transfer rate. Specifically, a user sends his video request to the cloud which subsequently downloads the video from the Internet and stores it in the cloud cache. Then the user can usually retrieve his requested video (whether popular or unpopular) from the cloud with high data rate in any place at any time, via the intra-cloud data transfer acceleration. Running logs of our real deployed commercial system (named VideoCloud) confirm the effectiveness and efficiency of cloud download. The users' average data transfer rate of unpopular videos exceeds 1.6 Mbps, and over 80% of the data transfer rates are more than 300 Kbps which is the basic playback rate of online videos. Our study provides practical experiences and valuable heuristics for making use of cloud utilities to achieve efficient Internet services.

The heterogeneous nature of Peer-to-Peer (P2P) networks can be exploited to optimize a wide range of applications. But this requires an accurate characterization of peer heterogeneity, which is difficult due to huge population and disparate properties of individuals. To overcome this barrier, we conduct a thorough inspection of peer heterogeneity in terms of individual churn and resource capacity. We make a first attempt to (i) experimentally reduce heterogeneous churn and resource dynamics to simple distributions with individual-specific parameters, and to (ii) provide an empirical support for the heterogeneous Markov model of churn. We further demonstrate how our characterization can be leveraged to optimize practical systems, through two case studies: fast backup in online storage and fault-tolerance in cycle-sharing systems. Both applications gain remarkable performance improvement by incorporating our model of peer heterogeneity.

When applied in high-churn Internet environments, P2P systems face a dilemma: although most participants are too unstable, a P2P system requires sufficient stable peers to provide satisfactory core services. Thus, determining how to leverage unstable nodes seems to be the only choice. Our primary idea is to group unstable nodes together in order to form an adequate number of stable service groups. Focusing on this topic, our main findings are three-fold: 1) A general analytical model to investigate the grouping process of P2P systems is established, in which the stability-scalability trade-off problem is paid special attention to. 2) We formalize the target of grouping as the Maximum Stability Grouping (MSG) problem. It proves to be not only NP-hard, but also infeasible; therefore, we restrict it to a feasible Homogeneous MSG (H-MSG) problem and deduce its optimal solution under the stochastic model. 3) We propose a homogeneous grouping strategy to fulfill the optimal solution. Comprehensive simulations have been performed on generated data sets and real-world traces from a P2P storage system and a P2P streaming system. Results show that our grouping strategy effectively captures the stability-scalability trade-off: besides excellent stability, it gains much higher stable service capacity, with acceptable loss in scalability.

Maintaining a given level of data redundancy is a fundamental requirement of peer-to-peer (P2P) storage systems—to ensure desired data availability, additional replicas must be created when peers fail. Since the majority of failures in P2P networks are transient (i.e., peers return with data intact), an intelligent system can reduce significant replication costs by not replicating data following transient failures. Reliably distinguishing permanent and transient failures, however, is a challenging task, because peers are unresponsive to probes in both cases. In this paper, we propose Protector, an algorithm that enables efficient replication policies by estimating the number of “remaining replicas” for each object, including those temporarily unavailable due to transient failures. Protector dramatically improves detection accuracy by exploiting two opportunities. First, it leverages failure patterns to predict the likelihood that a peer (and the data it hosts) has permanently failed given its current downtime. Second, it detects replication level across groups of replicas (or fragments), thereby balancing false positives for some peers against false negatives for others. Extensive simulations based on both synthetic and real traces show that Protector closely approximates the performance of a perfect “oracle” failure detector, and significantly outperforms time-out-based detectors using a wide range of parameters. Finally, we design, implement and deploy an efficient P2P storage system called AmazingStore by combining Protector with structured P2P overlays. Our experience proves that Protector enables efficient long-term data maintenance in P2P storage systems.

This paper presents MAPS - a personalized Multi-Attribute Probabilistic Selection framework - to estimate the probability of an item being a user's best choice and rank the items accordingly. The MAPS framework makes three original contributions in this paper. First, we capture the inter-attribute t

Popular online social networks (OSNs) like Facebook and Twitter are changing the way users communicate and interact with the Internet. A deep understanding of user interactions in OSNs can provide important insights into questions of human social behavior, and into the design of social platforms and applications. However, recent studies have shown that a majority of user interactions on OSNs are latent interactions, passive actions such as profile browsing that cannot be observed by traditional measurement techniques. In this paper, we seek a deeper understanding of both visible and latent user interactions in OSNs. For quantifiable data on latent user interactions, we perform a detailed measurement study on Renren, the largest OSN in China with more than 150 million users to date. All friendship links in Renren are public, allowing us to exhaustively crawl a connected graph component of 42 million users and 1.66 billion social links in 2009. Renren also keeps detailed visitor logs for each user profile, and counters for each photo and diary/blog entry. We capture detailed histories of profile visits over a period of 90 days for more than 61,000 users in the Peking University Renren network, and use statistics of profile visits to study issues of user profile popularity, reciprocity of profile visits, and the impact of content updates on user popularity. We find that latent interactions are much more prevalent and frequent than visible events, non-reciprocal in nature, and that profile popularity are uncorrelated with the frequency of content updates. Finally, we construct latent interaction graphs as models of user browsing behavior, and compare their structural properties against those of both visible interaction graphs and social graphs.

As the digital data rapidly inflates to a world-wide storage crisis, data deduplication is showing its increasingly prominent function in data storage. Driven by the problems behind the mainstream server-side deduplication schemes, recently there has been a tendency of introducing peer-assisted methods into the deduplication systems. However, this topic is still quite vague at present and lacks thorough research. In this paper, we conduct in-depth and quantitative investigation on the peer-assisted deduplication. Through measurements we observe that the inter-peer duplication accounts for a large proportion of the total duplication, and exhibits strong peer locality. Then based on our observations, we propose PeerDedupe, a novel peer-assisted sampling deduplication approach. Experiments show that PeerDedupe can remove over 98% duplication with each peer coordinating with no more than 5 other peers, and it requires much less server RAM usage than the existing works.

With the popularity of voting systems in cyberspace, there is growing evidence that current voting systems can be manipulated by fake votes. This problem has attracted many researchers working on guarding voting systems in two areas: relieving the effect of dishonest votes by evaluating the trust of voters, and limiting the resources that can be used by attackers, such as the number of voters and the number of votes. In this paper, we argue that powering voting systems with trust and limiting attack resources are not enough. We present a novel attack named as Reputation Trap (RepTrap). Our case study and experiments show that this new attack needs much less resources to manipulate the voting systems and has a much higher success rate compared with existing attacks. We further identify the reasons behind this attack and propose two defense schemes accordingly. In the first scheme, we hide correlation knowledge from attackers to reduce their chance to affect the honest voters. In the second scheme, we introduce robustness-of-evidence, a new metric, in trust calculation to reduce their effect on honest voters. We conduct extensive experiments to validate our approach. The results show that our defense schemes not only can reduce the success rate of attacks but also significantly increase the amount of resources an adversary needs to launch a successful attack.

User behavior models are important for building realistic simulation environment for research on P2P multimedia file-sharing systems. In this paper, we build a user download behavior model and a user removal behavior model, which can describe important user characteristics that are not captured in the existing models. The proposed download behavior model incorporates retry behavior, and the removal behavior model integrates free-riding, file usage, and file removal. Based on two-year real user logs, we derive the range of all the model parameters and generate many interesting observations. To validate the proposed models, we compare several models in a case study on the number of living replicas in P2P file-sharing systems. The results demonstrate the accuracy, usability, and advantage of the proposed models.

P2P storage systems use replication to provide a certain level of availability. While the system must generate new replicas to replace replicas lost to permanent failures, it can save significant replication cost by not replicating following transient failures. However, in real systems, it is impossible to reliably distinguish permanent and transients failures, resulting in a tradeoff between high recovery cost and low data availability. In this paper, we analyze the use of timeouts as a mechanism to navigate this tradeoff. We address the challenging problem of how to choose a timeout to walk the fine line between causing unnecessary replication due to detection inaccuracy, and reducing availability due to detection delay. We conduct simulations based both on synthetic and real traces, and show that the performance of our selected timeout closely approximates the optimal performance that can be achieved by timeouts, and even that of an ¿oracle¿ failure detector.

Peer-to-Peer (P2P) applications have been consuming an increasingly significant fraction of Internet bandwidth. They are becoming a financial burden to Internet Service Providers (ISPs), creating hot spots in the Internet, and causing potential performance degradation to other applications. As a result, there has been increasing tensions between P2P applications and network service providers. In this paper, we propose a framework called SODA for P2P applications to be self-adaptive and optimize their demands in order to more efficiently utilize network resources. Through preliminary experiments using two representative P2P applications, we demonstrate that SODA can effectively reduce bandwidth consumption by adapting the demands among peers.

Abstract To achieve high data availability or reliability in an efficient manner, distributed storage systems must detect whether an observed node failure is permanent or transient, and if necessary, generate replicas to restore the desired level of replication. Given the unpredictability of network dynamics, however, distinguishing permanent and transient failures is extremely difficult. Though timeout‐based detectors can be used to avoid mistaking transient failures as permanent failures, it is unknown how the timeout values should be selected to achieve a better tradeoff between detection latency and accuracy. In this paper, we address this fundamental tradeoff from several perspectives. First, we explore the impact of different timeout values on maintenance cost by examining the probability of their false positives and false negatives. Second, we propose a self‐configurable failure detector called the Neutralizer based on the idea of counteracting false positives with false negatives. The Neutralizer could enable the system to maintain a desired replication level on average with the least amount of bandwidth. We conduct extensive simulations using real trace data from a widely deployed peer‐to‐peer system and synthetic traces based on PlanetLab and Microsoft PCs, showing a significant reduction in aggregate bandwidth usage after applying the Neutralizer (especially in an environment with a low average node availability). Overall, we demonstrate that the Neutralizer closely approximates the performance of a perfect ‘oracle’ detector in many cases. Copyright © 2008 John Wiley & Sons, Ltd.

Skyline queries are capable of retrieving interesting points from a large data set according to multiple criteria. Most work on skyline queries so far has assumed a centralized storage, whereas in practice relevant data are often distributed among geographically scattered sites. In this work, we tackle constrained skyline queries in large-scale distributed environments without the assumption of any overlay structures, and propose a novel algorithm named PaDSkyline (Parallel distributed Skyline query processing). PaDSkyline significantly shortens the response time by performing parallel processing over site groups produced by a partition algorithm. Within each group, it locally optimizes the query processing over distributed sites. It also drastically enhances the network transmission efficiency by performing early reduction of skyline candidates with deliberately selected multiple filtering points. Results of extensive experiments demonstrate the efficiency and robustness of our proposals.

Reputation systems are playing critical roles in securing today's distributed computing and communication systems. Similar to other security mechanisms, reputation systems can be under attack. In this paper, we report the discovery of a new attack, named RepTrap(Reputation Trap), against feedback-based reputation systems, such as those used in P2P file-sharing systems and E-commerce websites(e.g. Amazon.com). We conduct an in-depth investigation on this new attack, including analysis, case study, and performance evaluation based on real data and realistic user behavior models. We discover that the RepTrap is a strong and destructive attack that can manipulate the reputation scores of users, objects, and even undermine the entire reputation system. Compared with other known attacks that achieve the similar goals, the RepTrap requires less effort from the attackers and causes multi-dimensional damage to the reputation systems.

Distributed storage systems often use data replication to mask failures and guarantee high data availability. Node failures can be transient or permanent. While the system must generate new replicas to replace replica lost to permanent failures, it can save significant replication costs by not replicating following transient faults. Given the unpredictability of network dynamics, however, distinguishing permanent and transient failures is extremely difficult. Traditional timeout approaches are difficult to tune and can introduce unnecessary replication. In this paper, we propose Protector, an algorithm that addresses this problem using network-wide statistical prediction. Our algorithm drastically improves prediction accuracy by making predictions across aggregate replica groups instead of single nodes. These estimates of the number of "live replicas" can guide efficient data replication policies. We prove that given data on node down times and the probability of permanent failures, the estimate given by our algorithm is more accurate than all alternatives. We describe two ways to obtain the failure probability function driven by models or traces. We conduct extensive simulations based both on synthetic and real traces, and show that Protector closely approximates the performance of a perfect "oracle" failure detector, while significantly outperforming timeout-based detectors using a wide range of parameters.

Abstract Much work has been done to address the need for incentive models in real deployed peer‐to‐peer networks. In this paper, we discuss problems found with the incentive model in a large, deployed peer‐to‐peer network, Maze. We evaluate several alternatives, and propose an incentive system that generates preferences for well‐behaved nodes while correctly punishing colluders. We discuss our proposal as a hybrid between Tit‐for‐Tat and EigenTrust, and show its effectiveness through simulation of real traces of the Maze system. Copyright © 2007 John Wiley & Sons, Ltd.

Peer-to-peer networks often use incentive policies to encourage cooperation between nodes. Such systems are generally susceptible to collusion by groups of users in order to gain unfair advantages over others. While techniques have been proposed to combat Web spam collusion, there are few measurements of real collusion in deployed systems. In this paper, we report analysis and measurement results of user collusion in Maze, a large-scale peer-to-peer file sharing system with a non-net-zero point-based incentive policy. We search for colluding behavior by examining complete user logs, and incrementally refine a set of collusion detectors to identify common collusion patterns. We find collusion patterns similar to those found in Web spamming. We evaluate how proposed reputation systems would perform on the Maze system. Our results can help guide the design of more robust incentive schemes.

The following topics are dealt with: peer-to-peer computing; security, trust and reputation; searching and query management; peer-to-peer systems routing; overlay networks; data management; and overlay construction.

The architecture of P2P file-sharing applications has been developing to meet the needs of large scale demands. The structured overlay network, also known as DHT, has been used in these applications to improve the scalability, robustness of the system, and to make it free from single-point failure. We believe that the measurement study of the overlay network used in the real file-sharing P2P systems can provide guidance for the designing of such systems, and improve the performance of the system. In this paper, we perform the measurement in two different aspects. First, the modified client provides view to the overlay network from a single user vision. Second, the instances of crawler programs deployed in many nodes managed to crawl the user information of the overlay network as much as possible. We find vulnerability in the overlay network, combined with the character of the DNS service; a more serious DDos attack can be launched

Abstract The CSFS (cryptographic storage file system) is a network file storage system that is suitable for a small‐to‐medium sized networks such as a campus network. In a CSFS, a lot of distributed file servers are organized in a star‐liked architecture. File names are stored in a name server and file data are stored in distributed file servers. A CSFS has good scalability and is able to accommodate hundreds of file servers. We implemented a CSFS in pure Java and tested the system with a benchmark. The test results show that CSFS delivers acceptable performance for general file operations. Its performance of file upload and download is as efficient as FTP. It can support more than 450 concurrent online users. Copyright © 2005 John Wiley & Sons, Ltd.