Centralized solutions offered by cloud providers are increasingly prevalent in the Internet, despite being single points of failure and threatening the privacy of users by giving access of large amounts of data to a few powerful entities. Decentralized peer-to-peer systems have garnered attention in opposition. However, their limitations, such as high latency and message complexity in searching content constitute a barrier to widespread adoption. This is the case of InterPlanetary File System (IPFS), where the algorithm used to search content comprises two steps: an optimistic and a fallback step. The optimistic step relies on the Bitswap protocol and operates on an unstructured network that tries to find content in a single hop. This solution has low latency but also low success rate. Should a search fail with Bitswap the fallback alternative resorts to the use of a Distributed Hash Table (DHT) to complete the search with a significantly increased latency cost. We propose, implement, and evaluate Goose, an alternative to the Bitswap protocol that exploits principles of informed search to introduce a distributed lightweight indexing scheme and an indirection layer in the unstructured network; increasing the success rate of searches when compared with Bitswap, significantly reducing the reliance on the DHT and improving the median access latency in IPFS by 27% and reducing the number of messages exchanged by up to 67%.

Edge computing is becoming an increasingly popular paradigm, with modern Internet services leveraging hundreds of edge locations to serve their users. However, existing data replication solutions are not designed to operate in this environment, which restricts the edge components of Internet services to operate as read-only caches and entry points for accessing data centers, severely limiting the benefits extracted from the edge. This paper presents Arboreal, a novel distributed data management system for cloud and edge infrastructures that enables stateful edge applications to be deployed with full (read and write) local access to application data, overcoming the limitations of existing solutions. Arboreal's data replication protocol allows it to automatically and dynamically replicate data across edge locations according to application needs, while providing global causal+ consistency. By relying on a hierarchical topology, Arboreal scales to hundreds of edge locations, while recovering from failures in a decentralized and localized manner, without compromising consistency or durability guarantees. Evaluation shows that the scalability of Arboreal heavily outperforms state-of-the-art solutions, while the dynamic replication mechanism allows to effectively support a wide variety of edge scenarios including mobile clients.

This paper introduces the IPFS requested content location service, a software service to monitor the operation of IPFS from the perspective of the content requested through IPFS gateways. The software is provided as a docker stack that consumes the logs of one or more IPFS gateways, extracts the CID of the requested content and the IP address of the requester, and queries the IPFS network for the providers of the content. The software also matches the IP addresses of the requesters and providers with their geographic location, and stores the results in a database for later analysis. The software has been used in our previous measurement study, published at DAIS'23, that analyzed the operation of IPFS from the perspective of the content requested through gateways.

Edge computing offers support for latencyconstrained applications, by replicating data in the edge. Edge storage systems need to adopt both partial replication, as only data of interest needs to be replicated, and weak consistency models, to avoid the overhead and latency induced by the coordination mechanisms of strong consistency models. In this context, session guarantees are a powerful tool that can be used to simplify the design of edge applications. This paper presents Engage, a storage system that offers efficient support for session guarantees in a partially replicated edge setting. To achieve this, Engage combines the use of vector clocks and distributed metadata propagation services with a payload propagation scheme tailored for the edge. We have implemented Engage and evaluated its performance experimentally. The results show that, when compared with previous proposals, the combination of techniques employed by Engage reduce both the number of false dependencies, that can slow down the system, and the signaling overhead, while improving the freshness of data exposed to clients.

Regression testing is an important task in any large software project, however as codebase increases, test suites grow and become composed of highly redundant test cases, thus greatly increasing the time required for testing. To solve this problem various test suite reduction tools have been proposed, however their absolute and relative performance are unclear to their prospective users, since there is a lack of a standardized evaluation or approach for choosing the best reduction tool. This work proposes TESRAC, a framework for assessing and comparing test suite reduction tools, which allows users to evaluate and rank a customizable set of tools in terms of reduction performance according to criteria (coverage, dimension, and execution time), and which can be configured to prioritize specific criteria. We used TESRAC to assess and compare three test suite reduction tools and one test suite prioritization tool that has been adapted to perform test suite reduction, across eleven projects of various dimensions and characteristics. Results show that a test suite prioritization tool can be adapted to perform a adequate test suite reduction, and a subset of tools outperforms the remaining tools for the majority of the projects. However, the project and test suite being reduced can have a strong impact on a tool's performance.

Prototyping and implementing distributed algorithms, particularly those that address challenges related with fault-tolerance and dependability, is a time consuming task. This is, in part, due to the need of addressing low level aspects such as management of communication channels, controlling timeouts or periodic tasks, and dealing with concurrency issues. This has a significant impact for researchers that want to build prototypes for conducting experimental evaluation; practitioners that want to compare different design alternatives/solutions; and even for practical teaching activities on distributed algorithms courses. In this paper we present Babel, a novel framework to develop, implement, and execute distributed protocols and systems. Babel promotes an event driven programming and execution model that simplifies the task of translating typical specifications or descriptions of algorithms into performant prototypes, while allowing the programmer to focus on the relevant challenges of these algorithms by transparently handling time consuming low level aspects. Furthermore, Babel provides, and allows the definition of, networking components that can capture different network capabilities (e.g., P2P, Client/Server, p-accrual Failure Detector), making the code mostly independent from the underlying communication aspects. Babel was built to be generic and can be used to implement a wide variety of different classes of distributed protocols. We conduct our experimental work with two relevant case studies, a Peer-to-Peer application and a State Machine Replication application, that show the generality and ease of use of Babel and present competitive performance when compared with significantly more complex implementations.

The prevalence and availability of cloud infrastructures has made them thede factosolution for storing and archiving data, both for organizations and individual users. Nonetheless, the cloud’s wide spread adoption is still hindered by dependability and security concerns, particularly in applications with large data collections where efficient search and retrieval services are also major requirements. This leads to an increased tension between security, efficiency, and search expressiveness. In this article we tackle this tension by proposing BISEN, a new provably-secure boolean searchable symmetric encryption scheme that improves these three complementary dimensions by exploring the design space of isolation guarantees offered by novel commodity hardware such as Intel SGX, abstracted as Isolated Execution Environments (IEEs). BISEN is the first scheme to support multiple users and enable highly expressive and arbitrarily complex boolean queries, with minimal information leakage regarding performed queries and accessed data, and verifiability regarding fully malicious adversaries. Furthermore, BISEN extends the traditional SSE model to support filter functions on search results based on generic metadata created by the users. Experimental validation and comparison with the state of art shows that BISEN provides better performance with enriched search semantics and security properties.

Nowadays, smart mobile devices generate huge amounts of data in all sorts of gatherings. Much of that data has localized and ephemeral interest, but can be of great use if shared among co-located devices. However, mobile devices often experience poor connectivity, leading to availability issues if application storage and logic are fully delegated to a remote cloud infrastructure. In turn, the edge computing paradigm pushes computations and storage beyond the data center, closer to end-user devices where data is generated and consumed, enabling the execution of certain components of edge-enabled systems directly and cooperatively on edge devices. In this article, we address the challenge of supporting reliable and efficient data storage and dissemination among co-located wireless mobile devices without resorting to centralized services or network infrastructures. We propose Thyme, a novel time-aware reactive data storage system for pervasive edge computing environments, that exploits synergies between the storage substrate and the publish/subscribe paradigm. We present the design of Thyme and elaborate a three-fold evaluation, through an analytical study, and both simulation and real world experimentations, characterizing the scenarios best suited for its use. The evaluation shows that Thyme allows the notification and retrieval of relevant data with low overhead and latency, and also with low energy consumption, proving to be a practical solution in a variety of situations.

Edge computing has emerged as a solution to address existing limitations of cloud computing for bandwidth-heavy and time-sensitive applications, by moving (some) computations from bandwidth saturated Cloud infrastructures closer to client devices, where data is effectively produced and consumed. However, existing materializations of the edge computing paradigm take limited advantage of computational and storage power that exists in the edge and between client devices and the cloud. Most of these leverage static hierarchical topologies (e.g., Fog Computing) to pre-process data before sending it to the Cloud, which limits the advantages that can be extracted from the edge computing paradigm. In the past, peer-to-peer systems have sought to tackle the challenges of increasing scalability and availability for very large systems, with a large number of solutions being proposed namely, distributed overlay networks for resource management. In this paper, we argue that the clever adaptation of peer-to-peer solutions can enable novel applications to fully exploit the potential of the edge. In particular, we study the viability of taking advantage of specialized overlay networks in edge environments to enable the management of a large number of computational resources. Contrary to previous proposals, that assume the environment to be composed of mostly homogeneous devices, our proposal embraces existing heterogeneity and exploits the location of computational resources to devise a (partially) self-organizing overlay network that can be exploited both to provide membership information to applications, but also do efficiently disseminate management information across edge devices. We have conducted an experimental evaluation using container-based emulation in an heterogeneous network composed by 100 devices, with results showing that our protocol is able to maximize the bandwidth usage of the system, allowing more data to flow throughout the network, while retaining high robustness to failures.

