Stateless distributed gradient descent for positive linear programs

ABSTRACT

We develop a framework of distributed and stateless solutions for packing and covering linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our model has a separate "agent" controlling each variable and an agent is allowed to read-off the current values only of those constraints in which it has non-zero coefficients. This is a natural model for many distributed applications like flow control, maximum bipartite matching, and dominating sets.

The most appealing feature of our algorithms is their simplicity and polylogarithmic convergence. For the packing LP max{cx | Ax <= b, x >= 0}, the algorithm associates a dual variable y_i = exp[1ε * (A_ix/b_{i -1})] for each constraint i and each agent j iteratively increases (resp. decreases) x_j multiplicatively if A_j^T y is too small (resp. large) as compared to c_j. Our algorithm starting from a feasible solution, always maintains feasibility, and computes a (1+epsilon) approximation in poly((ln (mn A_max))ε) rounds. Here m and n are number of rows and columns of A and A_max, also known as the "width" of the LP, is the ratio of maximum and minimum non-zero entries A_ij/(b_ic_j). Similar algorithm works for the covering LP min{by | A^T y >= c, y >= 0} as well.

While exponential dual variables are used in several packing/ covering LP algorithms before [25, 9, 13, 12, 26, 16], this is the first algorithm which is both stateless and has polylogarithmic convergence. Our algorithms can be thought of as applying distributed gradient descent/ascent on a carefully chosen potential. Our analysis differs from those of previous multiplicative update based algorithms and argues that while the current solution is far away from optimality, the potential function decreases/increases by a significant factor.

REFERENCES

• 1: B. Awerbuch , Y. Azar, Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation, Proceedings of the Proceedings 35th Annual Symposium on Foundations of Computer Science, p.240-249, November 20-22, 1994 [doi>10.1109/SFCS.1994.365690]
• 2: Baruch Awerbuch , Yossi Azar , Rohit Khandekar, Fast load balancing via bounded best response, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.314-322, January 20-22, 2008, San Francisco, California
• 3: B. Awerbuch and R. Khandekar. Stateless near optimal distributed flow control with poly-logarithmic convergence. LATIN, 2008.
• 4: Baruch Awerbuch , Rohit Khandekar, Distributed network monitoring and multicommodity flows: a primal-dual approach, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281141]
• 5: Baruch Awerbuch , Rohit Khandekar, Greedy distributed optimization of multi-commodity flows, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281140]
• 6: Baruch Awerbuch , Rohit Khandekar , Satish Rao, Distributed algorithms for multicommodity flow problems via approximate steepest descent framework, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.949-957, January 07-09, 2007, New Orleans, Louisiana
• 7: Baruch Awerbuch , Boaz Patt-Shamir , George Varghese, Self-stabilization by local checking and correction (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.268-277, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185378]
• 8: Baruch Awerbuch , George Varghese, Distributed program checking: a paradigm for building self-stabilizing distributed protocols (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.258-267, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185377]
• 9: Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
• 10: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 11: Shlomo Dalev , Amos Israeli , Shlomo Moran, Self-stabilization of dynamic systems assuming only read/write atomicity, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.103-117, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93407]
• 12: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 13: Naveen Garg , Jochen Könemann, Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems, SIAM Journal on Computing, v.37 n.2, p.630-652, May 2007 [doi>10.1137/S0097539704446232]
• 14: Naveen Garg , Neal E. Young, On-Line End-to-End Congestion Control, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.303-312, November 16-19, 2002
• 15: Mohamed G. Gouda , Nicholas J. Multari, Stabilizing Communication Protocols, University of Texas at Austin, Austin, TX, 1990
• 16: Christos Koufogiannakis , Neal E. Young, Beating Simplex for Fractional Packing and Covering Linear Programs, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.494-504, October 21-23, 2007 [doi>10.1109/FOCS.2007.16]
• 17: F. Kuhn. The price of locality: exploring the complexity of distributed coordination primitives. PhD Thesis, ETH Zurich, Diss. ETH No. 16213, December 2005.
• 18: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, The price of being near-sighted, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.980-989, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109666]
• 19: Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872040]
• 20: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 21: Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
• 22: Moni Naor , Larry Stockmeyer, What Can Be Computed Locally?, SIAM Journal on Computing, v.24 n.6, p.1259-1277, Dec. 1995 [doi>10.1137/S0097539793254571]
• 23: Christos H. Papadimitriou , Mihalis Yannakakis, Linear programming without the matrix, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.121-129, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167127]
• 24: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 25: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 26: N. Young, Sequential and Parallel Algorithms for Mixed Packing and Covering, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.538, October 14-17, 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Theory

Keywords:
distributed and stateless algorithms, fast convergence, gradient descent, linear programming