Large Deviations of the Throughput in Multi-Channel Medium-Access Protocols

Abstract

This thesis considers Aloha and slotted Aloha protocols as medium access rules for a multichannel message delivery system. Users decide randomly and independently with a minimal amount of knowledge about the system at random times to make a sending attempt. The system has a fixed number of available channels; equivalently, interference constraints make the delivery of too many messages at a time impossible. We derive probabilistic formulas for the most important quantities like the number of successfully delivered messages and the number of sending attempts, and we derive large-deviation principles for these quantities in the limit of many participants and many sending attempts. We analyse the rate functions and their minimizers and derive laws of large numbers. In particular, we are interested in questions like “if the number of successfully delivered messages is significantly lower than the expectation, was the reason that too many or too few sending attempts were made?”. The main tools are from the theory of large deviations.