[p2p-hackers] Node counting algorithm

[Sean C. Rhea]

On Feb 23, 2005, at 10:27 AM, Michael Parker wrote:
> If your leaf set overlaps, it's just the number of entries in your 
> leaf set.
> If your leaf set does not overlap, divide the size of the ring (e.g. 
> 2^128, 2^160) by the span of your leaf set (i.e., the farthest 
> clockwise node minus the farthest counterclockwise node, modulo the 
> ring size), and multiply by the size of your leaf set. Basically, what 
> this means is if your leaf set is size L, and it spans a percentage x 
> of the node identifier space, the size of the network is approximately 
> L * x^-1. To improve accuracy, ask the two farthest nodes in your leaf 
> set and ask them for their leaf sets, merging them into yours before 
> calculating. That way, you have a larger effective L.

This technique gives estimates that, on average, overestimate the size 
of the network if you pick node identifiers uniformly at random (UAR).  
The reason is that UAR doesn't mean evenly distributed; some nodes' 
leaf sets cover much more than others.  If you have one node whose leaf 
set covers a larger portion of the key space, that node underestimates 
the size of the ring, but a lot of other nodes end up covering less of 
the key space (to make room for the larger one) and end up 
overestimating the network size.  When you average them all, the few 
nodes that underestimate don't make up for all the rest that 
overestimate it.

IANAM (I am not a mathematician), but this is what happens when you 
simulate it at least, with identifiers drawn using SHA.  References for 
more mathematical explanations and a better algorithm are described in 
this paper:

   http://iptps05.cs.cornell.edu/PDFs/CameraReady_174.pdf

Sean
-- 
         Give a man a fish and he will eat for a day.  Teach him how
         to fish, and he will sit in a boat and drink beer all day.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://zgp.org/pipermail/p2p-hackers/attachments/20050223/45d8b186/PGP.pgp