We study deterministic broadcasting on multiple access channels when packets are injected continuously. The quality of service is considered in the framework of adversarial queuing. An adversary is determined by injection rate and burstiness, the latter denoting the number of packets that can be injected simultaneously in a round. We consider only injection rates that are less than 1. A protocol is stable when the numbers of packets in queues stay bounded at all rounds, and it is of fair latency when waiting times of packets in queues are O (burstiness/rate). For channels with collision detection, we give a full-sensing protocol of fair latency for injection rates that are at most 1 2(⌈lg n ⌉ + 1), where n is the number of stations, and show that fair latency is impossible to achieve for injection rates that are ω (1 log n ). For channels without collision detection, we present a full-sensing protocol of fair latency for injection rates that are at most 1 c lg 2 n , for some c > 0. We show that there exists an acknowledgment-based protocol that has fair latency for injection rates that are at most 1 cn lg 2 n , for some c > 0, and develop an explicit acknowledgment-based protocol of fair latency for injection rates that are at most 1 27 n 2 ln n . Regarding impossibility to achieve just stability by restricted protocols, we prove that no acknowledgment-based protocol can be stable for injection rates larger than 3 1 + lg n .

We study broadcasting on multiple access channels by deterministic distributed protocols. Data arrivals are governed by an adversary. The power of the adversary is constrained by the average rate of data injection and a bound on the number of different packets that can be injected in one round. The injection rate is at most 1, which forbids the adversary from overloading the channel. We consider a number of deterministic protocols. For each of them we give an upper bound on the worst-case packet latency, as a function of the constraints imposed on the adversary. We present results of experiments by simulations to compare packet latency of the deterministic protocols and of backoff-type randomized protocols. The experiments are carried out in a simulation environment that captures the burstiness of data injection and the resulting traffic by admissibility condition defined by the fraction of active stations and the rate of changing the status of active versus passive among the stations.

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 injection rate ρ (n) ≤ 1over>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 d lg2 n, for a sufficiently large constant d0. 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 lgn. 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.