TY - GEN
T1 - Adversarial queuing on the multiple-access channel
AU - Chlebus, Bogdan S.
AU - Kowalski, Dariusz R.
AU - Rokicki, Mariusz A.
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2006
Y1 - 2006
N2 - We consider broadcasting on the multiple-access channel when packets are injected continuously. Multiple-access channel is a synchronous system with the properties that a single transmission at a round delivers the message to all nodes, while multiple simultaneous transmissions result in a conflict which prevents delivering messages to any among the recipients. The traditional approach to dynamic broadcasting has been concerned with stability of protocols under suitable stochastic assumptions about injection rates. We study deterministic protocols competing against adversaries restricted by injection rate and burstiness of traffic. Stability means that the number of packets in queues is bounded by a constant in any execution, for a given number of stations, protocol, and adversary. Strong stability denotes the property that the number of queued packets is proportional to the burstiness of traffic, that is, the maximum number of packets an adversary may inject simultaneously. There are three natural classes of protocols we consider. The weakest acknowledgement-based protocols have a station rely on its local clock and on a feedback from the channel during its own attempts of transmissions. Full-sensing protocols allow a station to rely on a global clock and to store the history of all the previous successes/failures of transmissions in the course of an execution. A station running an adaptive protocol can rely on a global clock, may add control bits to be piggybacked on messages, and may store the complete history of the feedback from the channel during an execution. It turns out that there is no adaptive broadcast protocol stable for the injection rate λ = 1 for the multiple-access channel with at least n ≥ 4 stations, even when collision detection is available. We show that a simple full-sensing protocol is universally stable, which means it can handle any constant injection rate λ < 1 in a stable manner. A more involved full-sensing protocol is shown to be both universally stable and strongly-stable for injec tion rate ρ(n) ≤ 1/d lg2 n, where d > 0 is a sufficiently large constant and n is the number of stations. We show that there is an acknowledgement-based protocol that is strongly stable for injection rate ρ(n) ≤ 1/dn lg2 n, for a sufficiently large constant d > 0. Regarding the stability of acknowledgement-based protocols, we show that no such a protocol is stable for injection rate ρ(n) > 2/1+lg n. This implies that there are no universally stable acknowledgement-based protocols. We show that when collision detection is available, then a simple full-sensing protocol is both universally stable and strongly stable for injection rate ρ(n) ≤ 1/2 lg n. As a complementary fact, we prove that no adaptive protocol for a channel with collision detection can be strongly stable for the injection rate that satisfies ρ(n) = ω(1/log n). This shows that the protocol we give is optimal with respect to injection rates it handles in a strongly stable manner.
AB - We consider broadcasting on the multiple-access channel when packets are injected continuously. Multiple-access channel is a synchronous system with the properties that a single transmission at a round delivers the message to all nodes, while multiple simultaneous transmissions result in a conflict which prevents delivering messages to any among the recipients. The traditional approach to dynamic broadcasting has been concerned with stability of protocols under suitable stochastic assumptions about injection rates. We study deterministic protocols competing against adversaries restricted by injection rate and burstiness of traffic. Stability means that the number of packets in queues is bounded by a constant in any execution, for a given number of stations, protocol, and adversary. Strong stability denotes the property that the number of queued packets is proportional to the burstiness of traffic, that is, the maximum number of packets an adversary may inject simultaneously. There are three natural classes of protocols we consider. The weakest acknowledgement-based protocols have a station rely on its local clock and on a feedback from the channel during its own attempts of transmissions. Full-sensing protocols allow a station to rely on a global clock and to store the history of all the previous successes/failures of transmissions in the course of an execution. A station running an adaptive protocol can rely on a global clock, may add control bits to be piggybacked on messages, and may store the complete history of the feedback from the channel during an execution. It turns out that there is no adaptive broadcast protocol stable for the injection rate λ = 1 for the multiple-access channel with at least n ≥ 4 stations, even when collision detection is available. We show that a simple full-sensing protocol is universally stable, which means it can handle any constant injection rate λ < 1 in a stable manner. A more involved full-sensing protocol is shown to be both universally stable and strongly-stable for injec tion rate ρ(n) ≤ 1/d lg2 n, where d > 0 is a sufficiently large constant and n is the number of stations. We show that there is an acknowledgement-based protocol that is strongly stable for injection rate ρ(n) ≤ 1/dn lg2 n, for a sufficiently large constant d > 0. Regarding the stability of acknowledgement-based protocols, we show that no such a protocol is stable for injection rate ρ(n) > 2/1+lg n. This implies that there are no universally stable acknowledgement-based protocols. We show that when collision detection is available, then a simple full-sensing protocol is both universally stable and strongly stable for injection rate ρ(n) ≤ 1/2 lg n. As a complementary fact, we prove that no adaptive protocol for a channel with collision detection can be strongly stable for the injection rate that satisfies ρ(n) = ω(1/log n). This shows that the protocol we give is optimal with respect to injection rates it handles in a strongly stable manner.
KW - Adversarial queuing
KW - Broadcast
KW - Continuous packet injection
KW - Multiple-access channel
KW - Stability
UR - http://www.scopus.com/inward/record.url?scp=33748697400&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748697400&partnerID=8YFLogxK
U2 - 10.1145/1146381.1146398
DO - 10.1145/1146381.1146398
M3 - Conference contribution
AN - SCOPUS:33748697400
SN - 1595933840
SN - 9781595933843
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 92
EP - 101
BT - Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing 2006
PB - Association for Computing Machinery (ACM)
T2 - 25th Annual ACM Symposium on Principles of Distributed Computing 2006
Y2 - 23 July 2006 through 26 July 2006
ER -