A - B - C - D - E - [ A ... ]
A 0.0
B 0.2
C 0.4
D 0.6
E 0.8
Now connect F to D.
F initially has value 0.1 (randomly chosen).
F attempts a swap. It connects to B and they decide whether to swap.
B's side: I am 0.2, neighbours 0.0 and 0.2, distance product is 0.04.
If I swap, my distance product is 0.1 * 0.3 = 0.03.
F's side: I am 0.1, my neighbour is 0.6, distance product is 0.5.
If I swap, my distance product is 0.4.
Oskar's algorithm: A is old distance product, B is new distance product.
If A > B, swap. If B > A, swap with probability A / B.
Thus A here is 0.04 * 0.5. B is 0.03 * 0.4. The swap is advantageous, so
we swap.
0.0 - 0.1 - 0.4 - 0.6 - 0.8 -
|
0.2
F is now disconnected, and replaced by G, at the same position. G has a
value of 0.3. This will not result in a swap. G is replaced with H. H
has an initial random value of 0.15. It swaps with 0.4, for much the
same reasons shown above; 0.05*0.45*0.45 = 0.010125, 0.3*0.2*0.45 =
0.0270.
0.0 - 0.1 - 0.15 - 0.6 - 0.8 -
Lets try 0.16 with D. You get:
A = 0.45 * 0.2 * 0.44 = 0.0390
B = 0.01 * 0.64 * 0.44 = 0.002816
Hence 0.0 - 0.1 - 0.15 - 0.16 - 0.8 -
I submit that the distribution of locations across the network will
become more and more compact over time, because of the near infinite
resolution of the random initial locations. Thus we require a means to
pick a random initial location which is not too close to an existing
location. Or perhaps the algorithm is immensely sensitive to topology,
and such a situation cannot be saved? Or perhaps this is purely the
result of swapping including nodes with only one peer? Could an attacker
do something like the above even if it doesn't normally happen (and if
it doesn't, why not?)?
Possible "random initial location not too close to existing location" ?
If we have global knowledge, this is easy. All we do is track the pair
of peers with the smallest location delta. When we add a new node, we
bisect it and use that location. Unfortunately this requires local
knowledge, and distributing it would probably require a large amount of
state. Perhaps we could send 3 probes out, to 3 different initial
keyspace locations, then pick the one with the longest gap? Any better
ideas? Or is this not necessary because I'm smoking crack here?
Will randomly resetting nodes' locations help or hinder? If a location
is "unpopular", it will move to a distant part of the network and then
be dropped, AFAICS. Whereas if it's "popular", it's probably because it
is even closer to a node than the best contender was before.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20061220/2b7f52d4/attachment.pgp>
