paper

Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems

  • Authors:
Read the paper

📜 Abstract

This paper presents Pastry, a scalable, distributed object location and routing substrate for wide-area peer-to-peer applications. Pastry is completely decentralized, scalable, and fault-tolerant and does not require any global coordinate information such as a GPS. Nodes in a Pastry network form a self-organizing overlay network where each node is assigned a unique identifier from a circular namespace. For an N-node Pastry network, the average number of routing hops is log16 N. The number of entries in the routing table per node is also log16 N. Faults can be handled using simple extensions to the basic routing scheme. Pastry is not tied to any particular application, but it can serve as a generic substrate for wide-area distributed applications such as global-scale file systems, databases, web caches, and name services.

✨ Summary

This paper presents ‘Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems,’ a middleware designed for wide-area peer-to-peer applications. Published in November 2001 at Middleware 2001, the paper is authored by Antony Rowstron and Peter Druschel. Pastry is a peer-to-peer routing infrastructure that enables decentralized and scalable object location and routing without relying on global positioning or coordination.

The impact on further research has been substantial, as Pastry served as a foundational component for various large-scale distributed systems and peer-to-peer networks. It has been extensively cited in the development of distributed hash tables (DHTs) and has influenced subsequent systems like Azureus, FreePastry, and the Bamboo DHT.

  • Stoica, I., Morris, R., Karger, D., Kaashoek, M. F.,  Dabek, F.,   “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications,” Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, https://dl.acm.org/doi/10.1145/383059.383071.

  • Dabek, F.,  Cox, R.,  Kaashoek, M. F.,  Morris, R., “Vivaldi: A Decentralized Network Coordinate System,” Proceedings of the 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, https://dl.acm.org/doi/10.1145/1015467.1015480.

  • Rowstron, A.,  Druschel, P., “Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility,” ACM SIGOPS Operating Systems Review, https://dl.acm.org/doi/10.1145/844128.844140.

The research and strategies discussed in the Pastry paper contributed to the advancement of peer-to-peer systems, impacting numerous areas in both academia and industry.