  The rise of machine-to-machine communications has rekindled the interest in
random access protocols as a support for a massive number of uncoordinatedly
transmitting devices. The legacy ALOHA approach is developed under a collision
model, where slots containing collided packets are considered as waste.
However, if the common receiver (e.g., base station) is capable to store the
collision slots and use them in a transmission recovery process based on
successive interference cancellation, the design space for access protocols is
radically expanded. We present the paradigm of coded random access, in which
the structure of the access protocol can be mapped to a structure of an
erasure-correcting code defined on graph. This opens the possibility to use
coding theory and tools for designing efficient random access protocols,
offering markedly better performance than ALOHA. Several instances of coded
random access protocols are described, as well as a case study on how to
upgrade a legacy ALOHA system using the ideas of coded random access.
