Show simple item record

dc.contributor.advisorNancy Lynch
dc.contributor.authorLynch, Nancyen_US
dc.contributor.authorNewport, Calvinen_US
dc.contributor.otherTheory of Computationen_US
dc.date.accessioned2009-06-05T15:30:06Z
dc.date.available2009-06-05T15:30:06Z
dc.date.issued2009-06-04
dc.identifier.urihttp://hdl.handle.net/1721.1/45553
dc.description.abstractWe describe a modeling framework and collection of foundational composition results for the study of probabilistic 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.en_US
dc.format.extent21 p.en_US
dc.relation.ispartofseriesMIT-CSAIL-TR-2009-023
dc.titleModeling Radio Networksen_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record