Optimal Channel Utilization with Limited Feedback

Gianluca De Marco, Tomasz Jurdziński, Dariusz R. Kowalski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationFundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Proceedings
EditorsLeszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783030250263
StatePublished - 2019
Event22nd International Symposium on Fundamentals of Computation Theory, FCT 2019 - Copenhagen, Denmark
Duration: Aug 12 2019Aug 14 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11651 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference22nd International Symposium on Fundamentals of Computation Theory, FCT 2019


  • Algorithm
  • Distributed
  • Group testing
  • Limited feedback
  • Lower bound
  • Multiple-access channel
  • Threshold group testing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Optimal Channel Utilization with Limited Feedback'. Together they form a unique fingerprint.

Cite this