Distributed Balancing under Flow Constraints over Arbitrary Communication Topologies

In this article, we consider a flow network that is described by a digraph, each edge of which can admit a flow within a certain interval, with non-negative 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 inflow and the total outflow 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 article is the case where the digraph of the flow network matches the digraph of the communication network.