Looking at Peer-to-Peer Optimization Methods

P2P algorithms can offer robustness and communication efficiency over more centralised GRID methods. So authors compared to p2p algorithms performance searching in large-scale and unreliable networks. They compared two methods; a distributed particle swarm optimization algorithm (PSO, a class of direct search methods used to find an optimal solution to a type of function that determines how good a solution is) and a novel P2P branch-and-bound (B&B) algorithm.

The B&B works by basically following this flow;

• Find a promising interval (an interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set) then cut this set of number into two.
• Then it takes 8 or more random samples from it. Then it calculates a fixed set of items.
• The queue of items is ordered based on the lower set. It then culls sets who cut across a pre-set minimum.
• Then it uses gossip-based load balancing.

It seems to me that this process acts as a kind on slice-and-dice to zoom in on promising sets of data then, and only when it’s got the lowest set possible, can the sharing of the data over the peers happen. Also this use of gossip to load-balance rather than the more traditional (and centralised) method of shared memory.

So what did they find? First of they found an interesting application of the B&B algorithm; Because of the culling behaviour described above it does not need to expand into the whole network to solve a given problem; “The interesting effect we can discover is that the B&B approach ‘refuses’ to utilize the entire network, because it cannot generate enough promising intervals (pruning is ‘too’ efficient) and therefore it can deliver optimal solutions irrespective of network size, but at the cost of longer running times … Depending on the context, this effect can be very advantageous but harmful as well.”

Some counter-intuitive findings are presented also: for example, failures in the network can in fact significantly improve the performance of p2p PSO under some conditions; “For P2P PSO, increasing the network size is equivalent to increasing the population size. Interestingly, a non-zero churn rate introduces a restarting operator for PSO, that can in fact increase performance on at least some types of problems.”

Balázs Bánhelyi, Marco Biazzini, Alberto Montresor, and Márk Jelasity (2009). Peer-to-Peer Optimization in Large Unreliable Networks with Branch-and-Bound and Particle Swarms Lecture Notes In Computer Science, 5484, 87-92