A shared virtual world is a computer-generated space used as a metaphor for interactions. It should ensure :
To our knowledge, no system ensures both specifications.
Entities, driven by users or by computer, enter and leave the world, move from one virtual place to another and interact in real-time.
The virtual world is the surface of a torus. A position (x,y) is represented by a couple of 128 bits. Thus, the virtual world contains approximately 10^75 positions. An entity is responsible of its position on the torus.
The entities communicate through unreliable asynchronous links. We say that two entities are connected when they are able to exchange messages. It means a mutual knowledge of their fundamental characteristics (identifier, position, network address...).
| Table of contents [hide] |
The set of entities and the set of links between them form a communication graph which models Solipsis. We restrict the allowed global properties of this graph to two specifications: The Local Awareness and the Global Connectivity.
We define the Awareness Area of an entity e as the disk of radius r(e) centered on e. The awareness area of e corresponds to the immediate virtual surroundings of e. The radius r(e) is variable. It depends on the density of entities around e and the physical capacities of e.
→ The Local Awareness property is ensured when each entity is connected with all entities in its awareness area.
It is important to note that e may know some entities outside its awareness area, but this property indicates that e must be connected with all entities inside.
If the graph is disconnected, some entities may never be able to meet each other. Moreover, a world partitioning may cause local incoherences. So, it is important that the communication graph remains connected.
→ The Global Connectivity is ensured when the communication graph is connected, that is when there exists a path between any pair of entities within the graph.
The scalability issue requires us to rely on local behaviors and entity collaboration in order to achieve such challenging goals. We define two local algorithms which guarantees that a graph respecting the properties will still respect them after a virtual event (entity motion, entity disappearing, entity arrival).
A spontaneous collaboration scheme aims to help neighbors to respect the Local Awareness property. An entity acting as described in this first algorithm does expect that its neighbors acts as well.
The principle is simple :
→ an entity e alerts its neighbor p when another neighbor q enters in the awareness area of p.
Moreover, as an entity cares more about entities that are near to enter in its awareness Area or move in its direction, we enlarge the rule :
→ an entity e alerts its neighbor p when another neighbor q is now closer to p than e itself.
Note that this alert could be given in several cases: p moves closer to q, q moves closer to p, e moves away from p, the awareness radius of p grows up and q appear suddenly.
In order to ensure the Local Awareness property, an entity can only rely on its adjacents. If it does not know any entity in some large sector, it will hardly know about an entity arriving from this sector. Conversely, if it moves forward a sector with no known entity, it will hardly get aware of entities it should meet on its path.
Based on Computational Geometry notions, the second local algorithm aims that an entity will not “turn its back” to a portion of the world.
The convex of a set of entities is known as the smallest convex polygon containing all entities of this set. Naturally, the convex hull of a set of entities encloses a set of 'positions in the virtual world.
→ In order to not "turn its back" to a part of the world, an entity should always be inside the convex hull of its neighbors.
This property reduces the risk of graph disconnection by avoiding isolation of a set of entities. Moreover, it forces entities to have, at least, three adjacents, so at least two failures or departures are tolerated. Finally, it impacts on topology of the Solipsis network that looks like a mesh.
At any time, the motion of an entity or a brutal crash may put an entity to not respect this local rule. Then, it should find a (some) new entity(ies) such that the convex hull of its alive neighbors added to this(ese) new entity(ies) contains itself. It is realized thanks to an iterative process using a list of neighbors which is sorted in a couterclockwise order around the entity.
Let e be the entity not respecting the rule. Among its neighbors, e knows two consecutive entities p and q such that the angle (p,e,q) is greater than 180°. It should actually find an entity within this empty sector. When e detects that it is not respecting the rule, it immediately sends a message to p and q. For simplicity, we consider now the case of entity p, the other case being symetrically similar.
If p respects the rule (and it is assumed it does), it is sure that it knows an entity in the half-plane delimited by the line (p,e). We note this entity p'. It is also sure that the angle (p',e,q) is strictly less than (p,e,q), but it may be not enough to respect back the rule. Fortunately, it is sure an iterative process will eventually succeed in detecting a set of entities such that e is contained in the convex hull of its neighbors.