I haven't had time to read it properly yet, but this paper describes an alternative approach to scalable search in f2f networks: essentially you take a random walk and then route towards the local minimum. With a small number of parallel inserts and a small number of parallel requests there's a good chance that one of the requests will end up in the same local minimum as one of the inserts.
It sounds similar to the 0.5 routing algorithm, but it doesn't require path compression because it doesn't try to create global minima. http://www.cs.umd.edu/~ruggero/papers/podc05.pdf Cheers, Michael
