caa a22 4500 445354968 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00446-010-0118-0 doi (NATIONALLICENCE)springer-10.1007/s00446-010-0118-0 The abstract MAC layer [Elektronische Daten] [Fabian Kuhn, Nancy Lynch, Calvin Newport] A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specific channel behavior. Concrete implementations of the abstract MAC layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specific radio network under consideration. To illustrate this approach, we use the abstract MAC layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast in which multiple messages can originate at different times and locations in the network. We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks. Springer-Verlag, 2010 Wireless networks nationallicence Abstraction nationallicence Medium access control nationallicence Broadcast nationallicence Kuhn Fabian University of Lugano (USI), Lugano, Switzerland aut Lynch Nancy MIT CSAIL, Cambridge, MA, USA aut Newport Calvin MIT CSAIL, Cambridge, MA, USA aut Distributed Computing Springer-Verlag 24/3-4(2011-11-01), 187-206 0178-2770 24:3-4<187 2011 24 446 https://doi.org/10.1007/s00446-010-0118-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-010-0118-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kuhn Fabian University of Lugano (USI), Lugano, Switzerland aut NATIONALLICENCE 700 1- Lynch Nancy MIT CSAIL, Cambridge, MA, USA aut NATIONALLICENCE 700 1- Newport Calvin MIT CSAIL, Cambridge, MA, USA aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/3-4(2011-11-01), 187-206 0178-2770 24:3-4<187 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer