Contention Resolution with Message Deadlines

In the contention-resolution problem, multiple players contend for access to a shared resource. Contention resolution is used in wireless networks, where messages must be transmitted on a shared communication channel. When two or more messages are transmitted at the same time, a collision occurs, and none of the transmissions succeed. Much of the theoretical work on contention resolution has focused on efficiently resolving collisions in order to obtain throughput guarantees. However, in modern-day networks, not all traffic is treated equally. Instead, messages are often handled according to a notion of priority. While throughput remains an important metric, it fails to capture this increasingly-common scenario of traffic prioritization. Motivated by this concern, we design a contention-resolution algorithm where messages have delivery deadlines. Unit-length messages dynamically arrive over time, each with a corresponding delivery deadline that demarcates a window of time wherein the message must be transmitted successfully. We consider inputs that have a feasible schedule, even if message sizes increase by a constant factor. In this setting, we provide an algorithm which guarantees that each message succeeds by its deadline with high probability in its window size.