On the capacity of infinite population multiple access protocols

We present bounds on the maximum channel utilization (with finite average delay) of synchronous multiple access communications protocols serving an infinite population of homogeneous stations. Messages arrive to the system as a series of independent Bernoulli trials in discrete time, with probability p of an arrival at each arrival point (the Poisson limit is explicitly included) and are then randomly distributed among the stations. Pippenger showed that the channel utilization cannot exceed <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ξₚ</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ξₗ=1</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">limp → 0 ξₚ ≈ 0.744</tex> . Using a "helpful genie" argument, we find the exact capacity for all <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p ≥ 0.568</tex> (where we find optimal protocols that obey first-come first-served); for smaller values of p, we present an improved upper bound that decreases monotonically to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">≈ 0.6731</tex> in the Poisson limit as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p → 0</tex> .