On a recurrence equation arising in the analysis of conflict resolution algorithms
- 1 January 1987
- journal article
- research article
- Published by Taylor & Francis in Communications in Statistics. Stochastic Models
- Vol. 3 (1) , 89-114
- https://doi.org/10.1080/15326348708807048
Abstract
Conflict resolution algorithms (CRA) for broadcast communications have become increasingly popular since the work of Capetanakis as well as Tsybakov and Mikhailov (CTM-algorithm). In this paper we consider a class of CTM algorithms for which a common recurrence equation for the expected length of the conflict resolution interval holds. An analysis of that equation is the primary goal of this paper. A closed form expression for the solution of the recurrence is given. We also present an asymptotic approximation for it. In addition, we solve a functional equation associated with the recurrence and study a small value as well as an asymptotic approximations of the solution. Finally, we apply these approximations to compute the maximum throughput of some CRA. Our results are not restricted to the analysis of CRA , and a wide class of algorithms might be investigated by the proposed recurrence equation.Keywords
This publication has 6 references indexed in Scilit:
- Delay analysis of interval-searching contention resolution algorithmsIEEE Transactions on Information Theory, 1985
- Analysis of a stack algorithm for random multiple-access communicationIEEE Transactions on Information Theory, 1985
- Generalized TDMA: The Multi-Accessing Tree ProtocolIEEE Transactions on Communications, 1979
- Tree algorithms for packet broadcast channelsIEEE Transactions on Information Theory, 1979
- Criteria for classifying general Markov chainsAdvances in Applied Probability, 1976
- Some Conditions for Ergodicity and Recurrence of Markov ChainsOperations Research, 1969