Listening Efficient Contention Resolution for Semi-batch Arrivals without Collision Detection

Contention resolution is a problem that captures the difficulty of coordinating multiple processes to access a shared resource. A common way to model this problem is to assume n nodes arrive over time, each with a messages that it intends to transmit. In each round, every node can try to broadcast its message, and a node succeeds if it broadcasts alone. Nodes that do not broadcast can listen on the channel to obtain feedback regarding whether a successful transmission has occurred. Under above assumptions, recent results show that all n nodes can succeed within Θ(n) rounds, which is optimal; moreover, each node attempts broadcast at most O(polylog(n)) times before succeeding. However, all previous work attaining such strong guarantees assume channel feedback is free, and it remains unknown whether similar results can be obtained when listening cost are also taken into consideration. Such algorithms would be beneficial for distributed systems in which querying channel feedback incurs non-negligible cost, such as wireless networks.