caa a22 4500 445355093 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00446-011-0135-7 doi (NATIONALLICENCE)springer-10.1007/s00446-011-0135-7 Modeling radio networks [Elektronische Daten] [Calvin Newport, Nancy Lynch] We describe a modeling framework and collection of foundational composition results for the study of probabilistic packet-level distributed algorithms in synchronous radio networks. Existing results in this setting rely on informal descriptions of the channel behavior and therefore lack easy comparability and are prone to error caused by definition subtleties. Our framework rectifies these issues by providing: (1) a method to precisely describe a radio channel as a probabilistic automaton; (2) a mathematical notion of implementing one channel using another channel, allowing for direct comparisons of channel strengths and a natural decomposition of problems into implementing a more powerful channel and solving the problem on the powerful channel; (3) a mathematical definition of a problem and solving a problem; (4) a pair of composition results that simplify the tasks of proving properties about channel implementation algorithms and combining problems with channel implementations. Our goal is to produce a model streamlined for the needs of the radio network algorithms community. Springer-Verlag, 2011 Modeling nationallicence Distributed algorithms nationallicence Radio networks nationallicence Newport Calvin 32-G918, The Stata Center, 32 Vassar St., 02139, Cambridge, MA, USA aut Lynch Nancy 32-G918, The Stata Center, 32 Vassar St., 02139, Cambridge, MA, USA aut Distributed Computing Springer-Verlag 24/2(2011-10-01), 101-118 0178-2770 24:2<101 2011 24 446 https://doi.org/10.1007/s00446-011-0135-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0135-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Newport Calvin 32-G918, The Stata Center, 32 Vassar St., 02139, Cambridge, MA, USA aut NATIONALLICENCE 700 1- Lynch Nancy 32-G918, The Stata Center, 32 Vassar St., 02139, Cambridge, MA, USA aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/2(2011-10-01), 101-118 0178-2770 24:2<101 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer