A Peer-to-Peer Replica Location Service Based on a Distributed Hash Table
Published 1 April 2005
Min Cai, Ann Chervenak, Martin Frank
Citations104
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A Peer-to-Peer Replica Location Service with properties of self-organization, fault-tolerance and improved scalability, and a predecessor replication scheme is introduced that reduces query hotspots of popular mappings by distributing queries among nodes.
Abstract
A Replica Location Service (RLS) allows registration and discovery of data replicas. In earlier work, we proposed an RLS framework and described the performance and scalability of an RLS implementation in Globus Toolkit Version 3.0. In this paper, we present a Peer-to-Peer Replica Location Service (P-RLS) with properties of self-organization, fault-tolerance and improved scalability. P-RLS uses the Chord algorithm to self-organize PRLS servers and exploits the Chord overlay network to replicate P-RLS mappings adaptively. Our performance measurements demonstrate that update and query latencies increase at a logarithmic rate with the size of the P-RLS network, while the overhead of maintaining the P-RLS network is reasonable. Our simulation results for adaptive replication demonstrate that as the number of replicas per mapping increases, the mappings are more evenly distributed among P-RLS nodes. We introduce a predecessor replication scheme and show it reduces query hotspots of popular mappings by distributing queries among nodes.
Keywords
Computer Science
Chord
9,645 Citations2001Ion Stoica, Robert Morris +3 more
Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
Communications of the ACMSpace/time trade-offs in hash coding with allowable errors
7,507 Citations1970Burton H. Bloom
Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time.
Lecture notes in computer sciencePastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems
7,296 Citations2001Antony Rowstron, Peter Druschel
Experimental results obtained with a prototype implementation on an emulated network of up to 100,000 nodes confirm Pastry's scalability and efficiency, its ability to self-organize and adapt to node failures, and its good network locality properties.
A scalable content-addressable network
6,407 Citations2001Sylvia Ratnasamy, Paul Francis +3 more
The concept of a Content-Addressable Network (CAN) as a distributed infrastructure that provides hash table-like functionality on Internet-like scales is introduced and its scalability, robustness and low-latency properties are demonstrated through simulation.
Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing
2,143 Citations2001Ben Y. Zhao, John Kubiatowicz +1 more
Tapestry is an overlay location and routing infrastructure that provides location-independent routing of messages directly to the closest copy of an object or service using only point-to-point links and without centralized resources.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Measurement study of peer-to-peer file sharing systems</title>
1,922 Citations2001Stefan Saroiu, Krishna P. Gummadi +1 more
ACM SIGCOMM Computer Communication ReviewA scalable content-addressable network
1,789 Citations2001Sylvia Ratnasamy, Paul Francis +3 more
Communications of the ACMSkip lists: a probabilistic alternative to balanced trees
1,165 Citations1990William Pugh
In this chapter three algorithms for insertion and deletion in skip lists are studied, which are much simpler and significantly faster than equivalent algorithms for balanced trees.
The dangers of replication and a solution
1,027 Citations1996Jim Gray, Pat Helland +2 more
A new two-tier replication algorithm is proposed that allows mobile (disconnected) applications to propose tentative update transactions that are later applied to a master copy, to avoid the instability of other replication schemes.
IEEE Transactions on ComputersCoda: a highly available file system for a distributed workstation environment
865 Citations1990Mahadev Satyanarayanan, James J. Kistler +4 more
IEEE Internet ComputingMapping the Gnutella network
766 Citations2002R. Matei, Adriana Iamnitchi +1 more
This work studied the topology and protocols of the public Gnutella network to evaluate costs and benefits of the peer-to-peer (P2P) approach and to investigate possible improvements that would allow better scaling and increased reliability in Gnutsella and similar networks.
Accessing nearby copies of replicated objects in a distributed environment
762 Citations1997C. Greg Plaxton, Rajmohan Rajaraman +1 more
ACM SIGOPS Operating Systems ReviewSecure routing for structured peer-to-peer overlay networks
752 Citations2002Miguel Castro, Peter Druschel +3 more
This paper studies attacks aimed at preventing correct message delivery in structured peer-to-peer overlays and presents defenses to these attacks, and describes and evaluates techniques that allow nodes to join the overlay, to maintain routing state, and to forward messages securely in the presence of malicious nodes.
Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and
624 Citations2001Ben Y. Zhao, John Kubiatowicz +1 more
SkipNet: a scalable overlay network with practical locality properties
614 Citations2003Nicholas J. A. Harvey, Michael B. Jones +3 more
Cutting-edge scalable overlay network SkipNet is a scalable overlay network that provides controlled data placement and guaranteed routing locality by organizing data primarily by string names.
IEEE/ACM Transactions on NetworkingAnalyzing Peer-To-Peer Traffic Across Large Networks
587 Citations2004Subhabrata Sen, Jun Wang
The high volume and good stability properties of P2P traffic suggests that the P2P workload is a good candidate for being managed via application-specific layer-3 traffic engineering in an ISP's network.
Lecture notes in computer scienceKoorde: A Simple Degree-Optimal Distributed Hash Table
567 Citations2003M. Frans Kaashoek, David R. Karger
Koorde is a new distributed hash table (DHT) based on Chord 15 and the de Bruijn graphs 2 that meets various lower bounds, such as O(log n) hops per lookup request with only 2 neighbors per node.
The SDSC storage resource broker
557 Citations2010Chaitanya Baru, Reagan Moore +2 more
The architecture and various features of the SDSC SRB are described, which provides applications a uniform API to access heterogeneous distributed storage resources including, filesystems, database systems, and archival storage systems.
Journal of Grid ComputingMapping Abstract Complex Workflows onto Grid Environments
484 Citations2003Ewa Deelman, James Blythe +9 more
The current ACWG based on AI planning technologies is described and it is outlined how these technologies can play a crucial role in developing complex application workflows in Grid environments.
Flexible update propagation for weakly consistent replication
474 Citations1997Karin Anna Petersen, Mike Spreitzer +3 more
The anti-entropy protocol is presented in detail, describing the design decisions and resulting features, and how it enables replica convergence, and updates can be propagated using floppy disks and similar transportable media.
Lecture notes in computer scienceSecurity Considerations for Peer-to-Peer Distributed Hash Tables
401 Citations2002Emil Sit, Robert Morris
This paper looks at what sorts of security problems are inherent in large peer-to-peer systems based on distributed hash lookup systems, and proposes some design principles for detecting and preventing these problems.
ACM SIGMOD RecordThe dangers of replication and a solution
392 Citations1996Jim Gray, Pat Helland +2 more
Giggle: A Framework for Constructing Scalable Replica Location Services
382 Citations2002Ann Chervenak, Ewa Deelman +10 more
Secure routing for structured peer-to-peer overlay networks
328 Citations2002Miguel Castro, Peter Druschel +3 more
ACM Transactions on AlgorithmsSkip graphs
326 Citations2007James Aspnes, Gauri Shah
Skip graphs are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality.
Lecture notes in computer scienceRouting Algorithms for DHTs: Some Open Questions
292 Citations2002Sylvia Ratnasamy, Ion Stoica +1 more
Even though they were introduced only a few years ago, peer-to-peer (P2P) filesharing systems are now one of the most popular Internet applications and have become a major source of Internet traffic, so it is extremely important that these systems be scalable.
Analyzing peer-to-peer traffic across large networks
290 Citations2002Subhabrata Sen, Jia Wang
The high volume and good stability properties of P2P traffic indicates that the P2P workload is a good candidate for being managed via application-specific layer-3 traffic engineering in an ISP's network.
The MIT Press eBooksThe LOCUS Distributed System Architecture
200 Citations1986Gerald J. Popek
The LOCUS Distributed System Architecture is included in the Computer Systems series, edited by Herb Schwetman and contains architectural extensions to support extensive interprocess communication and internetworking.
Database replication techniques: a three parameter classification
168 Citations2002Matthias Wiesmann, Fernando Pedone +3 more
This paper analyses existing eager techniques using three key parameters (server architecture, server interaction and transaction termination) and distinguishes eight classes of eager replication protocols and, for each category, discusses its requirements, capabilities and cost.
Lecture notes in computer scienceSkip lists: A probabilistic alternative to balanced trees
162 Citations1989William Pugh
Lecture notes in computer scienceTopology-Aware Routing in Structured Peer-to-Peer Overlay Networks
161 Citations2003Miguel Castro, Peter Druschel +2 more
Structured peer-to-peer overlay networks like CAN, Chord, Pastry and Tapestry provide a self-organizing substrate for large-scale p2p applications that implement a scalable, fault-tolerant distributed hash table (DHT), in which any item can be located within a small number of routing hops.
Replica Management in Data Grids
106 Citations2002L. P. Guy, Peter Kunszt +3 more
The architecture and design of a Replica Management System, called Reptor, is described within the context of the EU Data Grid project, and a prototype implementation is currently under development.
Incrementally improving lookup latency in distributed hash table systems
100 Citations2003Hui Zhang, Ashish Goel +1 more
A random sampling technique that incrementally improves lookup latency in DHT systems, and analytically proves that LPRS can result in lookup latencies proportional to the average unicast latency of the network, provided the underlying physical topology has a power-law latency expansion.
Replication and consistency
89 Citations1997Yuri Breitbart, Henry F. Korth
A new replica management protocol is defined for this model in which gIobaI serializability is ensured, while message overhead and deadlock frequency are less than in previously published work.
Performance and scalability of a replica location service
83 Citations2004Ann Chervenak, Naveen Palavalli +3 more
Data replication in Mariposa
77 Citations2002Jeff Sidell, Paul M. Aoki +4 more
It is shown how the replica control mechanism can be used to provide consistent, although potentially stale, views of data across many machines without expensive per-transaction synchronization.
Pegasus: Planning for Execution in Grids
58 Citations2002Ewa Deelman, James M. Blythe +2 more
Motivation Grid computing has made great progress in the last few years, but it is becoming increasingly necessary to develop higher level services which can automate the process and provide an adequate level of performance and reliability.
A decentralized, adaptive replica location mechanism
57 Citations2003Matei Ripeanu, Ian Foster
It is argued that a replica location mechanism that combines probabilistic representations of replica location information with soft-state protocols and a flat overlay network of nodes brings important benefits: genuine decentralization, low query latency, and flexibility to introduce adaptive communication schedules.
The Case for Non-transparent Replication: Examples from Bayou.
55 Citations1998Douglas B. Terry, Karin Anna Petersen +2 more
This paper looks at two Bayou applications, a calendar manager and a mail reader, and illustrates ways in which they utilize Bayou’s features to manage their data in an application-specific manner.
ACM SIGMETRICS Performance Evaluation ReviewIncrementally improving lookup latency in distributed hash table systems
19 Citations2003Hui Zhang, Ashish Goel +1 more
The next generation of DHT systems will enable scalable wide-area storage and retrieval of information, and will support the rapid recovery of information in the rapidly changing environment.
arXiv (Cornell University)Worldwide Fast File Replication on Grid Datafarm
15 Citations2003Osamu Tatebe, Satoshi Sekiguchi +3 more
This paper discusses and evaluates several techniques to support long-distance fast file replication using rate-controlled HighSpeed TCP with network striping.
USENIX SummerManagement of Replicated Volume Location Data in the Ficus Replicated File System.
7 Citations1991Thomas W. Page, Richard G. Guy +4 more
The Ficus mechanism permits optimistic management of the volume location data by exploiting the existing directory reconciliation algorithms which merge directory updates made during network partition.