Show simple item record

dc.contributor.advisorNancy Lynchen_US
dc.contributor.authorKuhn, Fabianen_US
dc.contributor.authorNewport, Calvinen_US
dc.contributor.authorLynch, Nancyen_US
dc.contributor.otherTheory of Computationen_US
dc.date.accessioned2009-05-11T17:30:04Z
dc.date.available2009-05-11T17:30:04Z
dc.date.issued2009-05-11
dc.identifier.urihttp://hdl.handle.net/1721.1/45515
dc.description.abstractA 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 \emph{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 any number of messages arrive at any processes at any times.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.en_US
dc.format.extent27 p.en_US
dc.language.isoen
dc.relation.ispartofseriesMIT-CSAIL-TR-2009-021
dc.relation.replacesMIT-CSAIL-TR-2009-009
dc.relation.urihttp://hdl.handle.net/1721.1/44620
dc.subjectnetwork modelingen_US
dc.subjectmobile networksen_US
dc.subjectwireless networksen_US
dc.subjectmedium-acccess protocolsen_US
dc.titleThe Abstract MAC Layeren_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record