Brief announcement: Greedy distributed optimization of unsplittable multicommodity flows

Abstract

We consider solutions for distributed unsplittable multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. A requirement here is that each commodity routes its entire demand along a single path at any point in time. Assuming that the minimum capacity of any edge is at least polylogarithmic factor larger than the maximum demand of any commodity, we present a greedy distributed randomized algorithm, which with high probability, achieves 1 + ∈ approximation, in O(H · logO(1) m · (1/∈)O(1)) iterations where H ≤ n is an upper bound on the number edges allowed on any flow-path. No prior results exist for our distributed model. Our algorithm is based on simulating the splittable multicommodity flow solution of [1] and picking a path for routing the entire flow according to the probability distribution given by the splittable flow. We use Chernoff bounds to show that the real edgecongestions are sufficiently close to the edge-congestions in the simulation for the analysis of [1] to hold.