TY - GEN
T1 - Optimal Channel Utilization with Limited Feedback
AU - De Marco, Gianluca
AU - Jurdziński, Tomasz
AU - Kowalski, Dariusz R.
N1 - Funding Information:
This work is supported by the Polish National Science Center (NCN) grants UMO-2017/25/B/ST6/02553 and UMO-2017/25/B/ST6/02010.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - Algorithm
KW - Distributed
KW - Group testing
KW - Limited feedback
KW - Lower bound
KW - Multiple-access channel
KW - Threshold group testing
UR - http://www.scopus.com/inward/record.url?scp=85070650992&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070650992&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-25027-0_10
DO - 10.1007/978-3-030-25027-0_10
M3 - Conference contribution
AN - SCOPUS:85070650992
SN - 9783030250263
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 140
EP - 152
BT - Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Proceedings
A2 - Gąsieniec, Leszek Antoni
A2 - Jansson, Jesper
A2 - Levcopoulos, Christos
PB - Springer Verlag
T2 - 22nd International Symposium on Fundamentals of Computation Theory, FCT 2019
Y2 - 12 August 2019 through 14 August 2019
ER -