A Class of Efficient Contention Resolution Algorithms for Multiple Access Channels

A discrete time multiaccess channel is considered where the outcome of a transmission is either "idle," "success," or "collision," depending on the number of users transmitting simultaneously. Messages involved in a "collision" must be retransmitted. An efficient access allocation policy is developed for the case where infinitely many sources generate traffic in a Poisson manner and can all observe the outcomes of the previous transmissions. Its rate of success is 0.48776. Modifications are presented for the cases where the transmission times depend on the transmission outcomes and where observations are noisy.