  We consider deterministic distributed broadcasting on multiple access
channels in the framework of adversarial queuing. Packets are injected
dynamically by an adversary that is constrained by the injection rate and the
number of packets that may be injected simultaneously; the latter we call
burstiness. The maximum injection rate that an algorithm can handle in a stable
manner is called the throughput of the algorithm. We develop an algorithm that
achieves throughput $1$ for any number of stations against leaky-bucket
adversaries. The algorithm has $O(n^2+\text{burstiness})$ packets queued
simultaneously at any time, where $n$ is the number of stations; this upper
bound is proved to be best possible. An algorithm is called fair when each
packet is eventually broadcast. We show that no algorithm can be both stable
and fair for a system of at least two stations against leaky-bucket
adversaries. We study in detail small systems of exactly two and three stations
against window adversaries to exhibit differences in quality of broadcast among
classes of algorithms. For two stations, we show that fair latency can be
achieved by a full sensing algorithm, while there is no stable acknowledgment
based algorithm. For three stations, we show that fair latency can be achieved
by a general algorithm, while no full sensing algorithm can be stable. Finally,
we show that algorithms that either are fair or do not have the queue sizes
affect the order of transmissions cannot be stable in systems of at least four
stations against window adversaries.
