Dynamic Distributed Scheduling in Random Access Networks

We consider a model of random access ("Slotted-Aloha-type") communication networks of general topology. Assuming network links receive exogenous arrivals of packets for transmission, we seek dynamic distributed random access strategies whose goal is to keep all the network queues stable. 

We prove that the dynamic strategy, which we call Queue length based Random Access (QRA), ensures stability as long as the rates of exogenous arrival flows are within the network saturation rate region. (This region is typically smaller than the network maximum stability region, i.e. the region of arrival rates under which stability is feasible.) 

We discuss the relation and differences between QRA and so called MaxWeight-type algorithms. In fact, our stability analysis applies to a class of algorithms including both QRA and MaxWeight as special cases.