Asynchronous multiple access tree algorithms
Mart L. Molle · ACM SIGCOMM Computer Communication Review · 1983
Random access protocols allow large numbers of low duty cycle stations to exchange messages over a shared communications channel under distributed control. Recently, a new class of random access protocols called 'tree algorithms' has emerged. Tree algorithms offer several performance advantages over other random access protocols (e.g. ALOHA and CSMA), namely higher capacity and inherently stable operation. However, only synchronous (slotted) tree algorithms have so far been defined. Any practical implementation of a synchronous protocol is complicated by the need for stations to perform the steps of the algorithm synchronously. Thus asynchronous (unslotted) protocols are of greater practical importance, especially for local networks. Here we show how to construct asynchronous versions of several well-known tree algorithms, and describe some of the performance limitations that result from asynchronous operation.