TY - GEN
T1 - Contention Resolution Without Collision Detection
T2 - 36th International Symposium on Distributed Computing, DISC 2022
AU - De Marco, Gianluca
AU - Kowalski, Dariusz R.
AU - Stachowiak, Grzegorz
N1 - Funding Information:
Funding Dariusz R. Kowalski: partially supported by the National Science Foundation grant No. 2131538 and the Polish National Science Center (NCN) grant UMO-2017/25/B/ST6/02553.
Publisher Copyright:
© Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak.
PY - 2022/10/1
Y1 - 2022/10/1
N2 - A shared channel, also called a multiple access channel, is among the most popular and widely studied models of communication in distributed computing. An unknown number of stations (potentially unbounded) is connected to the channel and can communicate by transmitting and listening. A message is successfully transmitted on the channel if and only if there is a unique transmitter at that time; otherwise the message collides with some other transmission and nothing is sensed by the participating stations. We consider the general framework without collision detection and in which any participating station can join the channel at any moment. The contention resolution task is to let each of the contending stations to broadcast successfully its message on the channel. In this setting we present the first algorithm which exhibits asymptotically optimal Θ(1) throughput and only an O(log k) energy cost, understood as the maximum number of transmissions performed by a single station (where k is the number of participating stations, initially unknown). We also show that such efficiency cannot be reproduced by non-adaptive algorithms, i.e., whose behavior does not depend on the channel history (for example, classic backoff protocols). Namely, we show that non-adaptive algorithms cannot simultaneously achieve throughput Ω (1/polylog (k)) and energy O (log2 k/(log log k)2).
AB - A shared channel, also called a multiple access channel, is among the most popular and widely studied models of communication in distributed computing. An unknown number of stations (potentially unbounded) is connected to the channel and can communicate by transmitting and listening. A message is successfully transmitted on the channel if and only if there is a unique transmitter at that time; otherwise the message collides with some other transmission and nothing is sensed by the participating stations. We consider the general framework without collision detection and in which any participating station can join the channel at any moment. The contention resolution task is to let each of the contending stations to broadcast successfully its message on the channel. In this setting we present the first algorithm which exhibits asymptotically optimal Θ(1) throughput and only an O(log k) energy cost, understood as the maximum number of transmissions performed by a single station (where k is the number of participating stations, initially unknown). We also show that such efficiency cannot be reproduced by non-adaptive algorithms, i.e., whose behavior does not depend on the channel history (for example, classic backoff protocols). Namely, we show that non-adaptive algorithms cannot simultaneously achieve throughput Ω (1/polylog (k)) and energy O (log2 k/(log log k)2).
KW - Contention resolution
KW - Energy consumption
KW - Lower bound
KW - Randomized algorithms
KW - Shared channel
KW - Throughput
UR - http://www.scopus.com/inward/record.url?scp=85140921238&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85140921238&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2022.17
DO - 10.4230/LIPIcs.DISC.2022.17
M3 - Conference contribution
AN - SCOPUS:85140921238
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th International Symposium on Distributed Computing, DISC 2022
A2 - Scheideler, Christian
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 25 October 2022 through 27 October 2022
ER -