To ensure high availability in large scale distributed systems, Conflict-free Replicated Data Types (CRDTs) relax consistency by allowing immediate query and update operations at the local replica, with no need for remote synchronization. State-based CRDTs synchronize replicas by periodically sending their full state to other replicas, which can become extremely costly as the CRDT state grows. Delta-based CRDTs address this problem by producing small incremental states (deltas) to be used in synchronization instead of the full state. However, current synchronization algorithms for delta-based CRDTs induce redundant wasteful delta propagation, performing worse than expected, and surprisingly, no better than state-based. In this paper we: 1) identify two sources of inefficiency in current synchronization algorithms for delta-based CRDTs; 2) bring the concept of join decomposition to state-based CRDTs; 3) exploit join decompositions to obtain optimal deltas and 4) improve the efficiency of synchronization algorithms; and finally, 5) experimentally evaluate the improved algorithms.

The emergence of fog computing has led to the design of multi-layer fog computing models which are organized hierarchically. These models commonly dictate the hierarchical structure to all the participating compute nodes. However, organizing the compute nodes by adding customized connections that do not abide by the hierarchical approach, may result in improved performance due to the network’s properties i.e., latency or bandwidth between the nodes. For this reason, in this paper we propose an alternative to the hierarchical approach, which is the self-organizing compute nodes. These nodes organize themselves into a flat model which leverages on the network’s properties to provide improved performance. The results of the evaluation show that this approach reduces bandwidth utilization (~30%) by using optimized messaging instead of direct messaging. Furthermore, we show that following a flat model, enables the design of mechanisms for fault tolerance which has been mostly neglected in existing hierarchical models.

Nowadays, smart mobile devices generate huge amounts of data in all sorts of gatherings. Much of that data has localized and ephemeral interest, but can be of great use if shared among co-located devices. However, these devices often experience poor connectivity, leading to availability issues if applications' storage and logic are fully delegated to a remote cloud infrastructure. In turn, the edge computing paradigm pushes computations and storage beyond the data center, closer to end-user devices where data is generated and consumed. Thus, enabling the execution of certain components of edge-enabled systems directly and cooperatively on edge devices. In this paper, we address the challenge of supporting reliable and efficient data storage and dissemination among co-located wireless mobile devices without resorting to centralized services or network infrastructures. We propose Thyme, a novel time-aware reactive data storage system for wireless edge networks, that exploits synergies between the storage substrate and the publish/subscribe paradigm. We present the design of Thyme and evaluate it through simulation, characterizing the scenarios best suited for its use. The evaluation shows that Thyme allows for reliable notification and retrieval of relevant data with low overhead and latency.

The prevalence and availability of cloud infrastructures has made them the de facto solution for storing and archiving data, both for organizations and individual users. Nonetheless, the cloud's wide spread adoption is still hindered by dependability and security concerns, particularly in applications with large data collections where efficient search and retrieval services are also major requirements. This leads to an increased tension between security, efficiency, and search expressiveness, which current state of the art solutions try to balance through complex cryptographic protocols that tradeoff efficiency and expressiveness for near optimal security. In this paper we tackle this tension by proposing BISEN, a new provably-secure boolean searchable symmetric encryption scheme that improves these three complementary dimensions by exploring the design space of isolation guarantees offered by novel commodity hardware such as Intel SGX, abstracted as Isolated Execution Environments (IEEs). BISEN is the first scheme to enable highly expressive and arbitrarily complex boolean queries, with minimal information leakage regarding performed queries and accessed data, and verifiability regarding fully malicious adversaries. Furthermore, by exploiting trusted hardware and the IEE abstraction, BISEN reduces communication costs between the client and the cloud, boosting query execution performance. Experimental validation and comparison with the state of art shows that BISEN provides better performance with enriched search semantics and security properties.

With the advent of Edge Computing, suitable, practical, and novel abstractions are required for applications to leverage the existing computational power at the edge. In particular, applications in the domains of smart cities and the Internet of Things (IoT) can rely on devices in the vicinity of data consumers and producers for their operation. While these devices are expected to be equipped with wireless radios, network infrastructure might be unavailable in many scenarios. In those cases, devices must rely on wireless ad hoc networks for coordination and cooperation. In this context, one of the most important primitives is the broadcast of messages, that can be leveraged as a building block to devise more complex distributed services and applications. The literature on wireless ad hoc broadcast algorithms is quite vast, with many different algorithms being proposed which explore or combine different techniques or features in their operation. While such protocols are becoming increasingly relevant, understanding how they relate among them is complicated. To address this challenge, in this paper, we introduce a novel framework that allows to abstract the operation of wireless ad hoc broadcast protocols. Leveraging on our framework, we explore a particularly interesting class of these protocols: neighbor-aware ad hoc broadcast protocols; of which we propose 4 novel protocols. Finally, we rely on a materialization of our framework to implement prototypes of these protocols and experimentally study their performance in a testbed composed of 21 Raspberry Pi 3 - model B.

Storage requirements for visual data have been increasing in recent years, following the emergence of many highly interactive multimedia services and applications for mobile devices in both personal and corporate scenarios. This has been a key driving factor for the adoption of cloud-based data outsourcing solutions. However, outsourcing data storage to the Cloud also leads to new security challenges that must be carefully addressed, especially regarding privacy. In this paper we propose a secure framework for outsourced privacy-preserving storage and retrieval in large shared image repositories. Our proposal is based on IES-CBIR, a novel Image Encryption Scheme that exhibits Content-Based Image Retrieval properties. The framework enables both encrypted storage and searching using Content-Based Image Retrieval queries while preserving privacy against honest-but-curious cloud administrators. We have built a prototype of the proposed framework, formally analyzed and proven its security properties, and experimentally evaluated its performance and retrieval precision. Our results show that IES-CBIR is provably secure, allows more efficient operations than existing proposals, both in terms of time and space complexity, and paves the way for new practical application scenarios.

The design of distributed protocols that run in data centers and enterprise clusters is heavily dependent on synchrony assumptions regarding the timing behavior of the participating nodes and the network. However, little is known about the actual synchrony of real distributed systems, and how it varies across deployments. To better understand this timing behavior and how it impacts the design and implementation of distributed protocols, we conduct an extensive measurement study of the latency for transmitting and processing messages between nodes in four different environments. Our study determines how protocol characteristics affect the latency behavior. We also determine how different environmental factors can affect the measured latency and whether high latency events manifest globally or locally. Our results suggest several directions for reducing latency, and for leveraging recent distributed computing models in a more judicious way.

Distributed storage systems are a fundamental component of large-scale Internet services. To keep up with the increasing expectations of users regarding availability and latency, the design of data storage systems has evolved to achieve these properties by exploiting techniques such as partial replication, geo-replication, and weaker consistency models. How to combine all these techniques in a single solution in a practical and efficient way is highly challenging. In this paper we propose a novel replication scheme that can offer causal+ consistency in a geo-distributed scenario with partial replication, where datacenters replicate different portions of the entire database. We leverage on a recently proposed methodology that decouples the propagation of data and causality-tracking metadata. Our solution presents a novel causal consistency tracking and enforcing algorithm, focusing on maximizing parallelism in the execution of remote operations which, as we show, has a significant influence on the performance of a partially replicated system. We also propose and implement a design to integrate our solution in the popular Cassandra database. Experimental results show that, by exploring a new position in the trade-off between throughput and data visibility (by balancing the execution of local and remote operations, respectively), our solution presents overall good performance.

The edge computing paradigm brings the promise of overcoming the practical scalability limitations of cloud computing, that are a result of the high volume of data produced by Internet of Things (IoT) and other large-scale applications. The principle of edge computing is to move computations beyond the data center, closer to end-user devices where data is generated and consumed. This new paradigm creates the opportunity for edge-enabled systems and applications, that have components executing directly and cooperatively on edge devices. Having systems' components, actively and directly, collaborating in the edge, requires some form of distributed monitoring as to adapt to variable operational conditions. Monitoring requires efficient ways to aggregate information collected from multiple devices. In particular, and considering some IoT applications, monitoring will happen among devices that communicate primarily via wireless channels. In this paper we study the practical performance of several distributed continuous aggregation protocols in the wireless ad hoc setting, and propose a novel protocol that is more precise and robust than competing alternative.

