The Honeynet, as a typical active defense strategy, traps attackers' malicious behaviors, changing the asymmetric situation of network attack and defense. However, a static honeynet system would create a single deception environment, making it difficult to be effective against complex attacks. Additionally, the virtual honeypots are susceptible to exploitation by attackers, potentially leading to virtual escapes. To address the above issues, we propose a game theory-based method for secure deployment of mimic honeynet to enhance the deception capabilities of a honeynet and improve the security of honeypots. We construct multi-layer mimic honeypots and dynamically schedule the business executors within the mimic honeypot according to the virtualization layer's adjudication results, effectively preventing attacker escape attempts. We construct a Bayesian game model of attack and defense for the mimic honeynet, incorporating factors such as the attractiveness of the mimic honeypot and the similarity of the business layer. The aim of this game theory model is to determine the optimal mimic honeypot deployment strategy for a dynamic honeynet. Simulation results demonstrate that the mimic honeynet proposed in this paper effectively captures more malicious attack behaviors, reduces the probability of real hosts being attacked, and strengthens the security of the honeypot itself.

With the advancement of deep learning, network communication has become the most critical factor in model training. Especially, the all-reduce operation can comprise over 70% of the cumulative training duration as a pivotal component within data parallelism. However, existing all-reduce algorithms often perform poorly in complex network topologies, and there is currently no universal and straightforward all-reduce algorithm that can effectively adapt to diverse topological structures.In this work, we propose a topology decoupled all-reduce algorithm. We decouple the network into multiple tree substructures, select the trees with the smallest heights, and then split the data to perform aggregate communication within these selected structures. This approach significantly reduces the number of communications and enhances efficiency. Experimental results show that our topology decoupled all-reduce algorithm reduces communication time compared to NCCL’s by 42.9% and enhances end-to-end training efficiency by 11.7%.

Decentralized Finance (DeFi), in which digital assets are exchanged without trusted intermediaries, has grown rapidly in value in recent years. Stablecoins , which are pegged to a non-volatile asset such as the US dollar, are a prominent feature of DeFi as they mitigate the risk associated with price fluctuations. However, existing stablecoin systems are tied to individual blockchain platforms, and trusted parties or complex protocols are needed to exchange stablecoin tokens between blockchains. Our goal is to design a practical stablecoin system for cross-chain commerce, and to do so we must overcome two main challenges. The first is to support a large and growing number of blockchains efficiently. The second is for the stablecoin to be resilient to blockchain platform failures and to price fluctuations that affect its collateral. We present CroCoDai to address these challenges. We demonstrate CroCoDai ’s efficiency by comparing the performance of a prototype implementation to related baselines, and its resilience through an empirical analysis of historical token price data.

Machine unlearning involves retracting data records and reducing their influence on trained models, aiding user privacy protection, at a significant computational cost potentially. Weight perturbation-based unlearning is common but typically modifies parameters globally. We propose fine-grained Top-K and Random-k parameters perturbed inexact machine unlearning that address the privacy needs while keeping the computational costs tractable. However, commonly used training data are independent and identically distributed, for inexact machine unlearning, current metrics are inadequate in quantifying unlearning degree that occurs after unlearning. To address this quantification issue, we introduce SPD-GAN, which subtly perturbs data distribution targeted for unlearning. Then, we evaluate unlearning degree by measuring the performance difference of the models on the perturbed unlearning data before and after unlearning. Furthermore, to demonstrate efficacy, we tackle the challenge of evaluating machine unlearning by assessing model generalization across unlearning and remaining data. To better assess the unlearning effect and model generalization, we propose novel metrics, namely, the forgetting rate and memory retention rate. By implementing these innovative techniques and metrics, we achieve computationally efficacious privacy protection in machine learning applications without significant sacrifice of model performance. A by-product of our work is a novel method for evaluating and quantifying unlearning degree.

New categories may be introduced over time, or existing categories may need to be reclassified. Class incremental learning (CIL) is employed for the gradual acquisition of knowledge about new categories while preserving information about previously learned ones in such dynamic environments. It might also be necessary to also eliminate the influence of related categories on the model to adapt to reclassification. We thus introduce class-level machine unlearning (MU) within CIL. Typically, MU methods tend to be time-consuming and can potentially harm the model’s performance. A continuous stream of unlearning requests could lead to catastrophic forgetting. To address these issues, we propose a non-destructive eCIL-MU framework based on embedding techniques to map data into vectors and then be stored in vector databases. Our approach exploits the overlap between CIL and MU tasks for acceleration. Experiments demonstrate the capability of achieving unlearning effectiveness and orders of magnitude (upto ~ 278×) of acceleration.

Coded blockchains have acquired prominence in the recent past as a promising approach to slash the storage costs as well as to facilitate scalability. Within this class, Luby Transform (LT) coded blockchains are an appealing choice for scalability in heterogeneous networks owing to the availability of a wide range of low-complexity LT decoders. While these architectures have been studied from the aspects of storage savings and scalability, not much is known in terms of their security vulnerabilities. Pointing at this research gap, in this work, we present novel denial-of-service (DoS) threats on LT coded blockchains that target nodes with specific decoding capabilities, thereby preventing them from joining the network. Our proposed threats are non-oblivious in nature, wherein adversaries gain access to the archived blocks, and choose to execute their threat on a subset of them based on underlying coding scheme. We show that our optimized threats can achieve the same level of damage as that of blind attacks, however, with limited amount of resources. This is the first work of its kind that opens up new questions on designing coded blockchains to jointly provide storage savings, scalability and resilience to optimized threats.

A practical Multi-authority attribute-based encryption (MA-ABE) scheme with privacy-preserving properties realized by Inner Product Predicate Encryption (IPPE) was introduced by Michalevksy and Joye at ESORICS 2018. It requires secret keys linked to an attribute vector v and ciphertext associated with policy vector x to satisfy a certain predicate P(x, v) for decryption. Notably, the attribute information remains undisclosed during ciphertext inspection, provided no additional information about x and v is available. Despite extensive discussions in the literature concerning its efficiency, decentralization, and access policy structure, the security of certain schemes under the fully adaptive security model—first defined by Datta, Komargodski, and Waters at Eurocrypt 2023, which reflects real-world situations—has not been sufficiently explored. Specifically, their scheme is vulnerable to rogue-key attacks: an adversary can compromise a single attribute authority and then adaptively delay the publication of the compromised authority’s public key, crafting it based on the public keys of all other authorities. This ability to introduce a rogue key by compromising a single authority poses a significant security risk, as the adversary could decrypt any ciphertext without satisfying the policy. Addressing this gap, we propose an enhanced MA-ABE scheme building on Michalevsky and Joye (ESORICS’18), offering proof of resistance against rogue-key attacks. Additionally, we have conducted simulations of both the original and the enhanced schemes to evaluate the defense mechanisms’ resource requirements under consistent parameters and analyzed the cost implications of rogue-key attacks as the number of attribute authorities increases in the scheme.

Misinformation has emerged as a major societal threat in the recent years in general; specifically in the context of the COVID-19 pandemic, it has wrecked havoc, for instance, by fueling vaccine hesitancy. Cost-effective, scalable solutions for combating misinformation are the need of the hour. This work explored how existing information obtained from social media and augmented with more curated fact checked data repositories can be harnessed to facilitate automated rebuttal of misinformation at scale. While the ideas herein can be generalized and reapplied in the broader context of misinformation mitigation using a multitude of information sources and catering to the spectrum of social media platforms, this work serves as a proof of concept, and as such, it is confined in its scope to only rebuttal of tweets, and in the specific context of misinformation regarding COVID-19. It leverages two publicly available datasets, viz. FaCov (fact-checked articles) Sharma et al., 2022 and misleading (social media Twitter) Sharma et al., 2024 data on COVID-19 vaccination.

