GOSH! Gossiping Optimization Search Heuristics

Mauro Brunato, Roberto Battiti, Alberto Montresor

Abstract:

While the use of distributed computing in search and optimization problems
has a long research history, most efforts have been devoted to
parallel implementations with strict synchronization requirements or
to distributed architectures where a central server
coordinates the work of clients by partitioning the search space or
working as a status repository.

In this paper we discuss the distributed implementation of
global function optimization through decentralized
processing in a peer-to-peer fashion, where relevant information is
exchanged among nodes by means of epidemic protocols.

A key issue in such setting is the degradation of the quality of the solution
due to the lack of complete information about the global search status.
A tradeoff between message complexity and solution quality must be
investigated.

Preliminary computational results in  a simplified setting, reported in the experimental section,
show that research in the field is motivated.