I. Introduction
An access reservation protocol is instrumental in any multi-user communication system in order to enable users to connect asynchronously or transmit intermittently [1]. The Long Term Evolution (LTE) system [2] uses an access protocol consisting of two phases: a contention phase, where each user contends by activating a particular reservation token chosen from the set of available tokens; and a data phase, where the reservation tokens (i.e., token holders) detected by the base station (BS) get assigned resources for the data transfer. The asynchronous access in LTE gains importance as the needs to support traffic related to Machine-to-Machine (M2M) communications gets increasingly important. In many cases, M2M traffic is a real-time traffic, where data packets become obsolete after a deadline and thus may undergo only a single contention and data phases, i.e., unsuccessful transmissions cannot be postponed for later contention or scheduled to a later data phase.