In this work, we collect a moderate-sized representative corpus of tweets (over 200 000) pertaining to COVID-19 vaccination spanning for a period of seven months (September 2020–March 2021). Following a transfer learning approach, we utilize a pretrained transformer-based XLNet model to classify tweets as misleading or nonmisleading and manually validate the results with random subsets of samples. We leverage this to study and contrast the characteristics of tweets in the corpus that are misleading in nature against non-misleading ones. This exploratory analysis enables us to design features such as sentiments, hashtags, nouns, and pronouns which can, in turn, be exploited for classifying tweets as (non-)misleading using various machine learning (ML) models in an explainable manner. Specifically, several ML models are employed for prediction, with up to 90% accuracy, with the importance of each feature is explained using SHAP Explainable AI (XAI) tool. While the thrust of this work is principally exploratory in nature to obtain insight on the online discourse on COVID-19 vaccination, we conclude the article by outlining how these insights provide the foundations for a more actionable approach to mitigate misinformation. We have made the curated data as well as the accompanying code available so that the research community at large can reproduce, compare against, or build upon this work.

We demonstrate the Misinformation Concierge, a proof-of-concept that provides actionable intelligence on misinformation prevalent in social media. Specifically, it uses language processing and machine learning tools to identify subtopics of discourse and discerns non/misleading posts; presents statistical reports for policy-makers to understand the big picture of prevalent misinformation in a timely manner; and recommends rebuttal messages for specific pieces of misinformation, identified from within the corpus of data - providing means to intervene and counter misinformation promptly. The Misinformation Concierge proof-of-concept using a curated dataset is accessible at: https://demo-frontend-uy34.onrender.com/

A plethora of different blockchain platforms have emerged in recent years, but many of them operate in silos. As such, there is a need for reliable cross-chain communication to enable blockchain interoperability. Blockchain interoperability is challenging because transactions can typically not be reverted – as such, if one transaction is committed then the protocol must ensure that all related transactions are committed as well. Existing interoperability approaches, e.g., Cosmos and Polkadot, are limited in the sense that they only support interoperability between their own subchains, or require intrusive changes to existing blockchains. To overcome this limitation, we propose PIEChain, a general, Kafka-based cross-chain communication framework. We utilize PIEChain for a practical case study: a cross-chain auction in which users who hold tokens on multiple chains bid for a ticket sold on another chain. PIEChain is the first publicly available, practical implementation of a general framework for cross-chain communication.

We consider the design and analysis of quorum systems over erasure coded warm data (with low frequency of writes and accesses in general) to guarantee sequential consistency under a fail-stop model while supporting atomic read-modify-write operations by multiple clients. We propose a definition of asymmetric quorum systems that suit the framework of coded data by explicitly exploiting the structural properties of code and instantiate it over distinct families of coding strategies: maximum distance separable (MDS) codes and codes with locality, and we indicate a mechanism for synchronizing stale nodes using differential updates, which again exploits the code structures. The proposed quorum system's behavior is analyzed theoretically, exploring several aspects: viability of quorums under node unavailability; contention of resources between read and write operations; and quorum load. We complement these theoretical exploration with simulation based experiments to quantify the behavior of the proposed mechanism. The overall study demonstrates the feasibility and practicality of quorums over codes under practicable assumptions for achieving a stringent form of consistency, specifically, sequential consistency, while the stored data is being mutated by potentially multiple processes that might read and then modify the existing data. We achieve this in-place, without having to resort to store multiple versions of the data.

Summary Distinct transactions among different and unrelated users are combined together to create a single Bitcoin transaction (mixing transaction) to obfuscate the relationships among the actual participants (more specifically, the wallet addresses used for the transactions). We consider multi‐input multi‐output transactions with at least two inputs and three outputs as proxy, to analyze four characteristic periods of ∼50 days each, representing periods before the introduction of mixing, in its early days, during its growth, and after the volume of such multi‐input multi‐output transactions became more or less stabile. Structural properties and characteristics of the transaction and wallet address networks are computed and compared, through standard tools, but also via the introduction of two novel techniques that provide indicators of mixing‐like behaviors: (1) an entropy characterization to detect abnormally uniform inputs and/or outputs and (2) a connected component analysis of subgraphs formed by only multi‐input multi‐output transactions (showing cascades of such transactions). The contributions of this exploratory Bitcoin network analysis paper can thus be seen as two‐fold. At a macroscopic level, the growth and stabilization periods are shown to stand out with respect to most considered metrics, while at a microscopic level, chains of multi‐input multi‐output transactions, and transactions with outlier behavior in terms of input/output entropies are identified for further investigation.

This work explores how to enhance pseudonymous whistleblower submission systems, specifically by supporting protocol level unlinkability, while also making the system resilient against (distributed) denial of service attacks . To that end, we propose a blind signature based protocol which facilitates assignment of trust to anonymous posters in a manner which depends on the quality of prior posts, yet unlinkable to said posts or corresponding poster. This (multi-level) trust is leveraged to prioritize the posts, thus mitigating the effect that spam posts may have on the party reviewing the posts. We design and carry out simulations to explore the resilience of the whistleblower submission system against denial of service attacks while applying the proposed approach. Our experiments affirm that for a range of realistic scenarios the proposed approach provides reasonable mitigation.

The old mantra of decentralizing the Internet is coming again with fanfare, this time around the blockchain technology hype. We have already seen a technology supposed to change the nature of the Internet: peer-to-peer. The reality is that peer-to-peer naming systems failed, peer-to-peer social networks failed, and yes, peer-to-peer storage failed as well. In this paper, we will review the research on distributed systems in the last few years to identify the limits of open peer-to-peer networks. We will address issues like system complexity, security and frailty, instability and performance. We will show how many of the aforementioned problems also apply to the recent breed of permissionless blockchain networks. The applicability of such systems to mature industrial applications is undermined by the same properties that make them so interesting for a libertarian audience: namely, their openness, their pseudo-anonymity and their unregulated cryptocurrencies. As such, we argue that permissionless blockchain networks are unsuitable to be the substrate for a decentralized Internet. Yet, there is still hope for more decentralization, albeit in a form somewhat limited with respect to the libertarian view of decentralized Internet: in cooperation rather than in competition with the superpowerful datacenters that dominate the world today. This is derived from the recent surge in interest in byzantine fault tolerance and permissioned blockchains, which opens the door to a world where use of trusted third parties is not the only way to arbitrate an ensemble of entities. The ability of establish trust through permissioned blockchains enables to move the control from the datacenters to the edge, truly realizing the promises of edge-centric computing.

We propose a trusted third party free protocol for secure (in terms of content access, manipulation, and confidentiality) data storage and multi-user collaboration over an infrastructure of untrusted storage servers. It is achieved by the application of data dispersal, encryption as well as two-factor (knowledge and possession) based authentication and access control techniques so that unauthorized parties (attackers) or a small set of colluding servers cannot gain access to the stored data. The protocol design takes into account usability issues as opposed to the closest prior work Esiner and Datta (2016). We explore the security implications of the proposed model with event tree analysis and report on experiment results to demonstrate the practicality of the approach concerning computational overheads. Given that the protocol does not rely on any trusted third party, and most operations including actual collaboration do not require users to be online simultaneously, it is suitable not only for traditional multi-cloud setups but also for edge/fog computing environments.

