One of the authors of the p2p paper I looked at in my last posting emailed me with an update of thier work worth sharing with you..

... Please note that in the meantime we actually looked at a more sophisticated scenario in the context of hyperheuristics:

http://portal.acm.org/citation.cfm?doid=1569901.1570081

where, quite surprisingly (or maybe not...), what we found is again if you have lots of nodes, then the best is to use them pretty much independently and start several kinds of optimization algorithms on subsets of these  nodes. Although it is of course non-trivial as always what is "best", etc.