05263940

a

05263940 Awerbuch, Baruch Khandekar, Rohit Stateless near optimal flow control with poly-logarithmic convergence. Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, B\'uzios, Brazil, April 7--11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 580-592 (2008). 2008 Berlin: Springer EN

doi:10.1007/978-3-540-78773-0_50

Summary: We design completely local, stateless, and self-stabilizing flow control mechanism to be executed by ``greedy'' agents associated with individual flow paths. Our mechanism is very natural and can be described in a single line: The mechanism does not require any initialization or coordination between the agents. We show that starting from an arbitrary feasible flow, the mechanism always maintains feasibility and reaches, after polylog arithmic number of rounds, a $1 + \epsilon $ approximation of the maximum throughput multicommodity flow. Moreover, the total number of rounds in which the solution is not $1 + \epsilon $ approximate is also polylog arithmic. Previous distributed solutions in our model either required a state since they used a primal-dual approach or had very slow (polynomial) convergence.