A large volume of data is generated by traffic surveillance devices such as cameras and sensors integrated into an intelligent transportation system (ITS), a subfield of the Internet of Things (IoT). We argue that network coding can be applied to leverage on an emerging fog architecture that relies on edge resources, to achieve higher throughput , saving up network bandwidth , and provide resilience to link failures, while also achieving simple obfuscation against wire-tapping attacks by linearly combining the source packets . There are two broad linear network coding paradigms in the literature — deterministic and random network coding, each with their own strengths and limitations. With the aid of software-defined network (SDN), we rethink about the possibility of applying a hybrid approach to deal with networks at different scales. Under network conditions that reflect expected network properties of an ITS, our simulation results show that the proposed hybrid approach performs better than other alternates.

Given a graph, the notion of entropic centrality was introduced by Tutzauer to characterize vertices which are important in the sense that there is a high uncertainty about the destination of an atomic flow starting at them, assuming that at each hop, the flow is equally likely to continue to any unvisited vertex, or to be terminated there. We generalize this notion of entropic centrality to non-atomic flows, and furthermore show that the case of a non-atomic flow splitting with equal probability across different subsets of edges results in the same entropic centrality as that of the atomic flow. This gives a new and more generalized interpretation to the original entropic centrality notion. Finally, we demonstrate using network graphs derived from Bitcoin transactions that depending on the graph characteristics, the presented entropy based centrality metric can provide a unique perspective not captured by other existing centrality measures - particularly in identifying vertices with relatively low out-degrees which may nevertheless be connected to hub vertices, and thus can have high spread in the network.

We revisit a Renyi entropy based measure introduced originally for image clustering [1], and study its application to graph clustering. To effectuate Renyi entropy based graph clustering, we propose a simulated annealing algorithm. We explore our algorithm's efficacy and limitations with the Karate club graph [2], as well as some other real world network.

P2P-based social networking services are severely challenged by churn and the lack of reliable service providers, especially considering the high frequency of posts and profile updates of their users. Improved consistency and data availability shall facilitate better acceptance, which in turn will enhance privacy, an inherent benefit of this class of systems. We present Lilliput, a P2P storage primitive designed with the characteristics of Online Social Network workloads in mind. Lilliput separates the storage of static bulk data (videos and photo albums) from the essential social glue (e.g. basic profile information, frequent updates, notifications, and personal messages): it provides the latter through agile, lightweight replica groups. Extensive simulations show that Lilliput ensures high data availability (99.07% to 99.64%) and consistency, with a small bandwidth usage under realistic usage and load models.

In this work we focus on integrity and consistency of data accessed and manipulated by multiple collaborating users, and stored in an (untrusted) hosted service. This is a problem, aspects of which have been studied in isolation in hitherto distinct communities. Consistency is one of the cardinal problems of distributed computing. Integrity of hosted data has been studied over the last decade, and numerous techniques for proof of data possession and/or retrievability have been explored. The latter line of work however have often assumed static data, and techniques to handle dynamic or versioned data have only very recently been proposed. Yet, even the existing solutions that handle mutable content do so under the assumption that only a single data owner (using a single client) manipulate and verify said data. This is a serious limitation in terms of the variety of applications that can benefit from such mechanisms for proof of data possession. The novelty, and primary contribution of this work is in filling this gap. Specifically, we extend the existing ideas of proof of possession of dynamic data, in order to support multiple users who may collaborate in real time or asynchronously. In contrast (and addition) to the challenge of an untrusted storage server that existing techniques for proof of data possession need to overcome, we had to, simultaneously account for data integrity violations that may be incurred due to all the usual challenges of maintaining consistency of collaborative data (even if the storage server was trusted).

We leverage on authenticated data structures to guarantee correctness and completeness of query results over encrypted data . Our contribution is in bridging two independent lines of work (searchable encryption, and provable data possession) resulting in a general purpose technique, which does so without increasing the client storage overhead , while only a small token and a data structure is added to the server side (in comparison to a base searchable encryption without mechanisms for determining result integrity), where the data structure can simultaneously also be used for integrity checks on the stored data.

While many commercial systems as well as academic techniques for data outsourcing to and content confidentiality from untrusted data stores have been developed over the last decade, when it comes to multi-factor authentication based layered security, existing approaches typically rely on a logically centralized service. In this demo, we present DMZtore edge storage system that incorporates a decentralized multi-factor access control scheme [1] achieving layered security.

Over the life-cycle of a data object, it may be difficult to determine a priori how much redundancy to store it with. The desired degree of fault-tolerance may change over time, for instance, because the importance of the data changes, or the storage system environment changes. If the redundancy is achieved using replication, then changing the degree of fault-tolerance would mean adding (or removing) replicas - a reasonably straightforward operation. However, if erasure code is used instead (which is preferable, given the significantly lower storage overhead of erasure codes with respect to fully replicated systems), then, while shrinking redundancy can still be achieved similarly, expanding redundancy becomes non-trivial. A naive approach will require re-coding, which is both network resource and computation heavy. In this paper, we explore the possibility of using network coding techniques, to both distribute computational load, as well as reduce network usage, and in the process, speed-up the process of creating additional redundancy. The contributions of this paper are defining the problem and analyzing the theoretical limits by leveraging on and extending the existing literature on regenerating codes to realize erasure coded redundancy elasticity, propose a framework to realize code instances that are amenable to network coding based elastic expansion of redundancy, and integrate and benchmark one such code instance (which happens to be optimal with respect to the aforementioned established theoretical limit) with OpenStack Swift to demonstrate the practicality and advantages of the proposed approach.

Association rule mining and frequent itemset mining are two popular and widely studied data analysis techniques for a range of applications. In this paper, we focus on privacy-preserving mining on vertically partitioned databases. In such a scenario, data owners wish to learn the association rules or frequent itemsets from a collective data set and disclose as little information about their (sensitive) raw data as possible to other data owners and third parties. To ensure data privacy, we design an efficient homomorphic encryption scheme and a secure comparison scheme. We then propose a cloud-aided frequent itemset mining solution, which is used to build an association rule mining solution. Our solutions are designed for outsourced databases that allow multiple data owners to efficiently share their data securely without compromising on data privacy. Our solutions leak less information about the raw data than most existing solutions. In comparison to the only known solution achieving a similar privacy level as our proposed solutions, the performance of our proposed solutions is three to five orders of magnitude higher. Based on our experiment findings using different parameters and data sets, we demonstrate that the run time in each of our solutions is only one order higher than that in the best non-privacy-preserving data mining algorithms. Since both data and computing work are outsourced to the cloud servers, the resource consumption at the data owner end is very low.

In this work, we study the problem of storing reliably an archive of versioned data. Specifically, we focus on systems where the differences (deltas) between subsequent versions rather than the whole objects are stored - a typical model for storing versioned data. For reliability, we propose erasure encoding techniques that exploit the sparsity of information in the deltas while storing them reliably in a distributed back-end storage system, resulting in improved I/O read performance to retrieve the whole versioned archive. Along with the basic techniques, we propose a few optimization heuristics, and evaluate the techniques' efficacy analytically and with numerical simulations.

