NC State University

Department of Computer Science Colloquia 2001-2002

A telecast from Duke as part of
Triangle Computer Science Distinguished Lecturer Series

Date:   Monday, March 18, 2002
Time:   4:00 PM (talk telecast)
Place:   Parks Shop, Studio 1, NCSU Historical Campus (click for courtesy parking request)

Speaker:  Richard Karp , Computer Science Division, University of California, Berkeley

Accessing Data In Peer-to-Peer Networks and Other Large Distributed Networks

Abstract:   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.

Short Bio:   Richard Karp received the Ph.D. in Applied Mathematics from Harvard University in 1959. From 1959 to 1968 he was a member of the Mathematics 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. In 1999 he returned to ICSI and Berkeley, where he is a University Professor with appointments in Computer Science, Mathematics and Bioengineering. His current research activities center around algorithmic methods in genomics and computer networking.

Professor 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.

Host:   Pankaj Agarwal , Computer Science, Duke U.

Colloquia Home Page.