Data Access in Peer-to-Peer Distributed Networks

Richard M. Karp
ICSI Center for Internet Research and
University of California, Berkeley

Peer-to-peer networks such as Napster and Gnutella are examples of distributed systems in which very large numbers of computers store and exchange data. We discuss the design of a distributed algorithm which enables any computer in the system to determine the location of any given data object. The algorithm must work even in the presence of computer failures and the frequent arrivals and departures of computers from the system. It uses a distributed hash table which stores (key, value) pairs, where the value is the IP address of a data object, and the key is the address of the object in a virtual address space. There is a dynamic assignment of processors to different regions of the address space, and each processor maintains the data that hashes to its region. Each processor has a pointer to only a small number of neighbors in the address space, and yet it must be possible to navigate rapidly to the processor responsible for any given point in the address space. The algorithm enjoys the following properties:

1. The number of pointers that are followed in reaching any virtual address is , where is the number of processors in the system.
2. The number of pointers maintained by each node is . There is a variation of the design in which this number is reduced to , at the cost of doubling the time for data access.
3. The pointer structure is symmetric: i.e., if A points to B then B points to A. This symmetry implies that it is easy for a processor to identify the processors that point to it and notify them of changes in its status. Thus, the system can reconfigure itself rapidly when a processor departs.
4. Processors are not assigned to fixed parts of the virtual address space; the ability to reassign a processor to a different region facilitates reconfiguration and load balancing.
5. When links between processors fail or pointer updates are delayed, the system will continue to function, although its operation may be slowed.

This is joint work with A.P. Anantharaman, Karthik Lakshminarayan, Sylvia Ratnasamy, Ion Stoica and Sonesh Surana.

About the speaker:

Richard Karp received the Ph.D. in Applied Mathematics from Harvard University in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center. From 1968 to 1994 he was a Professor at the University of California, Berkeley, where he held the Class of 1939 Chair. From 1988 to 1995 he was a Research Scientist at the International Computer Science Institute (ICSI) in Berkeley. From 1995 to 1999 he was a Professor of Computer Science and Adjunct Professor of Molecular Biotechnology at the University of Washington. In 1999 he returned to ICSI and Berkeley, where he is a University Professor with appointments in Computer Science, Mathematics and Bioengineering.

The unifying theme in Karp's work has been the study of combinatorial algorithms. His 1972 paper ``Reducibility Among Combinatorial Problems'' showed that many of the most commonly studied combinatorial problems are NP-complete, and hence likely to be intractable. Much of his subsequent work has concerned parallel algorithms, the probabilistic analysis of combinatorial optimization algorithms and he construction of randomized algorithms for combinatorial problems. His current activities center around algorithmic methods in genomics and computer networking.

Karp has received the National Medal of Science, the Turing Award (ACM) the Fulkerson Prize(AMS and Math. Programming Society), the von Neumann Theory Prize(ORSA-TIMS), the Lanchester Prize (ORSA) the von Neumann Lectureship (SIAM), the Harvey Prize (Technion), the Centennial Medal (Harvard) and the Distinguished Teaching Award (Berkeley). He is a member of the National Academy of Sciences, the National Academy of Engineering and the American Philosophical Society and a Fellow of the American Academy of Arts and Sciences and the American Association for the Advancement of Science. He has been awarded five honorary degrees.

Contact information:

Richard Karp
ICSI Center for Internet Research and
University of California, Berkeley

karp@ICSI.Berkeley.EDU

/