In a decentralized storage system, agents replicate each other’s data to increase availability. Compared to organizationally centralized solutions, such as cloud storage, a decentralized storage system requires less trust in the provider and may result in smaller monetary costs. Our system is based on reciprocal storage contracts that allow the agents to adopt to changes in their replication partners’ availability (by dropping inefficient contracts and forming new contracts with other partners). The data availability provided by the system is a function of the participating agents’ availability. However, a straightforward system in which agents’ matching is decentralized uses the given agent availability inefficiently. As agents are autonomous, the highly available agents form cliques replicating data between each other, which makes the system too hostile for the weakly available newcomers. In contrast, a centralized, equitable matching is not incentive compatible: it does not reward users for keeping their software running. We solve this dilemma by a mixed solution: an “adoption” mechanism in which highly available agents donate some replication space, which in turn is used to help the worst-off agents. We show that the adoption motivates agents to increase their availability (is incentive-compatible), but also that it is sufficient for acceptable data availability for weakly-available agents.

In this paper, we focus on the problem of data privacy on the cloud, particularly on access controls over stream data. The nature of stream data and the complexity of sharing data make access control a more challenging issue than in traditional archival databases. We present Streamforce -- a system allowing data owners to securely outsource their data to an untrusted (curious-but-honest) cloud. The owner specifies fine-grained policies which are enforced by the cloud. The latter performs most of the heavy computations, while learning nothing about the data content. To this end, we employ a number of encryption schemes, including deterministic encryption, proxy-based attribute based encryption and sliding-window encryption. In Streamforce, access control policies are modeled as secure continuous queries, which entails minimal changes to existing stream processing engines, and allows for easy expression of a wide-range of policies. In particular, Streamforce comes with a number of secure query operators including Map, Filter, Join and Aggregate. Finally, we implement Streamforce over an open-source stream processing engine (Esper) and evaluate its performance on a cloud platform. The results demonstrate practical performance for many real-world applications, and although the security overhead is visible, Streamforce is highly scalable.

The need to store humongous volumes of data has regurgitated the study of erasure codes, so that reliable fault-tolerant distributed (for scaling out) data stores can be built while keeping the overheads low. In the context of storage codes, one of the most vigorously researched aspect in the last half a decade or so is their repairability - which looks into mechanisms to rebuild the data at a new storage node, to substitute the loss of information when an existing node fails. Desirable (sometimes mutually conflicting or reinforcing) repairability properties include reduction in the volume of I/O operations, minimize bandwidth usage, fast repairs, reduction in the number of live nodes to be contacted to carry out a repair (repair locality), repairing multiple failures simultaneously, etc.

In many large‐scale distributed systems and on the Web, agents need to interact with other unknown agents to carry out some tasks or transactions. The ability to reason about and assess the potential risks in carrying out such transactions is essential for providing a safe and reliable interaction environment. A traditional approach to reason about the risk of a transaction is to determine if the involved agent is trustworthy on the basis of its behavior history. As a departure from such traditional trust models, we propose a generic, trust framework based on machine learning where an agent uses its own previous transactions (with other agents) to build a personal knowledge base. This is used to assess the trustworthiness of a transaction on the basis of the associated features, particularly using the features that help discern successful transactions from unsuccessful ones. These features are handled by applying appropriate machine learning algorithms to extract the relationships between the potential transaction and the previous ones. Experiments based on real data sets show that our approach is more accurate than other trust mechanisms, especially when the information about past behavior of the specific agent is rare, incomplete, or inaccurate.

It is often necessary to compose a team consisting of experts with diverse competencies to accomplish complex tasks. However, for its proper functioning, it is also preferable that a team be socially cohesive. A team recommendation system, which facilitates the search for potential team members, can be of great help both for (a) individuals who need to seek out collaborators and for (b) managers who need to build a team for some specific tasks. Such a decision support system that readily helps summarize multiple metrics indicating a team (and its members) quality, and possibly rank the teams in a personalized manner according to the end users' preferences, thus serves as a tool to cope with what would otherwise be an information avalanche. In this work, we present Social Web Application for Team Recommendation, a general‐purpose framework to compose various information retrieval and social graph mining and visualization subsystems together to build a composite team recommendation system, and instantiate it for a case study of academic teams.

The Kurdish language is an Indo-European language spoken in Kurdistan, a large geographical region in the Middle East. Despite having a large number of speakers, Kurdish is among the less-resourced languages and has not seen much attention from the IR and NLP research communities. This article reports on the outcomes of a project aimed at providing essential resources for processing Kurdish texts. A principal output of this project is Pewan, the first standard Test Collection to evaluate Kurdish Information Retrieval systems. The other language resources that we have built include a lightweight stemmer and a list of stopwords. Our second principal contribution is using these newly-built resources to conduct a thorough experimental study on Kurdish documents. Our experimental results show that normalization, and to a lesser extent, stemming, can greatly improve the performance of Kurdish IR systems.

In the past few years erasure codes have been increasingly embraced by distributed storage systems as an alternative for replication, since they provide high fault-tolerance for low overheads. Erasure codes, however, have few shortcomings that need to be addressed to make them a complete solution for networked storage systems. Lack of support for efficient data repair and data update are the two most notable shortcomings. We recently proposed to use a 2-dimensional product code-Reed-Solomon coding per object and simple XORing across objects- and showed that at a reasonable storage overhead, it can greatly reduce the repair cost. In this paper we propose an efficient approach to handle data updates in cross-object erasure-coded storage systems. Our proposed solution has been implemented and experimentally evaluated. Our results show that compared to the naive approach (re-encoding the data), our proposed scheme can considerably decrease the update cost, especially for when the number of updated blocks is small.

Erasure codes are an integral part of many distributed storage systems aimed at Big Data, since they provide high fault-tolerance for low overheads. However, traditional erasure codes are inefficient on replenishing lost data (vital for long term resilience) and on reading stored data in degraded environments (when nodes might be unavailable). Consequently, novel codes optimized to cope with distributed storage system nuances are vigorously being researched. In this paper, we take an engineering alternative, exploring the use of simple and mature techniques - juxtaposing a standard erasure code with RAID-4 like parity to realize cross object redundancy (CORE), and integrate it with HDFS. We benchmark the implementation in a proprietary cluster and in EC2. Our experiments show that for an extra 20% storage overhead (compared to traditional erasure codes) CORE yields up to 58% saving in bandwidth and is up to 76% faster while recovering a single failed node. The gains are respectively 16% and 64% for double node failures.

To achieve reliability in distributed storage systems, data has usually been replicated across different nodes. However the increasing volume of data to be stored has motivated the introduction of erasure codes, a storage efficient alternative to replication, particularly suited for archival in data centers, where old datasets (rarely accessed) can be erasure encoded, while replicas are maintained only for the latest data. Many recent works consider the design of new storage-centric erasure codes for improved repairability. In contrast, this paper addresses the migration from replication to encoding: traditionally erasure coding is an atomic operation in that a single node with the whole object encodes and uploads all the encoded pieces. Although large datasets can be concurrently archived by distributing individual object encodings among different nodes, the network and computing capacity of individual nodes constrain the archival process due to such atomicity. We propose a new pipelined coding strategy that distributes the network and computing load of single-object encodings among different nodes, which also speeds up multiple object archival. We further present RapidRAID codes, an explicit family of pipelined erasure codes which provides fast archival without compromising either data reliability or storage overheads. Finally, we provide a real implementation of RapidRAID codes and benchmark its performance using both a cluster of 50 nodes and a set of Amazon EC2 instances. Experiments show that RapidRAID codes reduce a single object's coding time by up to 90%, while when multiple objects are encoded concurrently, the reduction is up to 20%.

