Unbounded Contention Resolution: k-Selection in Radio Networks

Abstract

Using k-Selection in Radio Networks as an example of unique-resource dispute among k unknown contenders, the conflict-resolution protocol presented in this paper shows that, for any sensible probability of error ", all of them get access to such resource in asymptotically optimal time (e+1+ )k+O(log2(1=")), where > 0 is any constant arbitrarily close to 0. This protocol works under a model where not even an upper bound on k is known and conflicts can not be detected by all the contenders.