[Speaker]: Rotem Oshma (MIT)
[Title]: Data Aggregation in Dynamic Networks
[Date]: Oct. 9th (Fri)
[Time]: 1:00 - 2:30PM
[Place]: Bldg. 32 (Stata), G631


[Abstract]:
In this talk I will describe some preliminary results on computation in
dynamic graphs. A dynamic graph is a graph in which the vertex set is
static, but the edge set can change completely from one round to the next.
We assume that the graph is connected in every round, but the neighborhood
of each node can change arbitrarily from round to round. We generally assume
that the nodes know nothing about the network, not even an upper bound on
its size. The intention is to capture mobile wireless ad-hoc networks with
an unpredictable motion pattern, or more generally, broadcast networks with
unreliable links.

Surprisingly, even in this weak model, nodes can efficiently compute any
function of their initial states. If message size is not restricted, we show
that the computation can be done in O(n) time, which is asymptotically
optimal. When the size of messages is restricted to O(log(n)), we give a
deterministic algorithm that computes any function in O(n^2) time. We do not
know if this is algorithm is optimal.

We also consider more stable dynamic graphs. We define a measure of
stability called T-interval connectivity, which I will describe in the talk,
and show that in T-interval connected graphs, any function can be computed
in O(n^2 / T) time.