The semantic knowledge of Wikipedia has proved to be useful for many tasks, for example, named entity disambiguation. Among these applications, the task of identifying the word sense based on Wikipedia is a crucial component because the output of this component is often used in subsequent tasks. In this article, we present a two‐stage framework (called TSDW) for word sense disambiguation using knowledge latent in Wikipedia. The disambiguation of a given phrase is applied through a two‐stage disambiguation process: (a) The first‐stage disambiguation explores the contextual semantic information, where the noisy information is pruned for better effectiveness and efficiency; and (b) the second‐stage disambiguation explores the disambiguated phrases of high confidence from the first stage to achieve better redisambiguation decisions for the phrases that are difficult to disambiguate in the first stage. Moreover, existing studies have addressed the disambiguation problem for English text only. Considering the popular usage of Wikipedia in different languages, we study the performance of TSDW and the existing state‐of‐the‐art approaches over both English and Traditional Chinese articles. The experimental results show that TSDW generalizes well to different semantic relatedness measures and text in different languages. More important, TSDW significantly outperforms the state‐of‐the‐art approaches with both better effectiveness and efficiency.

Modeling trust in complex dynamic environments is an important yet challenging issue since an intelligent agent may strategically change its behavior to maximize its profits. In thispaper, we propose a context aware trust model to predict dynamic trust by using a Hidden Markov Model (HMM) to model an agent's interactions. Although HMMs have already been applied in the past to model an agent's dynamic behavior to greatly improve the traditional static probabilistic trust approaches, most HMM based trust models only focus on outcomes of the past interactions without considering interaction context, which we believe, reflects immensely on the dynamic behavior or intent of an agent. Interaction contextual information is comprehensively studied and integrated into the model to more precisely approximate an agent's dynamic behavior. Evaluation using real auction data and synthetic data demonstrates the efficacy of our approach in comparison with previous state-of-the-art trust mechanisms.

Modeling and understanding social network structure has interested researchers from many backgrounds including social science, computer science, theoretical physics and graph theory. Notable models include [1] and [2] achieving graphs with power-law degree distribution using preferential attachment and small-world characteristics using randomized rewiring of a regular ring lattice respectively. In contrast to a body of follow-up research which refine upon these seminal works to better capture the graph structure and characteristics (such as improving clustering coefficient by considering social triads along with preferential attachment [3]), this work aims additionally to model the geographic spread in social networks. With increased mobility in our society as well as enhanced communication opportunities social networks are increasingly spread all over the globe. Synthetic graphs imitating real-world social network characteristics are often used for driving simulations for planning and decision support. Incorporating geographic spread can facilitate better infrastructure provisioning in distributed systems supporting social and collaborative applications or model information of malware diffusion, word-of-mouth marketing, etc. The proposed model is tunable and modular. The model can be tuned to produce graphs with different geographic spread. The model is modular in the sense that existing geographic spread agnostic social network models can be plugged into our model to achieve desirable geographic spread in addition to other characteristics (such as degree distribution, clustering coefficient) that such a model would natively support.

Event detection from tweets is an important task to understand the current events/topics attracting a large number of common users. However, the unique characteristics of tweets (e.g. short and noisy content, diverse and fast changing topics, and large data volume) make event detection a challenging task. Most existing techniques proposed for well written documents (e.g. news articles) cannot be directly adopted. In this paper, we propose a segment-based event detection system for tweets, called Twevent. Twevent first detects bursty tweet segments as event segments and then clusters the event segments into events considering both their frequency distribution and content similarity. More specifically, each tweet is split into non-overlapping segments (i.e. phrases possibly refer to named entities or semantically meaningful information units). The bursty segments are identified within a fixed time window based on their frequency patterns, and each bursty segment is described by the set of tweets containing the segment published within that time window. The similarity between a pair of bursty segments is computed using their associated tweets. After clustering bursty segments into candidate events, Wikipedia is exploited to identify the realistic events and to derive the most newsworthy segments to describe the identified events. We evaluate Twevent and compare it with the state-of-the-art method using 4.3 million tweets published by Singapore-based users in June 2010. In our experiments, Twevent outperforms the state-of-the-art method by a large margin in terms of both precision and recall. More importantly, the events detected by Twevent can be easily interpreted with little background knowledge because of the newsworthy segments. We also show that Twevent is efficient and scalable, leading to a desirable solution for event detection from tweets.

Team recommendation aids decision support, by not only identifying individuals who are experts for various aspects of a complex task, but also determining various properties of the team as a group. Several aspects such as cohesion and repetition of teams have been identified as important indicators, besides individuals' expertise, in determining how well a team performs. While such information often do not exist explicitly, digital footprint of users' activities can be harnessed to retrieve the same from diverse sources. In this work, we lay out a proof-of-concept on how to do so in the case of scientific knowledge workers, as well as demonstrate some necessary visualization, manipulation and communication tools to determine and manage multi-disciplinary teams. While the focus of our presentation is the specific application 'SWAT' for team recommendation, it also serves as a vehicle demonstrating how, in general, apparently disparate data sources can be harnessed to provide decision support guided by suitable analytics.

Many private and/or public organizations have been reported to create and monitor targeted Twitter streams to collect and understand users' opinions about the organizations. Targeted Twitter stream is usually constructed by filtering tweets with user-defined selection criteria e.g. tweets published by users from a selected region, or tweets that match one or more predefined keywords. Targeted Twitter stream is then monitored to collect and understand users' opinions about the organizations. There is an emerging need for early crisis detection and response with such target stream. Such applications require a good named entity recognition (NER) system for Twitter, which is able to automatically discover emerging named entities that is potentially linked to the crisis. In this paper, we present a novel 2-step unsupervised NER system for targeted Twitter stream, called TwiNER. In the first step, it leverages on the global context obtained from Wikipedia and Web N-Gram corpus to partition tweets into valid segments (phrases) using a dynamic programming algorithm. Each such tweet segment is a candidate named entity. It is observed that the named entities in the targeted stream usually exhibit a gregarious property, due to the way the targeted stream is constructed. In the second step, TwiNER constructs a random walk model to exploit the gregarious property in the local context derived from the Twitter stream. The highly-ranked segments have a higher chance of being true named entities. We evaluated TwiNER on two sets of real-life tweets simulating two targeted streams. Evaluated using labeled ground truth, TwiNER achieves comparable performance as with conventional approaches in both streams. Various settings of TwiNER have also been examined to verify our global context + local context combo idea.

Reputation systems deployed in popular online auction sites simply aggregate feedback about a seller's past transactions. By studying a real auction site dataset, we infer that a non-negligible fraction of unsatisfactory transactions involve sellers with high reputation. Such a phenomenon can be interpreted by motivation theory from behaviorial science: A seller with high reputation has more business opportunities. Bad feedback for latest transactions do not immediately affect his reputation adequately to hurt business, hence he may not be as prudent as before. In this work, we propose the concept of imprudence to study and detect the inappropriate behavior of a 'reliable' seller (i.e., the one with high reputation computed using conventional approaches). Specifically, we first identify and verify the features that influence a seller's imprudence behavior. We then design a novel intelligent buying agent to combine these factors using logistic regression for predicting and studying the probability of imprudence of a target seller. We validate our approach using real datasets driven experiments.

Finding relevant and reliable information on the web is a non-trivial task. While internet search engines do find correct web pages with respect to a set of keywords, they often cannot ensure the relevance or reliability of their content. An emerging trend is to harness internet users in the spirit of Web 2.0, to discern and personalize relevant and reliable information. Users collaboratively search or browse for information, either directly by communicating or indirectly by adding meta information (e.g., tags) to web pages. While gaining much popularity, such approaches are bound to specific service providers, or the Web 2.0 sites providing the necessary features, and the knowledge so generated is also confined to, and subject to the whims and censorship of such providers. To overcome these limitations we introduce COBS, a browser-centric knowledge repository which enjoys the inherent openness (similar to Wikipedia) while aiming to provide end-users the freedom of personalization and privacy by adopting an eventually hybrid/p2p back-end. In this paper we first present the COBS front-end, a browser add-on that enables users to tag, rate or comment arbitrary web pages and to socialize with others in both a synchronous and asynchronous manner. We then discuss how a decentralized back-end can be realized. While Distributed Hash Tables (DHTs) are the most natural choice, and despite a decade of research on DHT designs, we encounter several, some small, while others more fundamental shortcomings that need to be surmounted in order to realize an efficient, scalable and reliable decentralized back-end for COBS. To that end, we outline various design alternatives and discuss qualitatively (and quantitatively, when possible) their (dis-)advantages. We believe that the objectives of COBS are ambitious, posing significant challenges for distributed systems, middleware and distributed data-analytics research, even while building on the existing momentum. Based on experiences from our ongoing work on COBS, we outline these systems research issues in this position paper.

Erasure codes provide a storage efficient alternative to replication based redundancy in (networked) storage systems. They however entail high communication overhead for maintenance, when some of the encoded fragments are lost and need to be replenished. Such overheads arise from the fundamental need to recreate (or keep separately) first a copy of the whole object before any individual encoded fragment can be generated and replenished. There has recently been intense interest to explore alternatives, most prominent ones being regenerating codes (RGC) and hierarchical codes (HC). We propose as an alternative a new family of codes to improve the maintenance process, called self-repairing codes (SRC), with the following salient features: (a) encoded fragments can be repaired directly from other subsets of encoded fragments by downloading less data than the size of the complete object, ensuring that (b) a fragment is repaired from a fixed number of encoded fragments, the number depending only on how many encoded blocks are missing and independent of which specific blocks are missing. These properties allow for not only low communication overhead to recreate a missing fragment, but also independent reconstruction of different missing fragments in parallel, possibly in different parts of the network. The fundamental difference between SRCs and HCs is that different encoded fragments in HCs do not have symmetric roles (equal importance). Consequently the number of fragments required to replenish a specific fragment in HCs depends on which specific fragments are missing, and not solely on how many. Likewise, object reconstruction may need different number of fragments depending on which fragments are missing. RGCs apply network coding over (n, k) erasure codes, and provide network information flow based limits on the minimal maintenance overheads. RGCs need to communicate with at least k other nodes to recreate any fragment, and the minimal overhead is achieved if only one fragment is missing, and information is downloaded from all the other n-1 nodes. We analyze the static resilience of SRCs with respect to erasure codes, and observe that SRCs incur marginally larger storage overhead in order to achieve the aforementioned properties. The salient SRC properties naturally translate to low communication overheads for reconstruction of lost fragments, and allow reconstruction with lower latency by facilitating repairs in parallel. These desirable properties make SRC a practical candidate for networked distributed storage systems.

Self-Repairing Codes (SRC) are codes designed to suit the need of coding for distributed networked storage: they not only allow stored data to be recovered even in the presence of node failures, they also provide a repair mechanism where as little as two live nodes can be contacted to regenerate the data of a failed node. In this paper, we propose a new instance of self-repairing codes, based on constructions of spreads coming from projective geometry. We study some of their properties to demonstrate the suitability of these codes for distributed networked storage.

Recent years have witnessed a slew of coding techniques custom designed for networked storage systems. Network coding inspired regenerating codes are the most prolifically studied among these new age storage centric codes. A lot of effort has been invested in understanding the fundamental achievable trade-offs of storage and bandwidth usage to maintain redundancy in presence of different models of failures, showcasing the efficacy of regenerating codes with respect to traditional erasure coding techniques. For practical usability in open and adversarial environments, as is typical in peer-to-peer systems, we need however not only resilience against erasures, but also from (adversarial) errors. In this paper, we study the resilience of generalized regenerating codes (supporting multi-repairs, using collaboration among newcomers) in the presence of two classes of Byzantine nodes, relatively benign selfish (non-cooperating) nodes, as well as under more active, malicious polluting nodes. We give upper bounds on the resilience capacity of regenerating codes, and show that the advantages of collaborative repair can turn to be detrimental in the presence of Byzantine nodes. We further exhibit that system mechanisms can be combined with regenerating codes to mitigate the effect of rogue nodes.

Friend-to-friend networks, i.e. peer-to-peer networks where data are exchanged and stored solely through nodes owned by trusted users, can guarantee dependability, privacy and uncensorability by exploiting social trust. However, the limitation of storing data only on friends can come to the detriment of data availability: if no friends are online, then data stored in the system will not be accessible. In this work, we explore the tradeoffs between redundancy (i.e., how many copies of data are stored on friends), data placement (the choice of which friend nodes to store data on) and data availability (the probability of finding data online). We show that the problem of obtaining maximal availability while minimizing redundancy is NP-complete; in addition, we perform an exploratory study on data placement strategies, and we investigate their performance in terms of redundancy needed and availability obtained. By performing a trace-based evaluation, we show that nodes with as few as 10 friends can already obtain good availability levels.

The common tags given by multiple users to a particular document are often semantically relevant to the document and each tag represents a specific topic. In this paper, we attempt to emulate human tagging behavior to recommend tags by considering the concepts contained in documents. Specifically, we represent each document using a few most relevant concepts contained in the document, where the concept space is derived from Wikipedia. Tags are then recommended based on the tag concept model derived from the annotated documents of each tag. Evaluated on a Delicious dataset of more than 53K documents, the proposed technique achieved comparable tag recommendation accuracy as the state-of-the-art, while yielding an order of magnitude speed-up.

We demonstrate SSNetViz that is developed for integrating, visualizing and querying heterogeneous semantic social networks obtained from multiple information sources. A semantic social network refers to a social network graph with multi-typed nodes and links. We demonstrate various innovative features of SSNetViz with social networks from three information sources covering a similar set of entities and relationships in terrorism domain.

Improving web search solely based on algorithmic refinements has reached a plateau. The emerging generation of searching techniques tries to harness the ``wisdom of crowds'', using inputs from users in the spirit of Web 2.0. In this paper, we introduce a framework facilitating friends augmented search techniques (FAST). To that end, we present a browser add-on as front end for collaborative browsing and searching, supporting synchronous and asynchronous collaboration between users. We then describe the back end, a distributed key-value store for efficient information retrieval in the presence of an evolving knowledge base. The mechanisms we explore in supporting efficient query processing for FAST are applicable for many other recent Web 2.0 applications that rely on similar key-value stores. The specific collaborative search tool we present is expected to be an useful utility in its own right and spur further research on friends augmented search techniques, while the data-management techniques we developed are of general interest and applicability.

In this (invited) paper, we present a work in progress social library and reference management system called SoJa (Social Jabref), which is realized on top of a decentralized (peer-to-peer) social information system. The contribution of the work is multi-fold. It provides a platform to collaborate a

