On stability of multiple access systems with minimal feedback

M. G. Chebunin ; S. G. Foss

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1805-1821

Résumé

We introduce and analyse a new model of a multiple access transmission system with a non-standard «minimal feedback» information. We assume that time is slotted and that arriving messages form a renewal process. At the beginning of any time slot $n$, each message present in the system makes a transmission attempt with a (common) probability $p_n$ that depends on the system information from the past. Given that $B_n\ge 1$ messages make the attempt, each of them is successfully transmitted and leaves the system with probability $q_{B_n}$, independently of everything else, and stays in the system otherwise. Here $\{q_i\}$ is a sequence of probabilities such that $q_{i_0}>0$ and $q_i=0$ for $i>i_0$, for some $i_0\ge 1$. We assume that, at any time slot $n$, the only information available from the past is whether $i_0$ messages were successfully transmitted or not. We call this the «minimal feedback» (information). In particular, if $i_0=1$ and $q_1=1$, then this is the known «success-nonsuccess» feedback. A transmission algorithm, or protocol, is a rule that determines the probabilities $\{p_n\}$. We analyse conditions for existence of algorithms that stabilise the dynamics of the system. We also estimate the rates of convergence to stability. The proposed protocols implement the idea of ‘triple randomization’ that develops the idea of ‘double randomization’ introduced earlier by Foss, Hajek and Turlikov (2016).

Détail

Keywords: random multiple access, binary feedback, multiple transmission; positive recurrence, (in)stability, Foster criterion.