Saw an article on The Register about AOL Instant Messenger blocking non-AOL clients. Thought - that's a pity, why can't we have P 2 P instant messaging (presumably the AOL system uses some sort of central control, hence their blocking ability). Realised the similarities with the Six Degrees Of Seperation experiments running at the moment.

For a request to discover something e.g. "AndyP", you could pass that request to a random server - this would then pass it to a server which dealt with labels closer to "AndyP" than itself - i.e. one which deals with "A****". The process then repeats. It's a hill climbing process, but hard due to the fact that each server needs to know a lot of others to improve once you get close - the "A****" server would need to know about better servers for 26^4 keys - about 0.5Million. Keeping 0.5M IP-addresses up to date would be hard.

Thought again about the Six Degrees Of Seperation problem - how did it work? What were the criteria that people (equivalent to server nodes) used to determine the "distance" of their friends to the target recipient? Hmmm... say: Age; Geography; Job; Interests. All these provide a high degree of discrimination, a hill to be climbed which is much easier than comparison of letters (because letter combinations only compare to give a 1bit result - match or no-match). Age and Geography are simple linear numeric distances, and Job and Interests are generalisation hierarchies (or networks) over which distances can be calculated (e.g. is "Cook" more similar to "Computer Scientist" or "Butcher").

So, if we stick with the letters for ease of labelling, we say "S" is closer to "R" than "A" is. We can also have server nodes which deal with more finely grained variable volumes of the search space - say "A-C,*,*,*,*" or "A,A,A-L,A,A".

Wondered if this kind of discovery scheme was used already, and did a Google Search on "p2p hill climbing discover" and turned up the Freenet Project - http://dgarnier.etudier-online.com/macs598-dos/research-project/freenet-paper.html which uses a similar method for discovery of file resources.

Wondered how other searches (e.g. Genetic) might be used in this context.

-- Andy Pryke - 31 Jan 2002