Distributed integer weight balancing within interval constraints

Abstract

We consider distributed integer weight balancing in networks of nodes that are interconnected via directed edges, each able to admit a positive integer weight within a certain interval, captured by a lower and an upper limit. A digraph with positive integer weights on its edges is weight-balanced if, for each node, the sum of the weights of the incoming edges equals the sum of the weights of the outgoing edges. This paper proposes and analyzes a distributed algorithm for obtaining admissable and balanced integer weights; this can also be viewed as a distributed method for obtaining a set of integer flows that balance a flow network, for the case when there are lower and upper limit constraints on the flows. The proposed iterative algorithm assumes that communication among pairs of nodes that are interconnected is bidirectional, and allows the nodes to reach a set of balanced feasible integer weights/flows after a finite number of iterations. © 2016 IEEE.