Stateless distributed gradient descent for positive linear programs

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.

Authors

• Baruch Awerbuch
• Rohit Khandekar

Keywords

• distributed and stateless algorithms
• fast convergence
• gradient descent
• linear programming