A serverless 3D world

ABSTRACT

Online multi-participant virtual-world systems have attracted significant interest from the Internet community but are hindered by their inability to efficiently support interactivity for a large number of participants. Current solutions divide a large virtual-world into a few mutually exclusive zones, with each zone controlled by a different server, and/or limit the number of participants per server or per virtual-world. Peer-to-Peer (P2P) systems are known to provide excellent scalability in a networked environment (one peer is introduced to the system by each participant), however current P2P applications can only provide file sharing and other forms of relatively simple data communications. In this paper, we present a generic 3D virtual-world application that runs on a P2P network with no central administration or server. Two issues are addressed by this paper to enable such a spatial application on a P2P network. First, we demonstrate how to index and query a 3D space on a dynamic distributed network. Second, we show how to build such a complex application from the ground level of a P2P routing algorithm. Our work leads to new directions for the development of online virtual-worlds that we believe can be used for many government, industry, and public domain applications.

REFERENCES

• 1: K. Aberer and M. Punceva. Efficient search in structured peer-to-peer systems: Binary v.s. k-ary unbalanced tree structures. In Proceedings of the International Workshop on Databases, Information Systems, and Peer-to-Peer Computing (held in conjunction with VLDB), Berlin, Germany, September 2003.
• 2: Accurate Estimation of the Cost of Spatial Selections, Proceedings of the 16th International Conference on Data Engineering, p.123, February 28-March 03, 2000
• 3: Artur Andrzejak , Zhichen Xu, Scalable, Efficient Range Queries for Grid Information Services, Proceedings of the Second International Conference on Peer-to-Peer Computing, p.33, September 05-07, 2002
• 4: S. Bhattacharjee, P. Keleher, and B. Silaghi. The design of TerraDir. Technical Report CS-TR-4299, Department of Computer Science, University of Maryland at College Park, October 2001.
• 5: Min Cai , Martin Frank , Jinbo Chen , Pedro Szekely, MAAN: A Multi-Attribute Addressable Network for Grid Information Services, Proceedings of the Fourth International Workshop on Grid Computing, p.184, November 17-17, 2003
• 6: David Clark, Face-to-Face with Peer-to-Peer Networking, Computer, v.34 n.1, p.18-21, January 2001 [doi>10.1109/2.970548]
• 7: A. Daskos, S. Ghandeharizadeh, and X. An. PePeR: A distributed range addressing space for P2P systems. In Proceedings of the International Workshop on Databases, Information Systems, and Peer-to-Peer Computing (held in conjunction with VLDB), pages 200--218, Berlin, Germany, September 2003.
• 8: Murat Demirbas , Hakan Ferhatosmanoglu, Peer-to-Peer Spatial Queries in Sensor Networks, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.32, September 01-03, 2003
• 9: Peter Druschel , Antony Rowstron, PAST: A Large-Scale, Persistent Peer-to-Peer Storage Utility, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.75, May 20-22, 2001
• 10: P. Ganesan, M. Bawa, and H. Garcia-Molina. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Proceedings of the VLDB, Toronto, Canada, August 2004.
• 11: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 12: Gershon Kedem, The quad-CIF tree: A data structure for hierarchical on-line algorithms, Proceedings of the 19th conference on Design automation, p.352-357, January 1982
• 13: A. Kothari , D. Agrawal , A. Gupta , S. Suri, Range Addressable Network: A P2P Cache Architecture for Data Ranges, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.14, September 01-03, 2003
• 14: Witold Litwin , Tore Risch, LH*G: A High-Availability Scalable Distributed Data Structure By Record Grouping, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.923-927, July 2002 [doi>10.1109/TKDE.2002.1019223]
• 15: A. Mondal, Yilifu, and M. Kitsuregawa. P2PR-tree: An R-tree-based spatial index for peer-to-peer environments. In Proceedings of the International Workshop on Peer-to-Peer Computing and Databases (held in conjunction with EDBT), Heraklion, Greece, March 2004.
• 16: C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32(3):241--280, May 1999.
• 17: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 18: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 19: Kenneth C. Sevcik , Nick Koudas, Filter Trees for Managing Spatial Data over a Range of Size Granularities, Proceedings of the 22th International Conference on Very Large Data Bases, p.16-27, September 03-06, 1996
• 20: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, 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, p.149-160, August 2001, San Diego, California, United States
• 21: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Management

Keywords:
distributed hash tables, peer-to-peer systems, spatial data, virtual-worlds