Distributed Resource Allocation Among a Subset of Nodes of a Graph

A weakness of most distributed resource allocation algorithms proposed in the literature is that they assume that all nodes of the underlying graph are involved in the resource allocation problem. Such assumption does not hold in some applications. This manuscript deals with the problem of resource allocation among a subset of nodes of a graph. We propose a fully distributed algorithm based on consensus that provably reaches the optimal solution of a class of resource allocation problem that only involves certain nodes of a graph. Usefulness of the proposed algorithm is illustrated by means of two applications: distributed computation of a minimum-covariance estimate in sensor networks under failures, and distributed node counting.