In this paper we tackle the practical challenges of searching encrypted multimodal data (i.e., data containing multiple media formats simultaneously), stored in public cloud servers, with reduced information leakage. To this end we propose MuSE, a Multimodal Searchable Encryption scheme that, by combining only standard cryptographic primitives and symmetric-key block ciphers, allows cloud-backed applications to dynamically store, update, and search multimodal datasets with privacy and efficiency guarantees. As searching encrypted data requires a tradeoff between privacy and efficiency, we also propose a variant of MuSE that resorts to partially homomorphic encryption to further reduce information leakage, but at the cost of additional computational overhead. Both schemes are formally proven secure and experimentally evaluated regarding performance and search precision. Experiments with realistic datasets show that our contributions achieve interesting levels of efficiency and privacy, making MuSE particularly suitable for practical application scenarios.

In this paper we propose MIE, a Multimodal Indexable Encryption framework that for the first time allows mobile applications to securely outsource the storage and search of their multimodal data (i.e. data containing multiple media formats) to public clouds with privacy guarantees. MIE is designed as a distributed framework architecture, leveraging on shared cloud repositories that can be accessed simultaneously by multiple users. At its core MIE relies on Distance Preserving Encodings (DPE), a novel family of encoding algorithms with cryptographic properties that we also propose. By applying DPE to multimodal data features, MIE enables high-cost clustering and indexing operations to be handled by cloud servers in a privacy-preserving way. Experiments show that MIE achieves better performance and scalability when compared with the state of art, with measurable impact on mobile resources and battery life.

Online services such as Facebook or Twitter have public APIs to enable an easy integration of these services with third party applications. However, the developers who design these applications have no information about the consistency provided by these services, which exacerbates the complexity of reasoning about the semantics of the applications they are developing. In this paper, we show that is possible to deploy a transparent middleware between the application and the service, which enables a fine-grained control over the session guarantees that comprise the consistency semantics provided by these APIs, without having to gain access to the implementation of the underlying services. We evaluated our middleware using the Facebook public API and the Redis datastore, and our results show that we are able to provide fine-grained control of the consistency semantics incurring in a small local storage and modest latency overhead.

Many web applications are built around direct interactions among users, from collaborative applications and social networks to multi-user games. Despite being user-centric, these applications are usually supported by services running on servers that mediate all interactions among clients. When users are in close vicinity of each other, relying on a centralized infrastructure for mediating user interactions leads to unnecessarily high latency while hampering fault-tolerance and scalability.

Most geo-replicated storage systems use weak consistency to avoid the performance penalty of coordinating replicas in different data centers. This departure from strong semantics poses problems to application programmers, who need to address the anomalies enabled by weak consistency. In this paper we use a recently proposed isolation level, called Non-Monotonic Snapshot Isolation, to achieve ACID transactions with low latency. To this end, we present Blotter, a geo-replicated system that leverages these semantics in the design of a new concurrency control protocol that leaves a small amount of local state during reads to make commits more efficient, which is combined with a configuration of Paxos that is tailored for good performance in wide area settings. Read operations always run on the local data center, and update transactions complete in a small number of message steps to a subset of the replicas. We implemented Blotter as an extension to Cassandra. Our experimental evaluation shows that Blotter has a small overhead at the data center scale, and performs better across data centers when compared with our implementations of the core Spanner protocol and of Snapshot Isolation on the same codebase.

While several proposals for the specification and implementation of various consistency models exist, little is known about what is the consistency currently offered by online services with millions of users. Such knowledge is important, not only because it allows for setting the right expectations and justifying the behavior observed by users, but also because it can be used for improving the process of developing applications that use APIs offered by such services. To fill this gap, this paper presents a measurement study of the consistency of the APIs exported by four widely used Internet services, the Facebook Feed, Facebook Groups, Blogger, and Google+. To conduct this study, our work (1) proposes definitions for a set of relevant consistency properties, (2) develops a simple, yet generic methodology comprising a small number of tests, which probe these services from a user perspective, and try to uncover consistency anomalies that are key to our definitions, and (3) reports on the analysis of the data obtained from running these tests for a period of several weeks. Our measurement study shows that some of these services do exhibit consistency anomalies, including some behaviors that may appear counter-intuitive for users, such as the lack of session guarantees for write monotonicity.

We present a new technique for designing distributed protocols for building reliable stateful services called Visigoth Fault Tolerance (VFT). VFT introduces the Visigoth model, which makes it possible to calibrate the timing assumptions of a system using a threshold of slow processes or messages, and also to distinguish between non-malicious arbitrary faults and correlated attack scenarios. This enables solutions that leverage the characteristics of data center systems, namely their secure environment and predictable performance, in order to allow replicated systems to be more efficient with respect to the utilization of resources than those designed under asynchrony and Byzantine assumptions, while avoiding the need to make a system synchronous, or to restrict failure modes to silent crashes. We implemented a VFT protocol for a state machine replication library, and ran several benchmarks. Our evaluation shows that VFT has comparable performance to existing schemes and brings significant benefits in terms of the throughput per dollar, i.e., the server cost for sustaining a certain level of request execution.

Storage requirements for visual data have been increasing in recent years, following the emergence of many new highly interactive multimedia services and applications for both personal and corporate use. This has been a key driving factor for the adoption of cloud-based data outsourcing solutions. However, outsourcing data storage to the Cloud also leads to new challenges that must be carefully addressed, especially regarding privacy. In this paper we propose a secure framework for outsourced privacy-preserving storage and retrieval in large image repositories. Our proposal is based on IES-CBIR, a novel Image Encryption Scheme that displays Content-Based Image Retrieval properties. Our solution enables both encrypted storage and searching using CBIR queries while preserving privacy. We have built a prototype of the proposed framework, formally analyzed and proven its security properties, and experimentally evaluated its performance and precision. Our results show that IES-CBIR is provably secure, allows more efficient operations than existing proposals, both in terms of time and space complexity, and enables more reliable practical application scenarios.

Unstructured P2P networks have been widely used to implement resource location systems that support complex queries semantics. Unfortunately these systems usually rely on search algorithms based on some variant of flooding, which generate a significant amount of duplicate messages. An effective way to minimize the cost of query flooding in unstructured P2P networks is the use of super-peers. On the other hand, super-peers may become overloaded or may fail, and have a negative impact on the performance and connectivity of the overlay. These risks can be circumvented by replicating super-peers. Replication serves the dual purpose of supporting load distribution and fault-tolerance purposes. This paper proposes a novel algorithm to construct an overlay network connecting replicated super-peers. We have called the resulting overlay, Overnesia. The paper also proposes techniques to perform query routing that leverage on the unique properties of Overnesia to effectively distribute the query processing load among replicas.

This paper proposes a Geo-distributed key-value datastore, named ChainReaction, that offers causal+ consistency, with high performance, fault-tolerance, and scalability. ChainReaction enforces causal+ consistency which is stronger than eventual consistency by leveraging on a new variant of chain replication. We have experimentally evaluated the benefits of our approach by running the Yahoo! Cloud Serving Benchmark. Experimental results show that ChainReaction has better performance in read intensive workloads while offering competitive performance for other workloads. Also we show that our solution requires less metadata when compared with previous work.

In this paper we present Roller chain, a novel Distributed Hash Table that offers efficient data storage through the combination of gossip-based and structured overlay networks. The unstructured component maintains clusters of fully connected nodes, where each cluster acts as a virtual node in the structured component. This architecture simplifies the management of data replication and balances the load among nodes in the system. We have implemented a prototype of Roller chain that we have used to experimentally validate its performance against other state of the art solutions.

Mobile devices with wireless communication capabilities are a constant in our daily lives. This offers the possibility for such devices to exchange information for their users to assist in their daily lives. Consider for instance the exchange of information about points of interest in the locations that the user usually frequents. One should expect those devices to support such an application in a decentralized fashion, through pair wise interactions, without the interaction of the user, and avoiding to disclose information that might be sensitive to a central entity. Current solutions are not suitable for supporting such applications since most rely on some kind of centralized architecture (either brokers or rendezvous nodes), other solutions that don't rely on centralized solutions present a high overhead. To address this challenge, in this paper we propose MobUser, a novel topic-based publish-subscribe service specially tailored for supporting location-aware operation for mobile devices in a decentralized fashion. Extensive experimental work shows that MobUser offers not only better performance but also superior delivery rates when compared with a state-of-the-art mobile publish subscribe solution. We also show through a prototype implementation deployed on Android 4.0 devices, that the overhead and energy consumption of MobUser is acceptably low.

