Stateless Near Optimal Flow Control with Poly-logarithmic Convergence | SpringerLink
Skip to main content
Springer Nature Link
Log in

Stateless Near Optimal Flow Control with Poly-logarithmic Convergence

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

  • 1725 Accesses

Abstract

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:

If a path has many “congested” edges, decrease the flow on the path by a small multiplicative factor, otherwise increase its flow by a small multiplicative factor.

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 poly-logarithmic number of rounds, a 1 + ε approximation of the maximum throughput multicommodity flow. Moreover, the total number of rounds in which the solution is not 1 + ε approximate is also poly-logarithmic. Previous distributed solutions in our model either required a state since they used a primal-dual approach or had very slow (polynomial) convergence.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Awerbuch, B., Azar, Y., Khandekar, R.: Fast load balancing via bounded best response. In: SODA (2008)

    Google Scholar 

  2. Awerbuch, B., Khandekar, R.: Distributed network monitoring and multicommodity flows:primal-dual approach. In: PODC (2007)

    Google Scholar 

  3. Awerbuch, B., Khandekar, R.: Greedy distributed optimization of multi-commodity flows. In: PODC (2007)

    Google Scholar 

  4. Awerbuch, B., Khandekar, R., Rao, S.: Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. In: SODA (2007)

    Google Scholar 

  5. Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: FOCS (1991)

    Google Scholar 

  6. Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: FOCS (1991)

    Google Scholar 

  7. Bartal, Y., Byers, J.W., Raz, D.: Global optimization using local information with applications to flow control. In: FOCS (1997)

    Google Scholar 

  8. Dijkstra, E.: Self stabilizing systems in spite of distributed control. CACM 17, 643–644 (1974)

    MATH  Google Scholar 

  9. Dolev, S., Israeli, A., Moran, S.: Self-stabilization of dynamic systems assuming only read/write atomicity. In: PODC (1990)

    Google Scholar 

  10. Fleischer, L.: Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics 13, 505–520 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  11. Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: FOCS (1998)

    Google Scholar 

  12. Garg, N., Young, N.E.: On-line, end-to-end congestion control. In: FOCS (2002)

    Google Scholar 

  13. Gouda, M.G., Multari, N.J.: Stabilizing communication protocols. Technical Report TR-90-20, Dept. of Computer Science, University of Texas at Austin (June 1990)

    Google Scholar 

  14. Koufogiannakis, C., Young, N.E.: Beating simplex for fractional packing and covering linear programs. In: FOCS (2007)

    Google Scholar 

  15. Kuhn, F.: The price of locality: exploring the complexity of distributed coordination primitives. PhD Thesis, ETH Zurich, Diss. ETH No. 16213, (December 2005)

    Google Scholar 

  16. Luby, M., Nisan, N.: A parallel approximation algorithm for positive linear programming. In: STOC (1993)

    Google Scholar 

  17. Plotkin, S., Shmoys, D., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. Math of Oper. Research 20(2), 257–301 (1994)

    Article  MathSciNet  Google Scholar 

  18. Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: FOCS (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Johns Hopkins University,  

    Baruch Awerbuch

  2. IBM T.J.Watson Research Center,  

    Rohit Khandekar

Authors
  1. Baruch Awerbuch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rohit Khandekar
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Awerbuch, B., Khandekar, R. (2008). Stateless Near Optimal Flow Control with Poly-logarithmic Convergence. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_50

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_50

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation