> In the P2P world, O(log^2 N) may not be efficient, but > it may be the cheapest in terms of resources.
I like the use of "may" in that sentence. Well, maybe not. Small worlds typically need O(log N) connections to other nodes to maintain connectivity. Pastry and Chord use O(log N) connections as well. Small worlds get O(log^2 N) hop lookups, Pastry and Chord get O(log N). Remind me how x^2 packets and x^2 processing is better than x. >For instance, a walker > may take a while to find a resource in a small world topology, but it > expends little effort at each node. Same arguments apply to a Chord or Pastry lookup. The bandwidth spent to retain the ring structure is about the same as the bandwidth spent to ping neighbors. >Conversely, to attain fewer hops, > that also means a larger resource at each node to index and process > the index queries. True only in unstructured networks. Indexing and aggregation of the kind you allude to are not necessary to get better lookup times in structured p2p. >There are also ways to use the hubs in such > networks to greatly improve efficiency. Same techniques to reduce N apply equally well to other systems. > The small world is also not necessarily the complete network or only > topology available to an application. The number of hops in a search > is not the same as a the number of hops that may be applied to > communications. Thus even when one part is inefficient, the other may > be ideal. True, when something doesn't work well, there are other ways around it. I see nothing but hype in small worlds. Why not add UDDI+WSDL+ web services+social networking and become buzzword complete? How many here realize that the hype around small worlds was created mostly by physicists by applying elementary math to a highly idealized and theoretical problem, with no implementation? Those guys don't care about performance, just the pretty name. You've all seen the books, and you know they are devoid of content. 5 is really << 25. Use the better tool. Bob. _______________________________________________ p2p-hackers mailing list p2p-hackers@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