A Bound on the Capacity of Backoff and Acknowledgment-Based Protocols
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson · SIAM Journal on Computing · 2004
We study contention-resolution protocols for multiple-access channels. We show that every backoff protocol is transient if the arrival rate, $\lambda$, is at least 0.42 and that the capacity of every backoff protocol is at most 0.42. Thus, we show that backoff protocols have (provably) smaller capacity than full-sensing protocols. Finally, we show that the corresponding results, with the larger arrival bound of 0.531, also hold for every acknowledgment-based protocol.