STABILITY CONDITIONS FOR SOME DISTRIBUTED SYSTEMS - BUFFERED RANDOM-ACCESS SYSTEMS

被引:197
作者
SZPANKOWSKI, W
机构
关键词
ALOHA; MULTIDIMENSIONAL MARKOV CHAINS; SUBSTABILITY; LOYNES SCHEME; MATHEMATICAL INDUCTION;
D O I
10.2307/1427448
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
We consider the standard slotted ALOHA system with a finite number of buffered users. Stability analysis of such a system was initiated by Tsybakov and Mikhailov (1979). Since then several bounds on the stability region have been established; however, the exact stability region is known only for the symmetric system and two-user ALOHA. This paper proves necessary and sufficient conditions for stability of the ALOHA system. We accomplish this by means of a novel technique based on three simple observations: applying mathematical induction to a smaller copy of the system, isolating a single queue for which Loynes' stability criteria is adopted, and finally using stochastic dominance to verify the required stationarity assumptions in the Loynes criterion. We also point out that our technique can be used to assess stability regions for other multidimensional systems. We illustrate it by deriving stability regions for buffered systems with conflict resolution algorithms (see also Georgiadis and Szpankowski (1992) for similar approach applied to stability of token-passing rings).
引用
收藏
页码:498 / 515
页数:18
相关论文
共 26 条
[1]   THE STABILITY REGION OF THE FINITE-USER SLOTTED ALOHA PROTOCOL [J].
ANANTHARAM, V .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1991, 37 (03) :535-540
[2]  
Borovkov AA, 1976, STOCHASTIC PROCESSES, DOI [10.1007/978-1-4612-9866-3, DOI 10.1007/978-1-4612-9866-3]
[3]  
Breiman L., 1968, PROBABILITY
[4]   TREE ALGORITHMS FOR PACKET BROADCAST CHANNELS [J].
CAPETANAKIS, JI .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1979, 25 (05) :505-515
[5]  
Falin G., 1981, TECH KIBERN, V4, P126
[6]   ON RANDOM-WALKS ARISING IN QUEUING-SYSTEMS - ERGODICITY AND TRANSIENCE VIA QUADRATIC-FORMS AS LYAPOUNOV FUNCTIONS .1. [J].
FAYOLLE, G .
MATHEMATICAL THEORY OF QUEUEING SYSTEMS, 1989, 5 :167-184
[7]  
Georgiadis L., 1992, Queueing Systems Theory and Applications, V11, P7, DOI 10.1007/BF01159285
[8]  
GEORGIADIS L, 1993, 11TH P INT C AN OPT
[9]  
GEORGIADIS L, 1993, 31ST P ANN ALL C MON
[10]   STABILITY OF A QUEUE WITH NON-INDEPENDENT INTER-ARRIVAL AND SERVICE TIMES [J].
LOYNES, RM .
PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1962, 58 (JUL) :497-&