Delay on Broadcast Erasure Channels Under Random Linear Combinations

DOI10.1109/TIT.2016.2634007zbMATH Open1368.94055arXiv1408.3469OpenAlexW1503869652MaRDI QIDQ5347979FDOQ5347979

Authors: Nan Xie, John MacLaren Walsh, Steven Weber 

Publication date: 25 August 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: A well-known inner bound on the stability region of the finite-user slotted Aloha protocol is the set of all arrival rates for which there exists some choice of the contention probabilities such that the associated worst-case service rate for each user exceeds the user's arrival rate, denoted $Lambda$. Although testing membership in $Lambda$ of a given arrival rate can be posed as a convex program, it is nonetheless of interest to understand the properties of this set. In this paper we develop new results of this nature, including $i)$ an equivalence between membership in $Lambda$ and the existence of a positive root of a given polynomial, $ii)$ a method to construct a vector of contention probabilities to stabilize any stabilizable arrival rate vector, $iii)$ the volume of $Lambda$, $iv)$ explicit polyhedral, spherical, and ellipsoid inner and outer bounds on $Lambda$, and $v)$ characterization of the generalized convexity properties of a natural ``excess rate function associated with $Lambda$, including the convexity of the set of contention probabilities that stabilize a given arrival rate vector.

Full work available at URL: https://arxiv.org/abs/1408.3469

Mathematics Subject Classification ID

Information theory (general) (94A15)

This page was built for publication: Delay on Broadcast Erasure Channels Under Random Linear Combinations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5347979)