In this paper, we analyze the stochastic behavior of backoff protocols
for multiple access channels such as the Ethernet. In particular, we
prove that binary exponential backoff is unstable if the arrival rate
of new messages at each stations is lambda/N for any lambda > 1/2 and
the number of stations N is sufficiently large. For small N, we prove
that lambda greater than or equal to lambda(0)+1/4N-2 implies instabil
ity, where lambda(0) approximate to .567. More importantly, we also pr
ove that any superlinear polynomial backoff protocol (e.g., quadratic
backoff is stable for any set of arrival rates that sum to less than o
ne and any number of stations. The results significantly extend the pr
evious work in the area and provide the first examples of acknowledgme
nt-based protocols known to be stable for a nonnegligible overall arri
val rate distributed over an arbitrarily large number of stations. The
results also disprove a popular assumption that exponential backoff i
s the best choice among acknowledgment-based protocols for systems wit
h large overall arrival rates. Finally, we prove that any linear or su
blinear backoff protocol is unstable if the arrival rate at each stati
on is lambda/N for any fixed lambda and sufficiently large N.