Title: Adaptive rumour spreading
| Speaker: | Neil Olver |
| Affiliation: | VU University Amsterdam and CWI |
| Room: | MC 6486 |
Abstract:
We
consider
the
following
problem.
We
have
a
piece
of
information
that
we
wish
to
disseminate
throughout
a
population.
It
costs
us
money
to
directly
give
someone
the
information,
but
the
information
also
spreads
randomly
through
the
population
(according
to
a
simple
epidemic
model).
Our
goal
is
to
ensure
that
everyone
has
the
information
by
a
given
deadline
time,
while
spending
the
least
amount
of
money.
In
particular,
we
are
interested
in
the
question
of
how
much
it
can
help
to
track
the
spread
of
the
information
and
adaptively
adjust
our
dissemination
strategy
based
on
this
knowledge,
as
opposed
to
informing
people
only
at
the
beginning
and
at
the
deadline.
Our
main
result
concerns
a
bound
on
this
"adaptivity
gap"
in
the
homogeneous
case
where
interactions
between
pairs
of
users
all
occur
at
the
same
rate.
The
primary
(though
not
the
only)
motivation
for
this
problem
comes
from
"opportunistic"
communication,
a
popular
topic
in
the
networking
community.
The
idea
is
that
a
cellular
network
is
augmented
with
an
ad-hoc
network
formed
by
users
who
are
close
together,
the
goal
being
to
substantially
reduce
the
usage
of
the
cellular
network
when
sending
information
of
common
interest
(e.g.,
real-time
traffic
data).
(Joint
work
with
Alberto
Vera
Azócar,
Jose
Correa
and
Marcos
Kiwi.)