Algorithms for a decentralised, multi-user 3D world

Nicholas Chapman, March 2004


This thesis sets out a design for a distributed, decentralised, multi-user 3D world. The design offers strong availability and persistence guarantees for objects placed in the world, as well as a means of locating objects and other participants. This is achieved through the use of Pastry, a ‘distributed hash table’. Despite the use of replication to achieve persistence and availability, the design provides a strong consistency model, combining sequential consistency for writes with optimistic local reads for low latency. It also introduces a novel voxel approach for taking advantage of virtual-space locality when deciding where to place objects in the Pastry network. In short, this project has involved designing and implementing the foundation for a fully decentralised, multi-user 3D world with practically unlimited scalability, and strong availability and consistency guarantees.

Download: Chapman04.pdf (400KB)

: Main

: Projekts

: Code

: Articles

: Links