The Impact of Asynchrony on Stability of MAC

A large volume of work has already studied various aspects of a synchronous multiple access channel (MAC). However, synchronization is costly and far from reality. Very little is known in the case when stations communicating on the channel may observe asynchronous behavior. Unfortunately, in certain strong asynchrony settings it is impossible to ensure even a small positive throughput (deterministically). Hence, in this paper, we study whether a limited amount of synchrony is already enough for obtaining stability and high throughput. More specifically, we present a novel model to capture a bounded asynchrony, where the 'bounded' aspect is captured by an upper bound R on the length of any asynchronous time slot. We design two distributed deterministic algorithms to schedule transmissions of dynamically arriving packets at asynchronous stations, which guarantee optimal throughput for all but one packet injection rates and bounded queues at any time (this combination is sometimes known as optimal stable throughput). One of these algorithms is collision-free, while the other, instead, avoids control messages. Combining these results with our impossibility results we characterize exactly the very limited case where there is an inherent difference between synchronous and asynchronous networks for obtaining optimal stable throughput for this problem. As a subroutine, we design a new leader election algorithm for this model and prove upper and lower bounds on the number of slots. Interestingly, when R is a constant, our results match (asymptotically) the known results in synchronous slotted networks, while if R is a larger parameter, our lower bound proves that an additional factor of Ω(R/log R) is necessary in the formula on the number of slots.