Efficient peer-to-peer lookup based on a distributed trie

Michael Joseph Freedman, Radek Vingralek

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

Two main approaches have been taken for distributed keyvalue lookup operations in peer-to-peer systems: Broadcast searches [1, 2] and location-deterministic algorithms [5, 6, 7, 9]. We describe a third alternative based on a distributed trie. This algorithm functions well in a very dynamic, hostile environment, offering security benefits over prior proposals. Our approach takes advantage of working-set temporal locality and global key/value distribution skews due to content popularity. Peers gradually learn system state during lookups, receiving the sought values and/or internal information used by the trie. The distributed trie converges to an accurate network map over time. We describe several modes of information piggybacking, and conservative and liberal variants of the basic algorithm for adversarial settings. Simulations show efficient lookups and low failure rates.

Original languageEnglish (US)
Title of host publicationPeer-to-Peer Systems - 1st International Workshop, IPTPS 2002, Revised Papers
PublisherSpringer Verlag
Pages66-75
Number of pages10
Volume2429
ISBN (Print)3540441794, 9783540441793
StatePublished - Jan 1 2002
Externally publishedYes
Event1st International Workshop on Peer-to-Peer Systems, IPTPS 2002 - Cambridge, United States
Duration: Mar 7 2002Mar 8 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2429
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Workshop on Peer-to-Peer Systems, IPTPS 2002
CountryUnited States
CityCambridge
Period3/7/023/8/02

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient peer-to-peer lookup based on a distributed trie'. Together they form a unique fingerprint.

Cite this