Pastry swMATH ID: 11775 Software Authors: Rowstron, Antony; Druschel, Peter Description: Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. This paper presents the design and evaluation of Pastry, a scalable, distributed object location and routing substrate for wide-area peer-to-peer applications. Pastry performs application-level routing and object location in a potentially very large overlay network of nodes connected via the Internet. It can be used to support a variety of peer-to-peer applications, including global data storage, data sharing, group communication and naming. par Each node in the Pastry network has a unique identifier (nodeId). When presented with a message and a key, a Pastry node efficiently routes the message to the node with a nodeId that is numerically closest to the key, among all currently live Pastry nodes. Each Pastry node keeps track of its immediate neighbors in the nodeId space, and notifies applications of new node arrivals, node failures and recoveries. Pastry takes into account network locality; it seeks to minimize the distance messages travel, according to a to scalar proximity metric like the number of IP routing hops. par Pastry is completely decentralized, scalable, and self-organizing; it automatically adapts to the arrival, departure and failure of nodes. Experimental results obtained with a prototype implementation on an emulated network of up to 100,000 nodes confirm Pastry’s scalability and efficiency, its ability to self-organize and adapt to node failures, and its good network locality properties. Homepage: http://research.microsoft.com/en-us/um/people/antr/past/pastry.pdf Related Software: Chord; SCRIBE; BATON; PeerSim; PlanetLab; UNITY; Globus Toolkit; SPLAY; PATRICIA; Bigtable; Squid; TAG; Dynamo; Vivaldi; Linda; BOINC; FRAUDAR; SpEagle; Coq; TLA Cited in: 65 Publications all top 5 Cited by 159 Authors 6 Scheideler, Christian 3 Druschel, Peter 3 Kniesburges, Sebastian 3 Robinson, Peter 3 Rowstron, Antony I. T. 2 Castro, Miguel A. 2 Garcia-Molina, Hector 2 Herlihy, Maurice P. 2 Karger, David R. 2 Kermarrec, Anne-Marie 2 Koutsopoulos, Andreas 2 Kutten, Shay 2 Li, Dongsheng 2 Li, Xiaozhou 2 Lu, Xicheng 2 Misra, Jayadev 2 Nesterenko, Mikhail V. 2 Pandurangan, Gopal 2 Peleg, David 2 Plaxton, C. Greg 2 Saia, Jared 2 Schmid, Stefan 2 Trehan, Amitabh 2 Wattenhofer, Roger P. 2 Young, Maxwell 2 Zhang, Yiming 1 Albano, Matthew 1 Baker, Mary 1 Balakrishnan, Hari 1 Balazinska, Magdalena 1 Baldoni, Roberto 1 Baraglia, Ranieri 1 Bawa, Mayank 1 Birman, Kenneth P. 1 Bonomi, Silvia 1 Brocco, Amos 1 Busch, Costas 1 Cai, Xing Shi 1 Campo, Marcelo R. 1 Casalicchio, Emiliano 1 Chen, Jinbo 1 Chen, Yan 1 Chiola, Giovanni 1 Chuang, John C.-I. 1 Clouser, Thomas 1 Coelho, Fábio 1 Cordasco, Gennaro 1 Cortese, Giovanni 1 Costa, Fábio M. 1 Cuenca-Acuna, Francisco Matias 1 Da Silva E. Silva, Francisco José 1 Daswani, Neil 1 Davide, Fabrizio 1 de Camargo, Raphael Yokoingawa 1 Delporte-Gallet, Carole 1 Devroye, Luc P. J. A. 1 Dolev, Shlomi 1 Fauconnier, Hugues 1 Ferreira, Ronaldo A. 1 Filho, Fernando Castor 1 Finger, Marcelo 1 Fraigniaud, Pierre 1 Frank, Martin 1 Garcia-Haro, Joan 1 García-López, Pedro 1 Gargano, Luisa 1 Gauron, Philippe 1 Ghose, Abhishek 1 Gilbert, Seth 1 Gionis, Aristides 1 Goldman, Alfredo 1 Gotthelf, Pablo 1 Grossklags, Jens 1 Guerraoui, Rachid 1 Gupta, Diksha 1 Hammar, Mikael 1 Hirsbrunner, Béat 1 Hu, Y. Charlie 1 Jagannathan, Suresh 1 Joseph, Sam 1 Joung, Yuh-Jzer 1 Kapelko, Rafał 1 Kat, Ronen I. 1 Katz, Randy Howard 1 Keidar, Idit 1 Keren, Daniel 1 King, Valerie 1 Knollmann, Till 1 Kon, Fabio 1 Kubiatowicz, John D. 1 Kuhn, Fabian 1 Lewis, Scott J. 1 Li, Jianhua 1 Li, Ruixuan 1 Lu, Zhengding 1 Machado, Nuno 1 Maia, Francisco 1 Malgosa-Sanahuja, Josemaria 1 Maniatis, Petros 1 Manzanares-Lopez, P. ...and 59 more Authors all top 5 Cited in 19 Serials 8 Journal of Parallel and Distributed Computing 6 Theoretical Computer Science 6 Distributed Computing 4 Algorithmica 2 Journal of Computer and System Sciences 2 Information and Computation 2 Theory of Computing Systems 2 1 Computing 1 Information Sciences 1 Acta Mathematicae Applicatae Sinica. English Series 1 Mathematical and Computer Modelling 1 Wuhan University Journal of Natural Sciences (WUJNS) 1 Internet Mathematics 1 Science in China. Series F 1 International Journal of Parallel, Emergent and Distributed Systems 1 Journal of Shanghai Jiaotong University (Science) 1 Science China. Information Sciences 1 ACM Transactions on Algorithms Cited in 5 Fields 64 Computer science (68-XX) 5 Combinatorics (05-XX) 3 Operations research, mathematical programming (90-XX) 1 Statistics (62-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year