Abstract:
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.
