Geodesic
On ergodic algorithms in systems of multiple access with partial feedback
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 762-781.

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

We consider a model of a multiple access system with a non-standard partial feedback. Time is slotted. Quantities of messages in different time slots are independent and identically distributed random variables. At the beginning of each time slot each message presented in the system is sent to the channel with a certain probability, depending on available system history. If $i\ge1$ messages are being passed simultaneously, each of them is being passed successfully with probability $q_i$, and with probability $1-q_i$ transmission is distorted, the message remains in the system and tries to be sent later. We consider the case when $q_i> 0$ only if $i \le i_0$ for a given $i_0 \ge1$. By the end of the slot we receive information about the quantity of messages that were transmitted successfully (it is the «feedback») — only this information is available. The transmission algorithm (protocol) is a rule of setting transmission probabilities at different times based on the information, available to each moment. In particular, if $q_1 = 1$ and $q_i = 0$ for all $i>1$ then this feedback is called «success-nonsuccess». In this paper we study the existence of stable algorithms and the rate of convergence. Algorithms determined in this paper are based on additional randomization idea proposed in [3].
Keywords: random multiple access; binary feedback; positive recurrence; (in)stability; Foster criterion. 
@article{SEMR_2016_13_a47,
     author = {M. G. Chebunin},
     title = {On ergodic algorithms in systems of multiple access with partial feedback},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {762--781},
     publisher = {mathdoc},
     volume = {13},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a47/}
}
TY  - JOUR
AU  - M. G. Chebunin
TI  - On ergodic algorithms in systems of multiple access with partial feedback
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 762
EP  - 781
VL  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a47/
LA  - ru
ID  - SEMR_2016_13_a47
ER  - 
%0 Journal Article
%A M. G. Chebunin
%T On ergodic algorithms in systems of multiple access with partial feedback
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 762-781
%V 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a47/
%G ru
%F SEMR_2016_13_a47
M. G. Chebunin. On ergodic algorithms in systems of multiple access with partial feedback. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 762-781. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a47/

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

[2] S. Meyn, R. L. Tweedie, Markov Chains and 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

[4] V. V. Kalashnikov, Mathematical methods in queuing theory, Springer Science+Business Media, Dordrecht, 1994 | MR

[5] V. V. Kalashnikov, “Estimates of convergence rates and stability for regeneration and renewal Markov processes”, Queueing theory, VNIISI AS USSR, 1981, 7–12

[6] A. A. Borovkov, Probability Theory, Universitext, Springer, London, 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

[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

[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

[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–98 | 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

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

[20] D. Aldous, “Ultimate instability of exponential back-off protocol for acknowledgment based transmission control of random access communication channels”, IEEE Transactions on Information Theory, 33:2 (1987), 219–223 | DOI | MR | Zbl

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

[22] S. G. Foss, D. E. Denisov, “On transience conditions for Markov chains”, Sibirsk. Mat. Zh., 42:2 (2001), 425–433 | MR | Zbl