Analysis of contention tree algorithms

The Capetanakis-Tsybakov-Mikhailov contention tree algorithm provides an ef ficient scheme for multiaccessing a broadcast-communication channel. This p aper studies statistical properties of multiple-access contention tree algo rithms with ternary feedback For arbitrary degree of node. The particular q uantities under investigation are the number of levels required for a rando m contender to have successful access, as well as the number of levels and the number of contention frames required to provide access for all contende rs. Through classical Fourier analysis approximations to both the average a nd the variance are calculated as a function of the number of contenders n. It is demonstrated that in the limit of large n these quantities do not co nverge to a Bred mode, but contain an oscillating term as well.