Halo: High-Assurance Locate for Distributed Hash Tables

Apu Kapadia, Nikos Triandopoulos

Research output: Contribution to conferencePaperpeer-review

26 Scopus citations

Abstract

We study the problem of reliably searching for resources in untrusted peer-to-peer networks, where a significant portion of the participating network nodes may act maliciously to subvert the search process. We present a new method called Halo for performing redundant searches over a distributed hash table (DHT) structure to achieve high integrity and availability levels without affecting the storage and communication complexities of the underlying DHT. Other schemes for redundant searches have proposed new or modified DHTs with increased storage requirements at nodes, requiring modifications at all nodes in the network. In contrast, Halo aims to serve as a middleware component, making “black-box” calls of the underlying primitive search operation to eventually provide a new composite search operation of higher assurance. We apply this concept to the popular and well-studied DHT Chord, and demonstrate the efficiency and security of our approach though analytical modeling and simulation-based analysis. For example, we show that for 12% malicious nodes in the network, a regular Chord operation fails 50-60% of the time. In contrast, Halo reduces this failure rate to 1%. We show how our scheme lends itself to a recursive version that can tolerate 22% malicious nodes with the same level of success, while regular Chord fails 70-80% of the time.

Original languageEnglish
StatePublished - 2008
Event15th Symposium on Network and Distributed System Security, NDSS 2008 - San Diego, United States
Duration: 10 Feb 200813 Feb 2008

Conference

Conference15th Symposium on Network and Distributed System Security, NDSS 2008
Country/TerritoryUnited States
CitySan Diego
Period10/02/0813/02/08

Fingerprint

Dive into the research topics of 'Halo: High-Assurance Locate for Distributed Hash Tables'. Together they form a unique fingerprint.

Cite this