The transmission control protocol (TCP) that underpins most Internet traffic has a simple yet intuitively beautiful algorithm for congestion control. Every connection will gradually ramp up the bandwidth it uses until congestion occurs, at which point the connection throttles utilization. The additive-increase/multiplicative-decrease (AIMD) algorithm can be applied to a wide array of problem spaces where multiple agents compete for a limited resource.

The authors propose an algorithm that allows agents to respond probabilistically to a capacity constraint event, where such a response is determined by the agent’s success over either its entire past or some recent history interval. The authors also allow for each agent to have its own cost function. No inter-agent communication is required. The only coordination that is needed is for the shared resource to signal capacity constraint events and for an upfront global choice of a constant. This constant is chosen such that when multiplied by the derivative of each cost function and divided by that agent’s utilization, it gives a probability value between zero and one that can be used to decide whether to respond to a capacity event. Responses are considered asynchronous.

The authors prove that the algorithm will converge in the long run to an optimal state if the cost functions are strictly convex and continuously differentiable. They also show that despite having different cost functions, the agents converge to a common rate of change in their cost function. Although not the easiest paper to follow without domain knowledge or access to prior work, the authors do provide an excellent analysis of how their work differs from related research in a variety of domains.