Catálogo de publicaciones - libros

Distributed systems have experienced a shift of scale in the past few years. This evolution has generated an interest in peer-to-peer systems and resulted in much interesting work. Peer-to-peer systems are characterized by their potential to scale due to their fully decentralized nature. They are self-organizing, adapting automatically to peer arrivals and departures, and are highly resilient to failures. They rely on a symmetric communication model where peers act both as servers and clients. As the peer-to-peer concepts and technologies become more mature, many distributed services and applications relying on this model are envisaged in the context of large-scale distributed and parallel systems. This topic examines peer-to-peer technologies, applications, and systems, and also identifies key research issues and challenges. Twenty-six papers were submitted to the track and we accepted six. We organized two sessions, the first devoted to the problem of query management in structured and unstructured overlay networks, the second containing a broader selection of topics.

In this article, we introduce a way to distribute an index database of XML documents on an unstructured peer-to-peer network with a flat topology (i.e. with no super-peer). We then show how to perform content path query routing in such networks. Nodes in the network maintain a set of Multi Level Bloom Filters that summarises structural properties of XML documents. They propagate part of this information to their neighbor nodes, allowing efficient path query routing in the peer-to-peer network, as shown by the evaluation tests presented.

Distributed Hash Tables (DHTs) provide a scalable solution for data sharing in large scale distributed systems, P2P systems. However, they only provide good support for exact-match queries, and it is hard to support complex queries such as top-k queries. In this paper, we propose a family of algorithms which deal with efficient processing of top-k queries in DHTs. We evaluated the performance of our solution through implementation over a 64-node cluster and simulation. Our performance evaluation shows very good performance, in terms of communication cost and response time.

We introduce SONAR, a structured overlay to store and retrieve objects addressed by multi-dimensional names (). The overlay has the shape of a multi-dimensional torus, where each node is responsible for a contiguous part of the data space. A uniform distribution of keys on the data space is not necessary, because denser areas get assigned more nodes. To nevertheless support logarithmic routing, SONAR maintains, per dimension, fingers to other nodes, that span an exponentially increasing number of . Most other overlays maintain such fingers in the instead and therefore require a uniform data distribution. SONAR, in contrast, avoids hashing and is therefore able to perform range queries of arbitrary shape in a logarithmic number of routing steps—independent of the number of system- and query-dimensions.

SONAR needs just one hop for updating an entry in its routing table: A longer finger is calculated by querying the node referred to by the next shorter finger for its shorter finger. This doubles the number of spanned nodes and leads to exponentially spaced fingers.

The dominant eigenvector of matrices defined by weighted links in overlay networks plays an important role in many peer-to-peer applications. Examples include trust management, importance ranking to support search, and virtual coordinate systems to facilitate managing network proximity. Robust and efficient asynchronous distributed algorithms are known only for the case when the dominant eigenvalue is exactly one. We present a fully distributed algorithm for a more general case: non-negative square matrices that have an arbitrary dominant eigenvalue. The basic idea is that we apply a gossip-based aggregation protocol coupled with an asynchronous iteration algorithm, where the gossip component controls the iteration component. The norm of the resulting vector is an unknown finite constant by default; however, it can optionally be set to any desired constant using a third gossip control component. Through extensive simulation results on artificially generated overlay networks and real web traces we demonstrate the correctness, the performance and the fault tolerance of the protocol.

Free riding is a common phenomenon in P2P networks. Although several mechanisms have been proposed to handle free riding—mostly to exclude free riders, few of them have actually been adopted in practical systems. This may be attributed to the fact that they are nontrivial, and that completely eliminating free riders could jeopardize the sheer power created by the huge volume of participants in a P2P network. Rather than excluding free riders, in this paper we incorporate and utilize them to provide global index service to the files shared by other peers. The simulation results indicate that our model can significantly boost the search efficiency of a plain Gnutella, and the model is quite resistant to system churn rate and the ratio of free riding.

Publish/subscribe systems provide a useful paradigm for selective data dissemination and most of the complexity related to addressing and routing is encapsulated within the network infrastructure. The challenge of such systems is to organize the peers so as to best match the interests of the consumers, minimizing false positives and avoiding false negatives.

In this paper, we propose and evaluate the use of R-trees for organizing the peers of a content-based routing network. We adapt three well-known variants of R-trees to the content dissemination problem striving to minimize the occurrence of false positives while avoiding false negatives. The effectiveness and accuracy of each structure is analyzed by extensive simulations.

Parallel computing is increasingly exposed to the development and challenges of distributed systems, such as the lack of load balancing, asynchrony, long latencies, network partitions, failures, disconnected operations, heterogeneity and protocol standardization. Furthermore, distributed systems are becoming larger, more diverse and more dynamic. This Euro-Par topic provides a forum for research and practice, of interest to both academia and industry, about distributed systems, distributed computing, distributed algorithms, and parallel processing on distributed systems. Submission was encouraged across the whole area, with emphasis on the following: design and practice of distributed algorithms and data structures, analysis of the behaviour of distributed systems and algorithms, distributed operating systems, parallel processing on distributed systems, resource and service discovery, resource sharing and in distributed systems, distributed fault tolerance, security in distributed systems, scalability, concurrency and performance in distributed systems, middleware for parallel computations, web services, interoperability and standards, self-organised and self-adjusting distributed systems.

Up to now, more and more people use Internet storage services as a new way of sharing. File sharing by a distributed storage system is quite different from a specific sharing application like BitTorrent. And as large file sharing becomes popular, the data transmission rate takes the place of the response delay to be the major factor influencing user experience. This paper introduces strategies used to accelerate file sharing with low bandwidth consumptions in a deployed wide-area networked storage system - . We use a popularity and locality sensitive replication strategy to put files closer to users that request it frequently. The server selection scheme and the replication mechanism are also presented. Experimental results show these methods offer better sharing speed and cost less network bandwidth than conventional caching schemes.

Prefetching transfers a data item in advance from its storage location to its usage location so that communication is hidden and does not delay computation. We present a novel prefetching technique for object-based Distributed Shared Memory (DSM) systems and discuss its implementation. In contrast to page-based DSMs, an object-based DSM distributes data on the level of objects, rendering current prefetchers for page-based DSMs unsuitable due to more complex data streams. To predict future data accesses, our prefetcher uses a new predictor (Esodyp+) based on a modified Markov model that automatically adapts to program behavior. We compare our prefetching strategy with both a stride prefetcher and the prefetcher of the Delphi DSM system. For several benchmarks our prefetching strategy reduces the number of network messages by about 60 %. On 8 nodes, runtime is reduced by 15 % on average. Hence, network-bound programs benefit from our solution. In contrast to the other predictors, Esodyp+ achieves a prediction accuracy above 80 % with only 8 % of unused prefetches for the benchmarks.