Abstract :

For over thirty years, researchers have studied how good can simple random access protocols work. Since 1992, some of the distributed scheduling algorithms for throughput maximization take the form of random access as well, although message passing among the nodes is required. Similarly, utility optimization with infinite backlog has been achieved with the help of message passing. Very recently, people have developed a CSMA-type random access algorithm without message passing that is proved to be utility-optimal. However, it remains open whether even simpler ones, such as Aloha-type random access, can achieve utility-optimality. In this talk, we provide the first positive answer to this question.

We develop the first Aloha-type random access algorithm that has no message passing yet is provably utility-optimal. Rather than using the standard dual decomposition and subgradient method, our development leverages the broadcast nature of wireless medium and the idea that distributed learning by each node of the history of contention may be as effective as message passing. Details on the optimality, convergence, and robustness of the algorithms will be discussed in this talk.