[Title] Abstract MAC Layers
[Speaker] Nancy Lynch (MIT)
[Place] 32-G575 *NOTE THE PLACE HAS BEEN CHANGED*
[Time] 4:15PM
[Date] Feb. 24th (Wed), 2010

[Abstract]
In this talk, I will describe recent work that uses Abstract MAC
Layers to develop and analyze algorithms for wireless networks.
These algorithms are intended to run in networks with local radio
broadcast communication, with a variety of possible signal
characteristics.

Current work on wireless network algorithms is complicated by a
diversity of low-level communication assumptions, including
assumptions about message collisions and other forms of interference,
and about how the success of message delivery depends on geographical
distance.  It is hard to understand how the results depend on the
particular communication assumptions.  Moreover, many algorithms use
similar techniques to deal with the same network difficulties.  The
result has been a rather complicated theory.

To simplify matters, we propose using Abstract MAC Layers to mask some
of the complexities of the underlying networks.  For example, we have
defined a layer that provides reliable local broadcast communication,
with timing guarantees stated in terms of abstract delay
functions of the local contention.  We have developed and analyzed
two algorithms over this layer for the important problem of
Multi-Message Broadcast---a simple greedy algorithm and one
that uses regional leaders.  The second of these algorithms extends to
mobile networks.

In work in progress, we are demonstrating how our Abstract MAC Layer
can be implemented using existing methods of probabilistic decay and
network coding.  We are showing how one can use such layers to split
existing algorithms and their analysis into smaller pieces.  And, we
are showing how our layer can be used to solve other problems, such as
implementing a popular dynamic graph model.

The basic Abstract MAC Layer was developed jointly with Fabian
Kuhn and Calvin Newport.  Other collaborators on related projects
include Alex Cornejo, Majid Khabbazian, Darek Kowalski, Saira Viqar,
and Jennifer Welch.