Cloud computing has emerged as a popular paradigm that offers computing resources (e.g. CPU, storage, bandwidth, software) as scalable and on-demand services over the Internet. As more players enter this emerging market, a heterogeneous cloud computing market is expected to evolve, where individual

In peer-to-peer storage systems, peers replicate each others' data in order to increase availability. If the matching is done centrally, the algorithm can optimize data availability in an equitable manner for all participants. However, if matching is decentralized, the peers' selfishness can greatly alter the results, leading to performance inequities that can render the system unreliable and thus ultimately unusable. We analyze the problem using both theoretical approaches (complexity analysis for the centralized system, game theory for the decentralized one) and simulation. We prove that the problem of optimizing availability in a centralized system is NP-hard. In decentralized settings, we show that the rational behavior of selfish peers will be to replicate only with similarly-available peers. Compared to the socially-optimal solution, highly available peers have their data availability increased at the expense of decreased data availability for less available peers. The price of anarchy is high: unbounded in one model, and linear with the number of time slots in the second model. We also propose centralized and decentralized heuristics that, according to our experiments, converge fast in the average case. The high price of anarchy means that a completely decentralized system could be too hostile for peers with low availability, who could never achieve satisfying replication parameters. Moreover, we experimentally show that even explicit consideration and exploitation of diurnal patterns of peer availability has a small effect on the data availability-except when the system has truly global scope. Yet a fully centralized system is infeasible, not only because of problems in information gathering, but also the complexity of optimizing availability. The solution to this dilemma is to create system-wide cooperation rules that allow a decentralized algorithm, but also limit the selfishness of the participants.

Current collaborative software usually have no or limited support for ad-hoc collaboration. SharedMind supports synchronous collaboration, i.e. real-time collaboration, and asynchronous collaboration, i.e. the merging of local instances of a document modified by different users after dis- and reconnects to a group of collaborators. SharedMind is completely decentralized and supports ad-hoc collaboration for interconnected (sub)groups. It demonstrates the confluence of social media and tools for computer supported collaborative works.

User-generated content in the spirit of Web 2.0 is a promising means to improve the search for relevant information on the web, particularly multimedia content. The idea is that user col-laboratively search or browse for information, either directly by communicating or indirectly by adding meta information (e.g., tags) to web pages. However, current solutions are bound to specific web sites providing such features. To overcome this limitation we introduce COBS, making Web 2.0 features available also for the 'old' web. In this demo we present the front-end, a browser add-on that enables users to tag, rate or comment arbitrary web pages and to communicate with others in both a synchronous and asynchronous manner.

Recent years have seen advances in building large Internet-scale index structures, generally known as structured overlays . Early structured overlays realized distributed hash tables (DHTs) which are ill suited for anything but exact queries. The need to support range queries necessitates systems that can handle uneven load distributions. However such systems suffer from practical problems—including poor latency, disproportionate bandwidth usage at participating peers, or unrealistic assumptions on peers' homogeneity, in terms of available storage or bandwidth resources. In this article we consider a system that is not only able to support uneven load distributions but also to operate in heterogeneous environments, where each peer can autonomously decide how much of its resources to contribute to the system. We provide the theoretical foundations of realizing such a network and present a newly proposed system Oscar based on these principles. Oscar can construct efficient overlays given arbitrary load distributions by employing a novel scalable network sampling technique. The simulations of our system validate the theory and evaluate Oscar's performance under typical challenges, encountered in real-life large-scale networked systems, including participant heterogeneity, faults, and skewed and dynamic load-distributions. Thus the Oscar distributed index fills in an important gap in the family of structured overlays, bringing into life a practical Internet-scale index, which can play a crucial role in enabling data-oriented applications distributed over wide-area networks.

SSnetViz is an ongoing research to design and implement a visualization engine for heterogeneous semantic social networks. A semantic social network is a multi-modal network that contains nodes representing different types of people or object entities, and edges representing relationships among them. When multiple heterogeneous semantic social networks are to be visualized together, SSnetViz provides a suite of functions to store heterogeneous semantic social networks, to integrate them for searching and analysis. We will illustrate these functions using social networks related to terrorism research, one crafted by domain experts and another from Wikipedia.

We study a new application of threshold-based secret sharing in a distributed online social network (DOSN), where users need a means to back up and recover their private keys in a network of untrusted servers. Using a simple threshold-based secret sharing in such an environment is insufficiently secured since delegates keeping the secret shares may collude to steal the user's private keys. To mitigate this problem, we propose using different techniques to improve the system security: by selecting only the most reliable delegates for keeping these shares and further by encrypting the shares with passwords. We develop a mechanism to select the most reliable delegates based on an effective trust measure. Specifically, relationships among the secret owner, delegate candidates and their related friends are used to estimate the trustworthiness of a delegate. This trust measure minimizes the likelihood of the secret being stolen by an adversary and is shown to be effective against various collusive attacks. Extensive simulations show that the proposed trust-based delegate selection performs very well in highly vulnerable environments where the adversary controls many nodes with different distributions and even with spreading of infections in the network. In fact, the number of keys lost is very low under extremely pessimistic assumptions of the adversary model.

Using peer-to-peer overlays to notify users whenever a new update occurs is a promising approach to support Web based publish subscribe systems like really simple syndication (RSS). Such a peer-to-peer approach can scale well by reducing load at the source and also guarantee timeliness of notifications. Several such overlay based approaches have been proposed in recent years. However, malicious peers may pretend to relay but actually not, and thus deny service, or even propagate counterfeit updates - thus rendering a peer-to-peer mechanism not only useless, but even harmful (e.g., by false updates). We propose overlay independent randomized strategies to mitigate these ill-effects of malicious peers at a marginal overhead, thus enjoying the benefits of peer-to-peer dissemination, along with the assurance of content integrity in RSS like Web-based publish-subscribe applications without altering currently deployed server infrastructure.

Current implementations of real-time collaborative applications rely on a dedicated infrastructure to carry out all synchronizing and communication functions, and require all end nodes to communicate directly with and through the central server. In this paper, we investigate an architecture, in which the most resource intensive functionality of continuous communication among collaborators to disseminate changes is decentralized, utilizing the end users as relays. We observe that communication characteristics of real-time collaboration makes use of existing multicast mechanisms unsuitable. As collaborative editing sessions are typically long, we are able to gather and then use additional parameters of nodes (their instabilities and frequency of sending updates) and communication links (latencies and average costs). We identify several criteria to determine the quality of a multicast tree: cost, latency and instability. We analyze the complexity of these problems and propose algorithms to optimize the communication topology. We also consider the multiobjective problem in which we search for a tree that results in a good trade-off between these measures. Validation of algorithms on numerous graphs shows that it is important to consider the multiobjective problem, as optimal solutions for one performance measure can be far from optimal values of the others.

Trust plays important roles in diverse decentralized environments, including our society at large. Computational trust models help to, for instance, guide users' judgements in online auction sites about other users; or determine quality of contributions in web 2.0 sites. Most of the existing trust models, however, require historical information about past behavior of a specific agent being evaluated - information that is not always available. In contrast, in real life interactions among users, in order to make the first guess about the trustworthiness of a stranger, we commonly use our "instinct" - essentially stereotypes developed from our past interactions with "similar" people. We propose StereoTrust, a computational trust model inspired by real life stereotypes. A user forms stereotypes using her previous transactions with other agents. A stereotype contains certain features of agents and an expected outcome of the transaction. These features can be taken from agents' profile information, or agents' observed behavior in the system. When facing a stranger, the stereotypes matching stranger's profile are aggregated to derive his expected trust. Additionally, when some information about stranger's previous transactions is available, StereoTrust uses it to refine the stereotype matching. According to our experiments, StereoTrust compares favorably with existing trust models that use different kind of information and more complete historical information. Moreover, because evaluation is done according to user's personal stereotypes, the system is completely distributed and the result obtained is personalized. StereoTrust can be used as a complimentary mechanism to provide the initial trust value for a stranger, especially when there is no trusted, common third parties.

