An Exact Implementation of the Abstract MAC Layer via Carrier Sensing in Dynamic Networks

In this paper, we present the first algorithm to precisely implement the abstract MAC (absMAC) layer under the physical SINR model in dynamic networks. The absMac layer, first presented by (Kuhn et al., 2009), provides reliable local broadcast communications, with timing guarantees stated in terms of a collection of abstract delay functions, based on which high-level algorithms can be designed, independent of specific channel behaviors. The implementation of absMAC requires the design of a distributed algorithm for the local broadcast communication primitives over a particular communication model that defines concrete channel behaviors, and the objective is to minimize the bounds of the abstract delay functions. Halldórsson et al. (2015) showed that under the standard SINR model (synchronous communications without physical carrier sensing or location information), there exist no efficient exact implementations. In this work, we demonstrate that physical carrier sensing, a commonly seen function performed by wireless devices, can help get efficient exact implementation algorithms. Specifically, we propose an algorithm that precisely implements the absMAC layer under the SINR model in dynamic networks. The algorithm provides asymptotically optimal bounds for both acknowledgement and progress functions defined in the absMAC layer. Our algorithm leads to many new faster algorithms for solving high-level problems under the SINR model in dynamic networks. We demonstrate this by exemplifying problems of Consensus, Multi-Message Broadcast, and Single-Message Broadcast. It deserves to point out that our implementation algorithm is designed based on an optimal algorithm for a General Local Broadcast (GLB) problem, which takes the number of distinct messages into consideration for the first time. The GLB algorithm can handle many communication scenarios apart from those defined in the absMAC layer. Simulation results show that our proposed algorithms perform well in reality.