Gossip, or epidemic, protocols have emerged as a highly scalable and resilient approach to implement several application level services such as reliable multicast, data aggregation, publish-subscribe, among others. All these protocols organize nodes in an unstructured random overlay network. In many cases, it is interesting to bias the random overlay in order to optimize some efficiency criteria, for instance, to reduce the stretch of the overlay routing. In this paper, we propose X-BOT, a new protocol that allows to bias the topology of an unstructured gossip overlay network. X-BOT is completely decentralized and, unlike previous approaches, preserves several key properties of the original (nonbiased) overlay (most notably, the node degree and consequently, the overlay connectivity). Experimental results show that X-BOT can generate more efficient overlays than previous approaches independently of the underlying physical network topology.

The Sybil Attack is a serious threat to the secure and dependable operation of wireless ad hoc networks. This paper proposes an algorithm to provide each correct node in an one-hop wireless network with a quorum of non-Sybil identities from the neighbourhood. The quorums provided to different correct nodes may differ, but their intersection is composed by a majority of correct identities, with an arbitrarily close to 1 probability. Therefore, the quorums may be used for different purposes, such as voting. The algorithm is based on the combination of different resource tests, to efficiently detect (and exclude) Sybil identities.

Recently there has been an effort to build scalable and reliable application-level multicast solutions that combine the resilience of pure gossip-based with the efficiency of tree-based schemes. However, such solutions assume that participants have unlimited resources, for instance, that they can send an unbounded number of messages to mask network omissions. Such scenario is not realistic, specially for streaming protocols, where messages can be transmitted at a very high rate and have a small temporal validity. In this paper, we propose RASM, a scalable distributed protocol for application-level multicast. Our protocol is based on the combination of gossip-based and tree-based multicast schemes. Unlike previous approaches, which strive to combine gossip-based and tree-based schemes, our solution takes into consideration the reliability of components: nodes and communication links can fail, unexpectedly, ceasing their operation and dropping messages, respectively. Experimental results show that our scheme offers better reliability than previous solutions with low overhead.

One way to efficiently disseminate information in a P2P overlay is to rely on a spanning tree. However, in a tree, interior nodes support a much higher load than leaf nodes. Also, the failure of a single node can break the tree, impairing the reliability of the dissemination protocol. These problems can be addressed by using multiple trees, such that each node is interior in just a few trees and a leaf node in the remaining, the multiple trees approach allows to achieve load distribution and also to send redundant information for fault-tolerance. This paper proposes Thicket, a decentralized algorithm to efficiently build and maintain such multiple trees over a single unstructured overlay network. The algorithm has been implemented and is extensively evaluated using simulation in a P2P overlay with 10.000 nodes.

Gossip, or epidemic, protocols have emerged as a highly scalable and resilient approach to implement several application level services such as reliable multicast, data aggregation, publish-subscribe, among others. All these protocols organize nodes in an unstructured random overlay network. In many cases, it is interesting to bias the random overlay in order to optimize some efficiency criteria, for instance, to reduce the stretch of the overlay routing. In this paper we propose X-BOT, a new protocol that allows to bias the topology of an unstructured gossip overlay network. X-BOT is completely decentralized and, unlike previous approaches, preserves several key properties of the original (non-biased) overlay (most notably, the node degree and consequently, the overlay connectivity). Experimental results show that X-BOT can generate more efficient overlays than previous approaches.

Gossip, or epidemic, protocols have emerged as a powerful strategy to implement highly scalable and resilient reliable broadcast primitives. Due to scalability reasons, each participant in a gossip protocol maintains a partial view of the system. The reliability of the gossip protocol depends upon some critical properties of these views, such as degree distribution and clustering coefficient. Several algorithms have been proposed to maintain partial views for gossip protocols. In this paper, we show that under a high number of faults, these algorithms take a long time to restore the desirable view properties. To address this problem, we present HyParView, a new membership protocol to support gossip-based broadcast that ensures high levels of reliability even in the presence of high rates of node failure. The HyParView protocol is based on a novel approach that relies in the use of two distinct partial views, which are maintained with different goals by different strategies.

There is an inherent trade-off between epidemic and deterministic tree-based broadcast primitives. Tree-based approaches have a small message complexity in steady-state but are very fragile in the presence of faults. Gossip, or epidemic, protocols have a higher message complexity but also offer much higher resilience. This paper proposes an integrated broadcast scheme that combines both approaches. We use a low cost scheme to build and maintain broadcast trees embedded on a gossip-based overlay. The protocol sends the message payload preferably via tree branches but uses the remaining links of the gossip overlay for fast recovery and expedite tree healing. Experimental evaluation presented in the paper shows that our new strategy has a low overhead and that is able to support large number of faults while maintaining a high reliability.