TY - GEN
T1 - Efficient peer-to-peer lookup based on a distributed trie
AU - Freedman, Michael J.
AU - Vingralek, Radek
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33749500090&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749500090&partnerID=8YFLogxK
U2 - 10.1007/3-540-45748-8_6
DO - 10.1007/3-540-45748-8_6
M3 - Conference contribution
AN - SCOPUS:33749500090
SN - 3540441794
SN - 9783540441793
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 66
EP - 75
BT - Peer-to-Peer Systems - 1st International Workshop, IPTPS 2002, Revised Papers
A2 - Druschel, Peter
A2 - Kaashoek, Frans
A2 - Rowstron, Antony
PB - Springer Verlag
T2 - 1st International Workshop on Peer-to-Peer Systems, IPTPS 2002
Y2 - 7 March 2002 through 8 March 2002
ER -