Geodesic
On stability of multiple access systems with minimal feedback
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1805-1821.

Voir la notice de l'article provenant de la source Math-Net.Ru

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).
Keywords: random multiple access, binary feedback, multiple transmission; positive recurrence, (in)stability, Foster criterion. 
@article{SEMR_2019_16_a47,
     author = {M. G. Chebunin and S. G. Foss},
     title = {On stability of multiple access systems with minimal feedback},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1805--1821},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a47/}
}
TY  - JOUR
AU  - M. G. Chebunin
AU  - S. G. Foss
TI  - On stability of multiple access systems with minimal feedback
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 1805
EP  - 1821
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a47/
LA  - ru
ID  - SEMR_2019_16_a47
ER  - 
%0 Journal Article
%A M. G. Chebunin
%A S. G. Foss
%T On stability of multiple access systems with minimal feedback
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 1805-1821
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a47/
%G ru
%F SEMR_2019_16_a47
M. G. Chebunin; S. G. Foss. On stability of multiple access systems with minimal feedback. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1805-1821. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a47/

[1] M. Bramson, Stability of queueing networks, Lecture Notes in Mathematics, Springer, Berlin, 1950 | MR | Zbl

[2] S. Meyn, R. L. Tweedie, Markov Chains: Stochastic Stability, Springer, 1993 | MR | Zbl

[3] S. G. Foss, B. Hajek, A. M. Turlikov, “Doubly Randomised Protocols for a Random Multiple Access Channel with «Success-Nonsuccess» Feedback”, Problems of Information Transmission, 52:2 (2016), 60–70 | DOI | MR

[4] M. Chebunin, “On ergodic algorithms in systems of multiple access with partial feedback”, Siberian Electronic Mathematical Reports, 13 (2016), 762–781 | MR | Zbl

[5] C. Bordenave, S. Foss, V. Shneer, “A Random Multiple Access Protocol with Spatial Interactions”, Journal of Applied Probability, 46:3 (2009), 844–865 | DOI | MR | Zbl

[6] A. A. Borovkov, Probability Theory, Universitext, 2013 | DOI | MR | Zbl

[7] G. Fayolle, E. Gelembe, J. Labetoulle, “Stability and optimal control of the packet switching broadcast channel”, J. of Assoc. Comput. Mach., 24 (1977), 375–386 | DOI | MR | Zbl

[8] G. I. Falin, Random processes in structurally complex queueing systems, Dissertation d.f.-m.s., MSU, M., 1989 | MR

[9] B. S. Tsybakov, V. A. Mihajlov, “Free synchronized access in a broadcast channel with a feedback”, Problems of Information Transmission, 14:4 (1978), 32–59 | MR | Zbl

[10] J. L. Capetanakis, “Tree algorithms for packet broadcast channels”, IEEE Transactions on Information Theory, 25:5 (1979), 505–515 | DOI | MR | Zbl

[11] B. Hajek, T. van Loon, “Decentralized dynamic control of a multiaccess broadcast channel”, IEEE Trans. Automatic Control, 27:3 (1982), 559–569 | DOI | Zbl

[12] V. A. Mihajlov, “Geometrical Analysis of the Stability of Markov Chains in ${\mathbf R}^n_+$ and Its Application to Throughput Evaluation of the Adaptive Random Multiple Access Algorithm”, Problems of Information Transmission, 24:1 (1988), 47–56 | MR | Zbl

[13] N. Mehravari, T. Berger, “Poisson multiple-access contention with binary feedback”, IEEE Transactions on Information Theory, 30:5 (1984), 745–751 | DOI | MR | Zbl

[14] B. Paris, B. Aazhang, “Near-optimum control of multiple-access collision channels”, IEEE Transactions on Wireless Communications, 40 (1992), 1298–1308 | DOI | Zbl

[15] A. Malkov, A. Turlikov, “Random multiple access protocols for communication systems with «success-failure» feedback”, IEEE International Workshop on Information Theory (1995), 1–39

[16] B. S. Tsybakov, A. N. Beloyarov, “Random multiple access in a channel with a binary feedback «Success-Failure»”, Problems of Information Transmission, 26:3 (1990), 67–82 | MR | Zbl

[17] B. S. Tsybakov, A. N. Beloyarov, “Random multiple access in a channel with a binary feedback”, Problems of Information Transmission, 26:4 (1990), 83–97 | MR | Zbl

[18] A. Turlikov, S. Foss, “On ergodic algorithms in random multiple access systems with «success-failure» feedback”, Problems of Information Transmission, 46:2 (2010), 185–201 | DOI | MR | Zbl

[19] S. G. Foss, Stochastic recursive sequences and their applications in Queueing, Dissertation d.f.-m.s., IM SB RAS, Novosibirsk, 1992 | MR

[20] A. Ephremides, B. Hajek, “Information theory and communication networks: An unconsummated union”, IEEE Trans. Inform. Theory, 44:6 (1998), 2416–2434 | DOI | MR | Zbl