well with the number of users. For such schemes, the rate region of the channel and the set of feasible QoS are well known (see e.g., [@neely-etal-powerrouting]). The performance of the system with partial channel state information was studied in [@gopalan-etal-partialcsi]. There is a lot of interest in developing distributed and semi-distributed algorithms for opportunistic scheduling. One popular technique has been to adjust the backoff parameters of the nodes based on their instantaneous channel gain. A number of works have studied the optimal performance and the achievable throughput of such strategies (see e.g., [@qin-berry-multiuser]). In [@qin-berry-osa], the authors propose a splitting algorithm that resolves contention with feedback from the base station. The distributed strategies incur losses due to collisions but are known to very efficient especially for networks with a large number of users.

In this work, we are interested in the contention resolution problem of resolving the identity of the user with the highest channel gain. We formulate the contention resolution problem for opportunistic scheduling as identifying a random threshold (channel gain) that separates the best channel from the other samples. We show that the average delay to resolve contention is related to the entropy of the threshold random 