Algorithms and Complexity Seminar

Distributed Computation in Dynamic Networks

Rotem Oshman (MIT)

What is the power of distributed computation in worst-case dynamic networks? In this work we show that in an always-connected but constantly changing network where communication links are controlled by a worst-case adversary, nodes initially know nothing but their own unique identifiers, messages are restricted to O(log n) bits, and nodes do not even know who will receive the messages they broadcast, it is nevertheless possible to compute any function of the nodes' initial states in O(n^2) rounds. In contrast to other models of dynamic computation (e.g., self-stabilizing computation and population protocols), in our model nodes eventually halt and output the result of the computation.

If the network enjoys some degree of stability, we can use it to speed up the computation. We introduce a stability measure called T-interval connectivity, which asserts that in every window of T consecutive rounds, there exists some connected subgraph which remains stable during those T rounds. We show that in T-interval connected networks it is possible to compute any function in O(n + n^2/T) rounds. We also describe lower bounds on the problem of disseminating k pieces of information in a dynamic network.

Joint work with Fabian Kuhn and Nancy Lynch.