Looking Up Data in P2P Systems

Balakrishnan, Kaashoek, Karger, Morris, Stoica

distributed hashtable dht p2p

@article{balakrishnan:cacm-2003,
  title={Looking Up Data in {P2P} Systems},
  author={Balakrishnan, H. and Kaashoek, M.F. and Karger, D. and
          Morris, R. and Stoica, I.},
  journal={Communications of the {ACM}},
  volume={46},
  number={2},
  pages={43--48},
  year={2003},
  publisher={ACM}
}

Looking Up Data in P2P Systems. Balakrishnan, Kaashoek, Karger, Morris, Stoica.

• Centralization is bad in most case---single point of failure, can't cope with high load, wasted resources under light load, singe attack point.
• Broadcasting out requests will also never scale.
• Manually constructing hierarchy requires infrastructure, some nodes take more load, require more management, failure at higher levels can be catastrophic.
• Key issues for DHTS are mapping keys to nodes in a load-balanced way; forwarding a lookup for a key to an appropriate node; building routing tables.
• Guaranteeing that data which is on the network will be found is critical.
• The hashtable interface presents a simple, common viewpoint upon which many applications may be built.
• Summarizes the major DHT work up to that point, identifies areas for future work.
  • CAN: d-dimensional space, broken up into zones managed by nodes. Keys map into coordinate space, requests greedily forwarded toward containing zone.
  • Chord: Ring of virtual identifiers, forwarding along ring, finger tables maintained that boost performance logarithmically, but are not necessary.
  • Pastry: Virtual ring, sounds somewhat similar to Chord.
  • Tapestry: Again similar, but focuses on trying to optimize network travel.
  • Future work: Handle frequent node joins and departures; fault tolerance; proximity routing; handling malicious nodes; richer search/keys.