Maximizing Utility via Random Access without Message Passing

abstract It has been an intensively sought-after goal to achieve high throughput and fairness in wireless scheduling through simple and distributed algorithms. Many recent papers on the topic have relied on various types of message passing among the nodes. The following question remains open: can scheduling without any message passing guarantee throughput-optimality and fairness? Over the last year, it has been suggested in three papers [1]–[3] that random access without message passing may be designed and proved to be optimal in terms of throughput and utility. In this paper, we first extend the algorithm in [2] and provide a rigorous proof of utility-optimality for random access without message passing for Poisson clock model. Then we turn to the more difficult discrete contention and backoff model with collisions, study its optimality properties, and control a tradeoff between long-term efficiency and short-term fairness that emerges in this model. I.