Abstract
A channel with multiplicity feedback in case of collision returns the exact number of stations simultaneously transmitting. In this model, Θ((dlog(n/d))/logd) time rounds are sufficient and necessary to identify d transmitting stations out of n. In contrast, in the ternary feedback model the time complexity is Θ(dlog(n/d)). Generalizing, we can define a feedback interval [x,y], where 0≤x≤y≤d, such that the channel returns the exact number of transmitting stations only if this number is within that interval. For a feedback interval centered in d/2 we show that it is possible to get the same optimal time complexity for the channel with multiplicity feedback even if the interval has only size O(dlogd). On the other hand, if we further reduce the size to [Figure presented], then we show that no protocol having time complexity Θ((dlog(n/d))/(logd)) is possible.
Original language | English (US) |
---|---|
Pages (from-to) | 21-33 |
Number of pages | 13 |
Journal | Journal of Computer and System Sciences |
Volume | 119 |
DOIs | |
State | Published - Aug 2021 |
Keywords
- Algorithm
- Distributed
- Group testing
- Limited feedback
- Lower bound
- Multiple-access channel
- Threshold group testing
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics