[Solipsis-tech] Re: [Solipsis] some questions about Solipsis (from Taiwan)

[Shun-Yun H. <sy...@ya...>]

Hello Gwendal,

Thanks for the reply.

Yes, it's true I left out the details of how to construct Voronoi, which I
probably should mention somewhat. Sorry about it and thanks for reminding
me. :) The reason is that Voronoi is something that has been studied quite
extensively since early 20th century, and there are numerous papers on its
construction & maintance.

To answer you briefly, the construction of Voronoi is basically done by
having the coordinates of a set of points (preferably those within your
AOI), then apply the algorithm (which we currently use Fortune's sweepline
algorithm. ref [1], but there are others. The general complexity for
constructing a Voronoi is O(log n). For maintainance, currently it's done by
a complete re-construction (so again, O(log n)), however, there are more
optimized algorithms that exist that could update a Voronoi dynamically
ref[2], and takes O(n).

So basically, right now for all join/move/leave, a node simply destory and
re-constructs its Voronoi, and is done in O(log n).

Once the Voronoi is constructed and put into some nice data structure,
further queries (such as who is a neighbor of who), can be done rather
efficiently in mostly a look-up fashion. I think the overlap check is done
in O(n).

However, from my perspective, the number of nodes that each computer needs
to maintain should be low (less than 50 for a very crowded session). So
algorithmatic complexity should not be the performance bottle-neck as these
calculations can be done fairly quickly. I'm more worry about the amount of
message exchange that's required for maintaining Local Awareness and Global
Connectivity. If you're interested in the details of Voronoi, I'd recommend
ref [3] and ref [4], which gives out fairly comprehesive treatement.

For GC maintainace, now I think there are two conceputally separate
situations that should be discussed, which we probably should give different
names to it. One is whether all nodes are connected to each other. (i.e. the
connectivity of the 'graph' as you mentioned), the other is whether the
connections made include your neighbors correctly (i.e. whether the Local
Awareness property is maintained correctly). I think it's worth making
distinctions between them, because it's possible to have a fully-connected
graph while each node does not necessarily maintain Local Awareness
properly. However, whether the full connectivity will ensure later recovery
for local awareness property, is something that should be include in the
discussion for any P2P architecture.

em.. just somet new thoughts.. :)

about the worse-case diagram in your Ph.D thesis, I'm not sure if I
understand it correctly. does the diagram indicate that there are nodes that
should be connected but are in fact not? (for example, entity ef is not
connected/discovered by e). and is it because the entity-query/discovery
process would stop before discovering ef?

Cheers,

Shun-Yun


Reference.
[1] FORTUNE, S. 1987. A sweepline algorithm for Voronoi diagrams
[2] GOWDA, I. G., KIRKPATRICK, D. G., LEE, D. T., AND NAAMAD, A. 1983.
Dynamic Voronoi diagrams. IEEE Trans. Infi Theory IT-29, 724-731.
[3] Aurenhammer, Franz. 1991.  Voronoi diagrams-a survey of a fundamental
geometric data structure. ACM Computing Survey Vol. 23. No. 3. p345 - 405
[4] GUIBAS, L. J., AND STOLFI, J. 1985. Primitives for the manipulation of
general subdivisions and the computation of Voronoi diagrams. ACM Trans.
Graph. 4, 74-123.



----- Original Message ----- 
From: "SIMON Gwendal FTRD/DMI/ISS" <gwe...@rd...>
To: <sy...@ya...>
Cc: <sol...@li...>
Sent: Friday, June 11, 2004 12:25 AM
Subject: RE : [Solipsis] some questions about Solipsis (from Taiwan)


Hi,

[I include the solipsis list in this discussion]

Both projects (yours and Solipsis) relies on the same concept:
1- each entity is connected with all entities located within its Area Of
Interest (AOI)
2- each entity MAY be connected with some farther entities in order to
ensure Global Connectivity (GC). These far neighbors are chosen thanks to a
gemoetric rule (Voronoi for your project, an original and peculiar rule for
Solipsis)

