Survey-propagation decimation through distributed local computations -: art. no. P11016

We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey propagation (SP) algorithm. The first solver, called the 'SP diffusion algorithm', diffuses as dynamical information the maximum bias over the system, so that variable nodes can decide to freeze in a self-organized way, each variable making its decision on the basis of purely local information. The second solver, called the 'SP reinforcement algorithm', makes use of time-dependent external forcing messages on each variable, which are adapted in time in such a way that the algorithm approaches its estimated closest solution. Both methods allow us to find a solution of the random 3-SAT problem in a range of parameters comparable with the best previously described serialized solvers. The simulated time of convergence towards a solution ( if these solvers were implemented on a fully parallel device) grows as log(N).