Date Added: Apr 2011
This paper considers distributed protocol design for Resource Allocation (RA) problems. The authors propose a fully decentralized RA scheme based on the min-sum Message Passing (MP) approach in which each message is the solution of small distributed allocation problems. Due to the presence of cycles in the network graph, the MP routine may not converge to a fixed point. To this end, they introduce a Re-weighted MP (ReMP) algorithm that perturbs the ordinary min-sum algorithm by suitably Re-weighting messages. ReMP distributes the computational effort of achieving an optimal RA among nodes.