\reviewtitle{Spatial Gossip and Resource Location Protocols}
\reviewlable{kempe01spatial}
\reviewauthor{David Kempe, Jon Kleinberg, Alan Demers}

The authors elaborate on an algorithms for gossip originally developed by
Demers in an earlier paper.  The algorithm guarantees that new
information will spread to nodes at distance d with high probability
in $O(log^{1+\epsilon} d)$ time steps.

Imagine an $\sqrt{N} x \sqrt{N}$ region of a plane with sensors
uniformly dispersed.  The authors assume some underlying protocol that
allows point-to-point communication between any two nodes in a single
step, regardless of the distance separating them on the plane.  They
offer two extreme protocols (and then propose theirs as a hybrid):
\begin{description}
\item[Uniform Gossip] each node $u$ chooses a node $v$ uniformly at
random and forwards the message to $v$.  All nodes receive message $m$
within $O(log N) steps.
\item[Neighbor Flooding] each node $u$ chooses a neighbor $v$ and
forwards $m$ to it.  This is repeated in round-robin fashion.  Nodes
at distance $d$ will receive copy of a message in $O(d)$ steps, but it
takes $\Theta(\sqrt{N})$ steps to reach all nodes.
\end{description}

The authors note that information passes only from $u$ to $v$ --- it
is a push model of communication.  This seems a requirement when nodes
are sensors and are broadcasting to a radius.

They make a nice distinction between the algorithm by which nodes
choose which other nodes to communicate with and the protocol that is
built on top of the algorithm that determines the contents of the
messages that are sent.

The authors present an algorithm equivalent to that presented in
Demers.  Fix an exponent $\rho$ where $1 < \rho 2 $ and $D$ is the
diameter of the network (I think).  In each round $u$ chooses to
communicate with $v$ with probability proportional to
$d_{u,v}^{-D\rho}$ where $d_{u,v}$ is the distance between $u$ and
$v$.

I am unclear what scale these numbers are.  For example, if $D$ is
larger than 10 and the minimum distance between each node is 1, then
the chance of talking to a node distance 2 away is pretty tiny (no
matter what $\rho$ is).

They look at the resource location problem as monotonic or
non-monotonic.  When monotonic, a resource does not depart from a node
once there, so once you as a node have located it, you don't need to
do anything else.  The non-monotonic resource-location problem is
harder because resources do disappear.

Related work:
Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin.
Directed Diffusion: A Scalable and Robust Communication Paradigm for
Sensor Networks, MobiCOM 2000, Boston, MA, Aug 2000