Thu Oct 19, 2006, 4:15-5:15pm, 3400 Boelter Hall

Efficiency and Security Issues for Distributed Data Structures

Michael Goodrich
UC 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.

About the speaker:
Prof. 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 is also interested in computer 
science education. Prof. Goodrich has served on the program committee 
for several respected conferences in computational geometry and theoretical 
computer science, including acting as chair for 26th ACM Symp. on Theory 
of Computing (STOC).  He is an associate editor for International Journal
of Computational Geometry & Applications, Journal of Computer and System 
Sciences, and Journal of Graph Algorithms and Applications. He has been 
awarded several awards for excellence in teaching.

Host: Jens Palsberg.