Stability conditions for some distributed systems : buffered random access systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1992

Stability conditions for some distributed systems : buffered random access systems

Wojciec Szpankowski
  • Fonction : Auteur

Résumé

We first consider the standard slotted Aloha system with a finite number of buffered users. Stability analysis of such a system was initiated in 1979 by Tsybakov and Mikhailov. 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 users Aloha. This paper proves necessary and sufficient conditions for stability of the Aloha system, hence solves the problem posed by Tsybakov and Mikhailov. We accomplish this by means of a novel technique based on three simple observations isolating single queue from the system, applying Loynes' stability criteria for such an isolated queue and using stochastic dominance and mathematical induction 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 the stability region for a buffered system with conflict resolution algorithms. In another paper, Georgiadis and Szpankowski (1992) used this technique to establish stability criteria for the token passing ring system.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1815.pdf (870.73 Ko) Télécharger le fichier

Dates et versions

inria-00074857 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074857 , version 1

Citer

Wojciec Szpankowski. Stability conditions for some distributed systems : buffered random access systems. [Research Report] RR-1815, INRIA. 1992. ⟨inria-00074857⟩
130 Consultations
229 Téléchargements

Partager

Gmail Facebook X LinkedIn More