Exponential Backoff: Meta-Stability and Implicit Admission Control

Abstract

We analyze exponential backoff, an algorithm used to share a single communication channel in a distributed manner between several users, in a similar way as many networking standards such as 802.11. We demonstrate that this algorithm has a meta-stable behavior, in the sense that the system oscillates over long time-scales between meta-stable configurations where only a subset of the sources effectively access the channel. In other words, meta-stability creates a form of implicit admission control. We provide both theoretical tools and numerical experiments to understand this phenomenon further. Our experiments are fully reproducible and the code is publicly available as a Python package available at https://pypi.org/project/slotted-aloha-simulator/.

25 pages