Distributed Balancing under Flow Constraints over Arbitrary Communication Topologies

In this paper, we consider a flow network that is described by a digraph, each edge of which can admit a flow within a certain interval, with nonnegative end points that correspond to lower and upper flow limits. We propose and analyze a distributed iterative algorithm for solving the so-called feasible circulation problem, which consists of computing flows that are within the given intervals at each edge and balance the total in-flow and the total out-flow at each node. Unlike previously proposed distributed algorithms that required bidirectional communication between pairs of nodes that share an edge in the flow network, the algorithm we propose can operate over any communication network, assuming the corresponding digraph that describes it is strongly connected. The proposed algorithm allows the nodes to asymptotically compute (with a geometric rate that depends on the specifics of the given flow network and communication topology) a solution to the feasible circulation problem, as long as such a solution exists. An important special case of the setting studied in this paper is the case where the digraph of the flow network matches the digraph of the communic