Utility-Optimal Random Access Without Message Passing

Random access has been studied for decades to achieve simple wireless Medium Access Control (MAC). Some of the distributed scheduling algorithms for throughput or utility maximization also take the form of random access, although extensive message passing among the nodes is required. In this paper, the authors would like to answer this question: is it possible to design a MAC algorithm that can achieve the optimal network performance without message passing? They provide the first positive answer to this question in a simple Aloha-type random access wireless ad-hoc network. In particular, they propose a distributed random medium access control algorithm based on the framework of Network Utility Maximization (NUM).