Please find in the following some answers to your questions :

Q2 : the entities execute a "mutual neighbor discovery" algorithm every time
one of their neighbors move. Note that the AOI is not fixed. The number of
neighbors within the SOI is in a small range (typically a fixed value k +/-
20%).

Q3: we have to consider two proofs :
* are entities connected with all entities within AOI ? The answer is NO.
You may find an illustration of the identified worst case in the draft of my
PhD report (http://gwendal.simon.free.fr/Data/part1.pdf Figure 1.7 - page
17). Unfortunately, this report is written in french (due to a french law)
* does our rule ensure connectivity of the graph ? The answer is YES, if the
world is a torus and if the convex hull of the set of all entities is the
torus itself.

Q4: in current implementation, an entity stops the lookup of entity as soon
as it discovers another entity providing back the rule respect. It is
possible to optimize this algorithm in order to stop later.

I have now some questions about your paper. You don't give much details
about the construction and the maintaining of the Voronoi Diagram. What is
the algorithmic complexity of Voronoi re-building (when joining, when
moving, when leaving) ? What is the complexity of the "overlap-check"
algorithm (Voronoi regions overlapping AOI) ?

Best,

-- Gwendal


-----Message d'origine-----
De : Shun-Yun Hu [mailto:sy...@ya...]
Envoyé : mercredi 9 juin 2004 02:16
À : KELLER Joaquin FTRD/DMI/ISS
Objet : Re: [Solipsis] some questions about Solipsis (from Taiwan)


Hi Joaquin,

Thanks for the prompt reply. I've attached a current working draft of the
paper to this e-mail.
It's still not camera-ready yet (due next monday), as I need to reduce it to
5 pages, and I'm planning to include a section of analysis on Solipsis :) (I
wasn't aware of Solipsis when I first submited)

If you've any questions/comments/feedback, please do let me know, I'd very
appreciate.

some additional questions, if you don't mind:

Q2. It's as I suspected, because checking seems to be necessary for those
outside of SOI as well. I'm wondering about the frequency of the check. Does
it happen every time someone in my SOI moves? or does it happen only between
a certain interval. (this has performance/consistency impact on the design)

Q3. What is the case where it might not work? would you mind to let me know
the special circumstance? If it's difficult to prove GC maintaince via
mathmatical analysis, maybe simulation is the way. :)  We're also currently
doing simulations only, as I can't think of a good way to analyze/prove
topology maintaince. Have you any simulation results yet for Solipsis? (as
in having 1000+ entities simulation)

Q4. I guess my question is, will the P2P topology be maintained in a
deterministic way, or will hosts actually be able to connected in various
ways due to chance circumstance. For example, when trying to maintain GC,
you might start searching for a host to connect in the 180 degree "missing
range". However, it certainly appears that it's possible for more than one
host to "quality" as the node to connect to (for example, you could connect
to the 1st host that satisifis the requirement, or the "best" host, define
as that could reduce the "missing range angel" the most).

I've asked my friend (whose name is Peter) about collaboration, and I think
both him and I are interested.. :) although personally I'm not that into
language localization stuff.. :) I do hope for some form of collaboration,
if possible, because to my amazement when I first saw your paper, I think
both of us have the same ultimate goal, which is to realize some WWW-like
virtual environment, pervasive and usable for all people. :) We even have
the same literary reference in our paper (e.g. Matrix & Snow Crash), and
this was before I read about your paper..

Cheers,

Shun-Yun


----- Original Message ----- 
From: KELLER Joaquin FTRD/DMI/ISS
To: Shun-Yun Hu ; SIMON Gwendal FTRD/DMI/ISS
Cc: sol...@li...
Sent: Wednesday, June 09, 2004 1:01 AM
Subject: RE : [Solipsis] some questions about Solipsis (from Taiwan)


