[TITLE] Deploying Wireless Networks with Beeps (aka Distributed
coloring without sending a single message)
[SPEAKER] Alex Cornejo
[PLACE] 32-G631
[TIME] 1:00PM - 2:30PM
[DATE] March 5th (Fri), 2010

[ABSTRACT]
To highlight the importance of the discreteness of the model we
contrast it against a continuous variant described in
\cite{infocom09}. We present an $\bigO(1)$ time algorithm that
terminates with probability $1$ and assigns an interval of size
$\Omega(T/\Delta)$ that repeats every $T$ time units to every node
of the network. This improves an $\bigO(\log n)$ time algorithm with
the same guarantees from \cite{infocom09}.

Under the more realistic discrete model we present a Las Vegas
algorithm that solves $\Omega(T/\Delta)$-interval coloring in
$\bigO(\log n)$ time with high probability and describe how to adapt
the algorithm for dynamic networks where nodes may join or leave.

For constant degree graphs we prove a lower bound of $\Omega(\log n)$
on the time required to solve interval coloring for this model against
randomized algorithms. This lower bound implies that our algorithm is
asymptotically optimal for constant degree graphs.