When multiple users with diverse backgrounds and beliefs edit Wikipedia together, disputes often arise due to disagreements among the users. In this paper, we introduce a novel visualization tool known as WikiNetViz to visualize and analyze disputes among users in a dispute-induced social network. WikiNetViz is designed to quantify the degree of dispute between a pair of users using the article history. Each user (and article) is also assigned a controversy score by our proposed Controversy Rank model so as to measure the degree of controversy of a user (and an article) by the amount of disputes between the user (article) and other users in articles of varying degrees of controversy. On the constructed social network, WikiNetViz can perform clustering so as to visualize the dynamics of disputes at the user group level. It also provides an article viewer for examining an article revision so as to determine the article content modified by different users.

Query-load (forwarding and answering) balancing in structured overlays is one of the most critical and least studied problems. It has been assumed that caching heuristics can take care of it. We expose that caching, while necessary, is not in itself sufficient. We then provide simple and effective load-aware variants of the standard greedy routing used in overlays, exploiting routing redundancy originally needed for fault-tolerance, to achieve very good query load-balancing.

We propose a new genre of overlay network for disseminating information from popular but resource constrained sources. We call this communication primitive as latency gradated overlay, where information consumers self- organize themselves according to their individual resource constraints and the latency they are willing to tolerate in receiving the information from the source. Such a communication primitive finds immediate use in applications like RSS feeds aggregation. We propose heuristic algorithms to construct LagOver based on preferably some partial knowledge of the network at users (no knowledge slows the construction process) but no global coordination. The algorithms are evaluated based on simulations and show good characteristics including convergence, satisfying peers' latency and bandwidth constraints even in presence of moderately high membership dynamics. There are two points worth noting. First, optimizing jointly for latency and capacity (i.e., placing nodes that have free capacity close to the source) as long as latency constraint of other nodes are not violated performs better than optimizing for latency only. The joint optimization strategy has faster convergence of the LagOver network, and can deal with adversarial workloads that optimization of only latency can not deal with. Secondly, somewhat counter-intuitively, in order to do the aforementioned joint optimization, it is sufficient to find random nodes based on only the latency constraint, since even if the capacity of individual nodes is saturated it does not matter since the LagOver network can potentially be reconfigured.

Quite a few data-oriented overlay networks have been designed in recent years. These designs often (implicitly) assume various homogeneity which seriously limit their usability in real world. In this paper we present some performance results of the Oscar overlay, which simultaneously deals with heterogeneity as observed in the Internet (capacity of computers, bandwidth) as well as non-uniformity observed in data-oriented applications.

Content storage in a distributed collaborative environment uses redundancy for better resilience and thus provides good availability and durability. In a peer-to-peer environment, where peers continuously leave and rejoin the network, various lazy strategies can be employed to maintain a minimal redundancy of stored content in the system. Existing static resilience analyses fail to capture in detail the system's behavior over time, particularly the probability mass function of the actual available redundancy, since it ignores the crucial interplay between churn and maintenance operations, and looks only at the average system property. We perform a Markovian time-evolution analysis of the system specified by probability mass function of each possible system state, and establish that given a fixed rate of churn and a specific maintenance strategy, the system operates in a corresponding steady-state (dynamic equilibrium). Understanding the behavior of the system under such a dynamic equilibrium is a fundamental ingredient to precisely evaluate analytically the system's performance and availability as well as to determine the required operational maintenance cost. We also propose a new randomized variant of a lazy-maintenance scheme which has significant performance benefits in comparison to the existing deterministic procrastination based maintenance. We demonstrate the use of our analysis methodology in comparing performance of maintenance schemes using the examples of the new maintenance scheme we propose and the erstwhile best known existing lazy maintenance scheme. The comparative study shows that our randomized lazy maintenance strategy has substantially better resilience at same maintenance cost

We do a case study of two different analysis techniques for studying the stochastic behavior of a randomized system/algorithms: (i) The first approach can be broadly termed as a mean value analysis (MVA), where the evolution of the mean state is studied assuming that the system always actually resides in the mean state; (ii) The second approach looks at the probability distribution function of the system states at any time instance, thus studying the evolution of the (probability mass) distribution function (EoDF).

Among the open problems in P2P systems, support for nontrivial search predicates, standardized query languages, distributed query processing, query load balancing, and quality of query results have been identified as some of the most relevant issues. This paper describes how range queries as an important nontrivial search predicate can be supported in a structured overlay network that provides O(log n) search complexity on top of a trie abstraction. We provide analytical results that show that the proposed approach is efficient, supports arbitrary granularity of ranges, and demonstrate that its algorithmic complexity in terms of messages is independent of the size of the queried ranges and only depends on the size of the result set. In contrast to other systems which provide evaluation results only through simulations, we validate the theoretical analysis of the algorithms with large-scale experiments on the PlanetLab infrastructure using a fully-fledged implementation of our approach.

We show in this paper that de Bruijn networks, despite providing efficient search while using constant routing table size, as well as simplicity of the understanding and implementation of such networks, are unsuitable where key distribution will be uneven, a realistic scenario for most practical applications. In presence of arbitrarily skewed data distribution, it has only recently been shown that some traditional P2P overlay networks with non-constant (typically logarithmic) instead of constant routing table size can meet conflicting objectives of storage load balancing as well as search efficiency. So this paper, while showing that de Bruijn networks fail to meet these dual objectives, opens up a more general problem for the research community as to whether P2P systems with constant routing table can at all achieve the conflicting objectives of retaining search efficiency as well as storage load balancing, while preserving key ordering (which leads to uneven key distribution).

Identification is an essential building block for many services in distributed information systems. The quality and purpose of identification may differ, but the basic underlying problem is always to bind a set of attributes to an identifier in a unique and deterministic way. Name/directory services, such as DNS, X.500, or UDDI, are a well-established concept to address this problem in distributed information systems. However, none of these services addresses the specific requirements of peer-to-peer systems with respect to dynamism, decentralization, and maintenance. We propose the implementation of directories using a structured peer-to-peer overlay network and apply this approach to support self-contained maintenance of routing tables with dynamic IP addresses in structured P2P systems. Thus, we keep routing tables intact without affecting the organization of the overlay networks, making it logically independent of the underlying network infrastructure. Even though the directory is self-referential, since it uses its own service to maintain itself, we show that it is robust due to a self-healing capability. For security, we apply a combination of PGP-like public key distribution and a quorum-based query scheme. We describe the algorithm as implemented in the P-Grid P2P lookup system (http:// www.p-grid.org/) and give a detailed analysis and simulation results demonstrating the efficiency and robustness of our approach.

This paper studies the problem of updates in decentralised and self-organising P2P systems in which peers have low online probabilities and only local knowledge. The update strategy we propose for this environment is based on a hybrid push/pull rumor spreading algorithm and provides a fully decentralised, efficient and robust communication scheme which offers probabilistic guarantees rather than ensuring strict consistency. We describe a generic analytical model to investigate the utility of our hybrid update propagation scheme from the perspective of communication overhead.