Adversarial queuing on the multiple-access channel

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 lg² 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 lg² 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.