SpotlightDependability in Peer-to-Peer SystemsAiming to ease the problems associated withmaking a variety of items available to multi-ple users over the Internet, peer-to-peer (P2P)systems create fully decentralized systems. Byinvolving lots of peers, computational and storagecapabilities increase; moreover, data replication,caching, and efficient query routing enhance over-all performance.P2P systems can reduce complexity becauseeach server deals with a smaller set of data andclients. However, P2P systems’ long-running anddynamic nature creates dependability issues. Inthis article, we consider dependability with refer-ence to scalability, fault-tolerance, security, andanonymity properties. Scalability and fault-toler-ance depend on the number of peers and theirinterconnection, but security and anonymitydepend on the systems’ open nature and the Inter-net’s communication infrastructure. The fact thatany peer can contact any other in a network intro-duces data-integrity and privacy issues.In the not-too-distant future, self-adaptable anddependable systems will emerge from the develop-ment of nomadic technologies, mobile devices, andubiquitous computing. Recent research has usedP2P systems to organize ubiquitous environments1and to perform worldwide computations.2Becausemost current systems were designed to address spe-cific application domains, similar concepts havebeen addressed with different terminologies andmodels. An output of the comparison provided inthis article is an attempt to move toward commonterms and definitions. Because the models under-lying current P2P systems must be understood tosupport a thorough investigation of dependabilityproperties, we briefly examine the most popularP2P systems and then compare how these systemsaddress dependability.P2P-Based SystemsMost developers initially used P2P technology toimplement file-sharing systems that spannedInternet-like environments, with a focus onsearching and routing. More recently, they haveused it to implement hash-map-like functionali-ties (the ability to map a key to a location) in dis-tributed settings. P2P technology is evolving inresponse to peer unreliability, which continues tofurther the need for fault-tolerant systems. It hasalso become clear that effective systems requiresecurity and anonymity, so encryption andauthentication techniques for large-scale decen-tralized systems are starting to arrive. P2P systemshave further influenced research into distributedfile systems, which are starting to resemble theP2P organization models.Several organizational models with differentdegrees of dependability have been proposed overthe past few years. Before discussing specificdependability issues, though, let’s look at the mostrepresentative P2P systems. They reveal the basicmechanisms that support the system propertiesdiscussed in the rest of the article. To unify the ter-minology, we’ll use the term item to refer to any54 JULY • AUGUST 2004 Published by the IEEE Computer Society 1089-7801/04/$20.00 © 2004 IEEE IEEE INTERNET COMPUTINGServer-centric architectures such as the Web’s suffer from well-known problemsrelated to application size and increasing user requests.Peer-to-peer systems canhelp address some of the key challenges, but this survey of several current P2Psystems shows that dependability remains an open issue. To perform in Internet-scale applications, P2P systems must address the four major properties ofdependable systems: scalability, fault-tolerance, security, and anonymity.Editor: Siobhán Clarke • [email protected] DePaoli and Leonardo Mariani • Università degli Studi di Milano Bicoccageneral entity — a file, object, or other artifact —stored in a peer in any of these systems.NapsterNapster (www.napster.com) lets users share audiofiles via network nodes. Although one of the old-est and most famous, however, Napster is a hybridrather than a true P2P system (the search serviceis centralized). When a peer joins the network, ituploads information about locally stored files to acentral server, and clients locate these files bysending requests to that server. Peer-to-peer inter-actions occur only during file transfer.GnutellaIn contrast to the Napster approach, Gnutella(www.gnutella.com)3supplies an open, decentral-ized, P2P search protocol. New peers join a Gnutel-la network by contacting an already connectedpeer, which they then use to discover additionalpeers by broadcasting ping messages. The Gnutel-la approach does not require centralization: querymessages are broadcast along the network throughthe set of known peers. Each peer receiving aquery first tries to satisfy the request with its localdata and then forwards the message to all knownpeers. In this way, a query propagates in the sys-tem until an associated time-to-live (maximumnumber of hops) expires.P-GridThe self-organizing P-Grid (www.p-grid.org)4sys-tem addresses responsiveness and robustness byexploiting a tree-based distributed indexing struc-ture that maps items with nodes according to abinary-key value. Each peer p is associated with anode n of the tree; therefore, p becomes responsiblefor all items contained in the subtree rooted at noden. When a new peer joins the network, it computesrouting data via a peer that is already part of P-Grid and negotiates item responsibility. The con-struction algorithm requires only local interactionsand guarantees that all the tree’s nodes can bereached. The tree structure ensures good search-response time — at most O(log n), where n is thenumber of items in the network — and moderatesthe amount of routing data stored on each peer.ChordBy implementing a distributed lookup protocol,Chord (www.pdos.lcs.mit.edu/chord/)5addressesthe problem of efficiently locating which nodesstore which particular data items. This protocolmaps peers and items to an m-bit identifier via ahash function and then arranges them in a “ring”network of at most 2mpeers. Each peer knows atleast its successor peer.When a peer joins the network, it takes theposition in the ring corresponding to the assignedhash key and assumes responsibility for itemsaccording to the formula itemID mod 2m =peerID. The same formula assigns new items topeers; if the computed peer doesn’t exist, the itemis transferred to the next available peer with agreater identifier. Ring-structure navigabilityincreases by making each peer hold a finger table(a shortcut that reduces the numbers of hops)with at most m
View Full Document
Unlocking...