  This paper focuses on the contention resolution problem on a shared
communication channel that does not support collision detection. A shared
communication channel is a multiple access channel, which consists of a
sequence of synchronized time slots. Players on the channel may attempt to
broadcast a packet (message) in any time slot. A player's broadcast succeeds if
no other player broadcasts during that slot. If two or more players broadcast
in the same time slot, then the broadcasts collide and both broadcasts fail.
The lack of collision detection means that a player monitoring the channel
cannot differentiate between the case of two or more players broadcasting in
the same slot (a collision) and zero players broadcasting. In the
contention-resolution problem, players arrive on the channel over time, and
each player has one packet to transmit. The goal is to coordinate the players
so that each player is able to successfully transmit its packet within
reasonable time. However, the players can only communicate via the shared
channel by choosing to either broadcast or not. A contention-resolution
protocol is measured in terms of its throughput (channel utilization). Previous
work on contention resolution that achieved constant throughput assumed that
either players could detect collisions, or the players' arrival pattern is
generated by a memoryless (non-adversarial) process. The foundational question
answered by this paper is whether collision detection is a luxury or necessity
when the objective is to achieve constant throughput. We show that even without
collision detection, one can solve contention resolution, achieving constant
throughput, with high probability.
