[p2p-hackers] Skipgraph and global balancing operations

[Michael Rogers]

I think it's referring to the fact that, unlike trees, skip lists don't 
need to be rebalanced as nodes are added and removed. AFAIK the reason 
is that the rank of each item in the list (ie the number of pointers the 
item keeps) is chosen randomly, so the higher "layers" are replaced 
incrementally as a natural result of churn.

Cheers,
Michael

Verdi March wrote:

>Hi,
>
>in the skipgraph paper [1], in section 2 it's mentioned that
>skip lists require no global balancing operations.
>
>I'm not clear at the "global balancing operations" statement:
>what are the operations and why skip lists don't need those.
>
>Any help is appreciated.
>
>
>Regards,
>Verdi
>
>_______________________________________________
>p2p-hackers mailing list
>p2p-hackers at zgp.org
>http://zgp.org/mailman/listinfo/p2p-hackers
>_______________________________________________
>Here is a web page listing P2P Conferences:
>http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
>  
>