ε-almost selectors and their applications to multiple-access communication

Consider a group of stations connected through a multiple-access channel, with the constraint that if at a time instant exactly one station transmits a message, then the message is successfully received by any other station, whereas if two or more stations simultaneously transmit their messages then a conflict occurs and all messages are lost. Let us assume that n is the number of stations and that an (arbitrary) subset A of them, |A| ≤ k ≤ n, is active, that is, there are at most k stations that have a message to send over the channel. In the classical conflict resolution problem, the issue is to schedule the transmissions of each station to let every active station use the channel alone (i.e., without conflict) at least once, and this requirement must be satisfied whatever might be the set of active stations A. The parameter to optimize is, usually, the worst case number of transmissions that any station has to attempt before all message transmissions are successful. In this paper, we study the following question: is it possible to obtain a significant improvement on the protocols that solve the classical conflict resolution problem if we allow the protocols to fail over a 'small' fraction of all possible subsets of active stations? In other words, is it possible to significantly reduce the number of transmissions that must be attempted if the set of active stations is chosen uniformly at random and the conflict resolution algorithm is only required to work correctly with 'high' probability? In this paper, we will show that this is indeed the case. Our main technical tool is a generalization of selectors, a recently introduced combinatorial structure that has found applications in several areas. As it turned out for selectors, we believe that our new combinatorial structures are likely to be useful also outside the present context.