  Consider a massive random access scenario in which a small set of $k$ active
users out of a large number of $n$ potential users need to be scheduled in
$b\ge k$ slots. What is the minimum common feedback to the users needed to
ensure that scheduling is collision-free? Instead of a naive scheme of listing
the indices of the $k$ active users in the order in which they should transmit,
at a cost of $k\log(n)$ bits, this paper shows that for the case of $b=k$, the
rate of the minimum fixed-length common feedback code scales only as $k
\log(e)$ bits, plus an additive term that scales in $n$ as $\Theta \left(\log
\log(n) \right)$ for fixed $k$. If a variable-length code can be used, assuming
uniform activity among the users, the minimum average common feedback rate
still requires $k \log(e)$ bits, but the dependence on $n$ can be reduced to
$O(1)$. When $b>k$, the number of feedback bits needed for collision-free
scheduling can be significantly further reduced. Moreover, a similar scaling on
the minimum feedback rate is derived for the case of scheduling $m$ users per
slot, when $k \le mb$. The problem of constructing a minimum collision-free
feedback scheduling code is connected to that of constructing a perfect hashing
family, which allows practical feedback scheduling codes to be constructed from
perfect hashing algorithms.
