  This paper shows how to achieve contention resolution on a shared
communication channel using only a small number of channel accesses -- both for
listening and sending -- and the resulting algorithm is resistant to
adversarial noise.
  The shared channel operates over a sequence of synchronized time slots, and
in any slot agents may attempt to broadcast a packet. An agent's broadcast
succeeds if no other agent broadcasts during that slot. If two or more agents
broadcast in the same slot, then the broadcasts collide and both broadcasts
fail. An agent listening on the channel during a slot receives ternary
feedback, learning whether that slot had silence, a successful broadcast, or a
collision. Agents are (adversarially) injected into the system over time. The
goal is to coordinate the agents so that each is able to successfully broadcast
its packet.
  A contention-resolution protocol is measured both in terms of its throughput
and the number of slots during which an agent broadcasts or listens. Most prior
work assumes that listening is free and only tries to minimize the number of
broadcasts.
  This paper answers two foundational questions. First, is constant throughput
achievable when using polylogarithmic channel accesses per agent, both for
listening and broadcasting? Second, is constant throughput still achievable
when an adversary jams some slots by broadcasting noise in them? Specifically,
for $N$ packets arriving over time and $J$ jammed slots, we give an algorithm
that with high probability in $N+J$ guarantees $\Theta(1)$ throughput and
achieves on average $O(\texttt{polylog}(N+J))$ channel accesses against an
adaptive adversary. We also have per-agent high-probability guarantees on the
number of channel accesses -- either $O(\texttt{polylog}(N+J))$ or $O((J+1)
\texttt{polylog}(N))$, depending on how quickly the adversary can react to what
is being broadcast.

Distributed, Parallel, and Cluster Computing