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

Michael J. Freedman, Radek Vingralek

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

12 Scopus citations


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
EditorsPeter Druschel, Frans Kaashoek, Antony Rowstron
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540441794, 9783540441793
StatePublished - 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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other1st International Workshop on Peer-to-Peer Systems, IPTPS 2002
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this