Hi Shun-Yun,
I am happy to know there is a solipsis-like project elsewhere in the planet
:-) Sure I want to get your netgames 2004 paper ! Your questions:
Q1: A list of nodes, at least some nodes should be alive. To get that list
you can download it, (eg entities.met in the solipsis distrib) and/or while
using Solipsis you keep memory of met entities so the list is frequently
updated.
Q2: By now: Checking is done for all known entities (whether they are inside
or outside SOI); When entity A detects that an entity B has entered the SOI
of entity C, entity A sends out immediatly a message to entity C. If entity
B is outside SOI of entity C, nothing occurs.
Q3: So so. We have proved that in some tricky cases it will not work. But we
have strong hints that it should works most of the time (not proved).
Q4: I am not sure to fully understand this question. There are some
deterministic rules to choose entities that will restore or keep GC
(something like "take the nearest that fulfill GC property"). But all that
is probably not very predictable since unpredictable network delays have a
huge impact on rules like "take the first node you got and..."
Q5: The awareness radius, awareness area or SOI is enlarged or reduced in
order to keep the number of entities inside in a certain range (say between
9 and 15).

Have fun,
-- Joaquin


BTW: we plan to handle multiple (human) languages in Solipsis GUI, and our
first target (after english) is Chinese (simplified-mainland and/or
classical-taiwanese) we will be happy if you and your friend contribute on
that.
-----Message d'origine-----
De : Shun-Yun Hu [mailto:sy...@ya...]
Envoyé : mardi 8 juin 2004 15:53
À : KELLER Joaquin FTRD/DMI/ISS; SIMON Gwendal FTRD/DMI/ISS Objet :
[Solipsis] some questions about Solipsis (from Taiwan)




Hello Joaquin and Gwendal,

I'm a CS graduate student in Taiwan, I've recently learned the very
interesting and wonderful works you guys are doing at France Telecom R&D, on
Solipsis.

I got very interested in your work because I've also been thinking about a
massive P2P Virtual Environment that exists on the Internet, and I've been
doing related studies and research since Sept. 2003, along with a good
friend of mine.

I've only come across Solipsis recently, and had read through both of your
papers. However, I've some questions raised in my mind. If you could answer
these questions for me I'd very appreciated. :)

Q1. what's the bootstrap procedure? (i.e. how does a node join Solipsis
initially? through a list of known nodes? or through a 'gateway server' of
some sort?)

Q2. when, and how frequent does an entity check for mutual neighbor
discovery? (every time when someone within the Sphere of Influence (SOI) is
moving? or at certain intervals? another question is about the range of
checking. According to the paper, seems like checking is done only for those
entities within your SOI, however, to ensure Global Conneectivity (GC), it
seems like it's possible you would connect to entities outside of your SOI,
then will you check for those entities whether they're enterining someone
else's SOI?)

Q3. A very important question is, is GC guaranteed to be maintained if every
node keeps the "inside convex hull" property? I understand you seem to be
thinking that is the case, however, has this been proven by either
simulation or mathematicial analysis? (I'm very curious to this question,
because I've also met with a similiar problem).

Q4. To ensure Local Awareness and Global Connectivity, entities need to
connect to each other, however, are connections between entities uniquely
determined, given their locations in the virtual world, or are there
actually more than one possibility of these 'links' between entities? (I'm
thinking the case when an entity is trying to ensure GC, the entities
connections it end up doing, might not be done in a strictly deterministic
manner, or is it purely deterministic?)

Q5. under what situation would SOI be enlarged? (the paper describes how it
could be reduced, when there are too many to connect, what about
enlargement?)

sorry for these long questions, I'd appreicate very much if you could answer
them. :)

We've got a paper that'll appear in the NetGame 2004 workshop coming up in
early Sept. also on P2P networked virtual environment. If you're interested,
I'd be willing to forward a copy to you.

Thanks again and cheers! :)


Shun-Yun Hu