  This paper considers a random access system where each sender can be in two
modes of operation, active or not active, and where the set of active users is
available to a common receiver only. Active transmitters encode data into
independent streams of information, a subset of which are decoded by the
receiver, depending on the value of the collective interference. The main
contribution is to present an information-theoretic formulation of the problem
which allows us to characterize, with a guaranteed gap to optimality, the rates
that can be achieved by different data streams.
  Our results are articulated as follows. First, we exactly characterize the
capacity region of a two-user system assuming a binary-expansion deterministic
channel model. Second, we extend this result to a two-user additive white
Gaussian noise channel, providing an approximate characterization within
$\sqrt{3}/2$ bit of the actual capacity. Third, we focus on the symmetric
scenario in which users are active with the same probability and subject to the
same received power constraint, and study the maximum achievable expected
sum-rate, or throughput, for any number of users. In this case, for the
symmetric binary expansion deterministic channel (which is related to the
packet collision model used in the networking literature), we show that a
simple coding scheme which does not employ superposition coding achieves the
system throughput. This result also shows that the performance of slotted ALOHA
systems can be improved by allowing encoding rate adaptation at the
transmitters. For the symmetric additive white Gaussian noise channel, we
propose a scheme that is within one bit of the system throughput for any value
of the underlying parameters.
