Component repositories play an increasingly relevant role in software life-cycle management, from software distribution to end-user, to deployment and upgrade management. Software components shipped via such repositories are equipped with rich metadata that describe their relationship (e.g., Dependencies and conflicts) with other components. In this practice paper we show how to use a tool, distcheck, that uses component metadata to identify all the components in a repository that cannot be installed (e.g., Due to unsatisfiable dependencies), provides detailed information to help developers understanding the cause of the problem, and fix it in the repository. We report about detailed analyses of several repositories: the Debian distribution, the OPAM package collection, and Drupal modules. In each case, distcheck is able to efficiently identify not installable components and provide valuable explanations of the issues. Our experience provides solid ground for generalizing the use of distcheck to other component repositories.

Availability of applications or devices is known to be one of the most critical variables impacting the performances of software systems. We study in this article the problem of finding peers matching a given availability pattern in a peer-to-peer (P2P) system. Motivated by practical examples, we specify two formal problems of availability matching that arise in real applications: disconnection matching , where peers look for partners expected to disconnect at the same time, and presence matching , where peers look for partners expected to be online simultaneously in the future. As a scalable and inexpensive solution, we propose to use epidemic protocols for topology management; we provide corresponding metrics for both matching problems. We evaluated this solution by simulating two P2P applications, task scheduling and file storage , over a new trace of the eDonkey network, the largest one with availability information. We first proved the existence of regularity patterns in the sessions of 14M peers over 27 days. We also showed that, using only 7 days of history, a simple predictor could select predictable peers and successfully predicted their online periods for the next week. Finally, simulations showed that our simple solution provided good partners fast enough to match the needs of both applications, and that consequently, these applications performed as efficiently at a much lower cost. This solution is purely distributed as it does not rely on any central server or oracle to operate. We believe that this work will be useful for many P2P applications for which it has been shown that choosing good partners, based on their availability, drastically improves their performance and stability.

This paper studies source location anonymity in a large monitoring wireless sensor network with a single data collector, and under a global attack. The qualifier ”global” indicates the capability of the eavesdropper (attacker) to capture all network transmissions, and to discern their time and location. We propose a scheme for generating fake network traffic to disguise the real event notification. This scheme is particularly effective for the protection of the monitored asset in delay-intolerant applications monitoring rare and spatially sparse events. Unlike earlier work on this topic, we jointly consider the protection strength, events' dynamics, probability of the attacker's exposure during the attack, notification latency, network overhead, and scalability. The efficiency of the scheme that provides statistical source anonymity is achieved by partitioning network nodes randomly into several node groups. Members of the same group collectively emulate both temporal and spatial distribution of the event. Under such framework, we aim to better model the global eavesdropper, especially her way of using statistical tests to detect the real event. In addition, our approach aims to reduce the per-event work spent to generate the fake traffic while, most importantly, providing a guaranteed latency in reporting the event. The latency is controlled by decoupling the routing from the fake-traffic schedule. A good dummy-source group design also provides a robust protection of event bursts. This is achieved at the expense of the significant overhead as the number of dummy-source groups must be increased to the reciprocal value of the false alarm parameter used in the statistical test. Ultimately, our message is that designing a protection scheme to meet multiple requirements, imposed by realistic application scenarios, involves trade-offs among several performance measures, and calls for an evaluation framework that recognizes these challenges. We believe that the proposed source anonymity protection strategy, and the evaluation framework, are well justified by the abundance of the applications that monitor a rare event with uniform spatial distribution.

In this paper we present an empirical study of a workload gathered by crawling the eDonkey network --- a dominant peer-to-peer file sharing system --- for over 50 days.We first confirm the presence of some known features, in particular the prevalence of free-riding and the Zipf-like distribution of file popularity. We also analyze the evolution of document popularity.We then provide an in-depth analysis of several clustering properties of such workloads. We measure the geographical clustering of peers offering a given file. We find that most files are offered mostly by peers of a single country, although popular files don't have such a clear home country.We then analyze the overlap between contents offered by different peers. We find that peer contents are highly clustered according to several metrics of interest.We propose to leverage this property by allowing peers to search for content without server support, by querying suitably identified semantic neighbours. We find via trace-driven simulations that this approach is generally effective, and is even more effective for rare files. If we further allow peers to query both their semantic neighbours, and in turn their neighbours' neighbours, we attain hit rates as high as over 55% for neighbour lists of size 20.

This paper presents GosSkip, a self organizing and fully distributed overlay that provides a scalable support to data storage and retrieval in dynamic environments. The structure of GosSkip, while initially possibly chaotic, eventually matches a perfect set of Skip-list-like structures, where no hash is used on data attributes, thus preserving semantic locality and permitting range queries. The use of epidemic-based protocols is the key to scalability, fairness and good behavior of the protocol under churn, while preserving the simplicity of the approach and maintaining O(log(N)) state per peer and O(log(N)) routing costs. In addition, we propose a simple and efficient mechanism to exploit the presence of multiple data items on a single physical node. GosSkip's behavior in both a static and a dynamic scenario is further conveyed by experiments with an actual implementation and real traces of a peer to peer workload

No abstract available.

We present improvements to the backtracking technique of pattern-matching compilation. Several optimizations are introduced, such as commutation of patterns, use of exhaustiveness information, and control flow optimization through the use of labeled static exceptions and context information. These optimizations have been integrated in the Objective-Caml compiler. They have shown good results in increasing the speed of pattern-matching intensive programs, without increasing final code size.

Distributed scalable garbage collectors, mostly based on some kind of reference counting, fail to detect distributed cycles of garbage. This problem may lead to important memory leaks in distributed storage systems. In this paper, we present a new algorithm which detects and collects such distributed cycles of garbage. Our algorithm is based on the propagation of marks along chains of remote pointers. It uses two new mechanisms: min-max marking, to propagate two dierent marks to each stub, and sub-generation, to build an acyclic graph on a cycle using back-tracking information. A new technique, called optimistic back-tracking, is also used to speed-up subgeneration. The resulting algorithm is completely distributed, asynchronous, fault-tolerant and inexpensive. Moreover, it collects incrementally all distributed cycles of garbage, without partitioning the system. Thus, it is particularly well adapted to large-scale networks. Finally, it can be easily implemented with minor modications of a local tracing garbage collector. Keywords: distributed garbage collection, cycles, sub-generation, optimistic back-tracing, min-max marking. 1.

Most existing reference-based distributed object systems include some kind of acyclic garbage collection, but fail to provide acceptable collection of cyclic garbage. Those that do provide such GC currently suffer from one or more problems: synchronous operation, the need for expensive global consensus or termination algorithms, susceptibility to communication problems, or an algorithm that does not scale. We present a simple, complete, fault-tolerant, asynchronous extension to the (acyclic) cleanup protocol of the SSP Chains system. This extension is scalable, consumes few resources, and could easily be adapted to work in other reference-based distributed object systems---rendering them usable for very large-scale applications.