ICS Theory Group

CompSci 269S, Fall 2006: Theory Seminar

Nov 17, 2006, in CS 253

High-Assurance Searching in Distributed Data Structures

Presented by Michael Nelson


We study the problem of supporting queries in overlay networks on a dynamic collection of networked hosts in which some fraction of the hosts may be malicious. We present novel hashing schemes that can be employed to limit the ability of adversarial nodes to carry out attacks. When used in conjunction with previous work, our scheme yields a distributed hash table that behaves near-optimally in the absence of malicious nodes and efficiently in the presence of malicious nodes. This talk is based on the joint work of Michael T. Goodrich, Michael J. Nelson, Jonathan Z. Sun, Roberto Tamassia, and Nikos Triandopoulos.