Only Small World P2P Network Navigation (Search) Scalable

Only small world networks are scalable i.e. can grow in size without becoming very inefficient.

A small world network, where nodes represent people and edges connect people that know each other, captures the small world phenomenon of strangers being linked by a mutual acquaintance.

The small world phenomenon (also known as the small world effect) is the hypothesis that everyone in the world can be reached through a short chain of social acquaintances. The concept gave rise to the famous phrase six degrees of separation after a 1967 small world experiment by social psychologist Stanley Milgram which suggested that two random US citizens were connected on average by a chain of six acquaintances.

This has far reaching consequences for 'anonymous' P2P file sharing. A leading researcher on small world networks, Jon Kleinberg, states the following:

Moreover, α=2 is the only exponent at which any decentralized algorithm can achieve a delivery time bounded by any polynomial in logN: for every other exponent, an asymptotically much larger delivery time is required, regardless of the algorithm employed.

Jon Kleinberg
http://www.cs.cornell.edu/home/kleinber/nat00.pdf

Lets take this phrase by phrase to see what does this actually mean for anonymous file sharing clients like ANts P2P, MUTE and Freenet.

• α=2 is the only exponent at which any decentralized algorithm can achieve a delivery time bounded by any polynomial in logN.
• logN refers to the width of a network.
• As the number of users (N) increases, the average number of hops between any two users, the width, increases by a factor of logN.
• However, it is expected delivery time (T) for messages sent between users that is important for file sharing.
• T increases by a factor of logN only for small world networks (α=2). For other networks T is very much larger.
• T for a ad-hoc overlay p2p net (like ANts, MUTE or Freenet) is the number of users a file or query has to be forwarded via to reach its destination, the path length (L).
• For a small network the path length is small so that a workable amount of bandwidth in total is used in uploading and downloading for each hop along path length.
• For a large network L is far too large unless the network is small world although ironically the width of the network still scales by logN.

• for every other exponent, an asymptotically much larger delivery time is required, regardless of the algorithm employed.
• So you can come up with whatever clever message routing method you like, it will not scale unless it is small world.
• It is the network structure, the topology not the routing algorithm that determines if a network scales.
• So neither ANts P2P or MUTE will scale by improving routing algorithms while they remain networks with a random topology(structure).
• However, Iain Clark of Freenet seems to have already made this break through and has redesigned Freenet 0.7 to be small world.

I have decided to do the same for ANts p2p file sharing by making a very simple mod that will force the network to be small world.

kerjodando, the name of my ANts p2p mod, will force users to connect to only friends or others that share a similar interest to themselves, a p2p small world social network.

I call these groups, swarms and they are controlled, like bit torrent, by a simple tracker. Users can be members of many swarms covering all their interests and social networks. Swarms can either be private (invitation only) or public.

In this way kerjodando will be more scalable and be able to grow much bigger.

Hornet