TY - GEN
T1 - Deterministic contention resolution without collision detection
T2 - 41st IEEE International Conference on Distributed Computing Systems, ICDCS 2021
AU - De Marco, Gianluca
AU - Kowalski, Dariusz R.
AU - Stachowiak, Grzegorz
N1 - Funding Information:
ACKNOWLEDGMENT This paper is supported by Polish National Science Center NCN grant UMO-2017/25/B/ST6/02553 and in part by the NSF Award 2043302.
Publisher Copyright:
© 2021 IEEE.
PY - 2021/7
Y1 - 2021/7
N2 - This paper studies the Contention resolution problem on a shared channel (also known as a multiple access channel). A set of $n$ stations are connected to a common device and are able to communicate by transmitting and listening. Each station may have a message to broadcast. At any round, a transmission is successful if and only if exactly one station is transmitting at that round. Simultaneous transmissions interfere one another and, as a result, the respective messages are lost. The Contention resolution is the fundamental problem of scheduling the transmissions into rounds in such a way that any station delivers successfully its message on the channel. We consider a general dynamic distributed setting. We assume that the stations can join (or be activated on) the channel at arbitrary times (dynamic scenario). This has to be contrasted with the simplified static scenario, in which all stations are assumed to be activated simultaneously. We also assume that the stations are not able to detect whether a collision among simultaneous transmissions occurred (model without collision detection). Finally, there is no global clock in the system: each station measures the time using its own local clock which starts when the station is activated and is possibly out of sync with respect to the other stations. We study non-adaptive deterministic distributed algorithms for the contention resolution problem and assess their efficiency both in terms of channel utilization (also called throughput) and energy consumption. While this topic has been quite extensively examined for randomized algorithms, this is, to the best of our knowledge, the first paper to discuss to which extent deterministic contention resolution algorithms can be efficient in terms of both channel utilization and energy consumption. Our results imply an exponential separation gap between static and dynamic setting with respect to channel utilization. We also show that the knowledge of the number of participating stations k (or an upper bound on it) has a substantial impact on the energy consumption.
AB - This paper studies the Contention resolution problem on a shared channel (also known as a multiple access channel). A set of $n$ stations are connected to a common device and are able to communicate by transmitting and listening. Each station may have a message to broadcast. At any round, a transmission is successful if and only if exactly one station is transmitting at that round. Simultaneous transmissions interfere one another and, as a result, the respective messages are lost. The Contention resolution is the fundamental problem of scheduling the transmissions into rounds in such a way that any station delivers successfully its message on the channel. We consider a general dynamic distributed setting. We assume that the stations can join (or be activated on) the channel at arbitrary times (dynamic scenario). This has to be contrasted with the simplified static scenario, in which all stations are assumed to be activated simultaneously. We also assume that the stations are not able to detect whether a collision among simultaneous transmissions occurred (model without collision detection). Finally, there is no global clock in the system: each station measures the time using its own local clock which starts when the station is activated and is possibly out of sync with respect to the other stations. We study non-adaptive deterministic distributed algorithms for the contention resolution problem and assess their efficiency both in terms of channel utilization (also called throughput) and energy consumption. While this topic has been quite extensively examined for randomized algorithms, this is, to the best of our knowledge, the first paper to discuss to which extent deterministic contention resolution algorithms can be efficient in terms of both channel utilization and energy consumption. Our results imply an exponential separation gap between static and dynamic setting with respect to channel utilization. We also show that the knowledge of the number of participating stations k (or an upper bound on it) has a substantial impact on the energy consumption.
KW - Contention resolution
KW - Deterministic algorithm
KW - Energy consumption
KW - Throughput
UR - http://www.scopus.com/inward/record.url?scp=85117141499&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85117141499&partnerID=8YFLogxK
U2 - 10.1109/ICDCS51616.2021.00100
DO - 10.1109/ICDCS51616.2021.00100
M3 - Conference contribution
AN - SCOPUS:85117141499
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 1009
EP - 1019
BT - Proceedings - 2021 IEEE 41st International Conference on Distributed Computing Systems, ICDCS 2021
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 7 July 2021 through 10 July 2021
ER -
