Analysis of contention tree algorithms

A.J.E.M. Janssen, M.J.M. Jong, de

Research output: Contribution to journalArticleAcademicpeer-review

58 Citations (SciVal)
276 Downloads (Pure)


The Capetanakis-Tsybakov-Mikhailov contention tree algorithm provides an efficient scheme for multiaccessing a broadcast-communication channel. This paper studies statistical properties of multiple-access contention tree algorithms with ternary feedback for arbitrary degree of node. The particular quantities under investigation are the number of levels required for a random contender to have successful access, as well as the number of levels and the number of contention frames required to provide access for all contenders. Through classical Fourier analysis approximations to both the average and 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 converge to a fixed mode, but contain an oscillating term as well.
Original languageEnglish
Pages (from-to)2163-2172
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number6
Publication statusPublished - 2000


Dive into the research topics of 'Analysis of contention tree algorithms'. Together they form a unique fingerprint.

Cite this