Stephan Holzer: A Local Broadcast Layer for the SINR Network Model

We present the first algorithm to implement an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that efficient SINR implementations are not possible for the standard absMAC specification. We modify that specification to an ”approximate” version that better suits the SINR model. We give an efficientalgorithm to implement the modified specification, and use it to derive efficient algorithms for higher-level problems of global broadcast and consensus.