Stability of the Max-Weight Protocol in Adversarial Wireless Networks
In this paper, the authors consider the MAX-WEIGHT protocol for routing and scheduling in wireless networks under an adversarial model. This protocol has received a significant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal whenever the traffic patterns and propagation conditions are governed by a stationary stochastic process. However, the standard proof of throughput optimality (which is based on the negative drift of a quadratic potential function) does not hold when the traffic patterns and the edge capacity changes over time are governed by an arbitrary adversarial process.