Nov 16, 2006: Efficiency and Security Issues for Distributed Data Structures
Filed in: Edison
Series
Dr. Michael Goodrich, University of California at
Irvine
This talk highlights our recent work on the efficiency and security of distributed peer-to-peer data structures, including distributed hash tables (DHTs), rainbow skip graphs, and skip webs. These structures share a common theme in that they assume that data is distributed throughout a peer-to-peer network, for which we wish to build an indexing scheme so that we can locate items of interest quickly, as well as efficiently insert and delete items from the search structure. These structures differ in how they perform this indexing, with DHTs supporting only exact-match queries, rainbow skip graphs supporting one-dimensional range queries, and skip webs supporting multi-dimensional searches. Their efficiency depends on how well they distribute search keys and how well they avoid congestion among concurrent searches. Their security derives from how well they tolerate node losses and/or malicious responses.
Prof. Goodrich received his B.A. in Mathematics and Computer Science from Calvin College in 1983 and his PhD in Computer Sciences from Purdue University in 1987. He served as a professor of computer science at Johns Hopkins University from 1987-2001, at which time he joined the faculty at UC-Irvine. He has also served on the faculties of Univ. of Illinois and Brown University during sabbatical visits.
Dr. Goodrich's research is directed at the design of high performance algorithms and data structures for solving large-scale problems motivated from information assurance and security, the Internet, information visualization, and geometric computing. He has pioneered and led research on efficient parallel and distributed solutions to a number of fundamental problems, including sorting, convex hull construction, segment intersection reporting, fixed-dimensional linear programming, polygon triangulation, Voronoi diagram construction, and data authentication.
With nearly 200 publications, including several widely-adopted books, his recent work includes contributions to efficient and secure distributed data structures, authenticated geometric searching, IP traceback, and network/grid security. He is a Compere Loveless Fellow and a member of the Fulbright Senior Specialist Roster, the Sigma Xi Scientific Research Honor Society, and the editorial boards of several top journals on algorithms. He is a recipient of the NSF Research Initiation Award, the DARPA Spirit of Technology Transfer Award, the Brown Univ. Award for Technological Innovation, the ACM Recognition of Service Award, and the Pond Award for Excellence in Undergraduate Teaching.
Abstract
This talk highlights our recent work on the efficiency and security of distributed peer-to-peer data structures, including distributed hash tables (DHTs), rainbow skip graphs, and skip webs. These structures share a common theme in that they assume that data is distributed throughout a peer-to-peer network, for which we wish to build an indexing scheme so that we can locate items of interest quickly, as well as efficiently insert and delete items from the search structure. These structures differ in how they perform this indexing, with DHTs supporting only exact-match queries, rainbow skip graphs supporting one-dimensional range queries, and skip webs supporting multi-dimensional searches. Their efficiency depends on how well they distribute search keys and how well they avoid congestion among concurrent searches. Their security derives from how well they tolerate node losses and/or malicious responses.
Bio
Prof. Goodrich received his B.A. in Mathematics and Computer Science from Calvin College in 1983 and his PhD in Computer Sciences from Purdue University in 1987. He served as a professor of computer science at Johns Hopkins University from 1987-2001, at which time he joined the faculty at UC-Irvine. He has also served on the faculties of Univ. of Illinois and Brown University during sabbatical visits.
Dr. Goodrich's research is directed at the design of high performance algorithms and data structures for solving large-scale problems motivated from information assurance and security, the Internet, information visualization, and geometric computing. He has pioneered and led research on efficient parallel and distributed solutions to a number of fundamental problems, including sorting, convex hull construction, segment intersection reporting, fixed-dimensional linear programming, polygon triangulation, Voronoi diagram construction, and data authentication.
With nearly 200 publications, including several widely-adopted books, his recent work includes contributions to efficient and secure distributed data structures, authenticated geometric searching, IP traceback, and network/grid security. He is a Compere Loveless Fellow and a member of the Fulbright Senior Specialist Roster, the Sigma Xi Scientific Research Honor Society, and the editorial boards of several top journals on algorithms. He is a recipient of the NSF Research Initiation Award, the DARPA Spirit of Technology Transfer Award, the Brown Univ. Award for Technological Innovation, the ACM Recognition of Service Award, and the Pond Award for Excellence in Undergraduate Teaching.