Optimal Channel Utilization with Limited Feedback

A channel with multiplicity feedback is a shared channel that in case of collision (two or more stations transmitting simultaneously) returns as a feedback the exact number of stations simultaneously transmitting. It is known that in such a model (formula presented) time rounds are sufficient and necessary to identify the IDs of d transmitting stations, from an ensemble of n. In contrast, the model with collision detection (or ternary feedback) allows only a limited feedback from the channel: 0 (silence), 1 (success) or 2+ (collision). In this case it is known that (formula presented) time rounds are necessary. Generalizing, we can define a feedback interval [x, y], where (formula presented), such that the channel returns the exact number of transmitting stations only if this number is within that interval. The collision detection model corresponds to x = 0 and y = 1, while the multiplicity feedback is obtained for x=0 and y=d. It is natural to ask for which size of the feedback intervals we can still get the same optimal time complexity (formula presented) valid for the channel with multiplicity feedback. In this paper we show that we can still use this number of time rounds even when the interval has a substantially smaller size: namely (formula presented). On the other hand, we also prove that if we further reduce the size of the interval to (formula presented), then no protocol having time complexity (formula presented) is possible.