Distributed computation in dynamic networks

TLDR

The model represents mobile and wireless networks with unpredictable communication, using T‑interval connectivity to guarantee a connected spanning subgraph every T rounds. The study investigates distributed computation in dynamic networks that change continually, aiming for correctness and termination without assuming eventual stability. The authors analyze a worst‑case adversarial model where each round’s links are chosen arbitrarily and nodes lack neighbor knowledge, and introduce T‑interval connectivity to enable algorithm design under continual change.

Abstract

In this paper we investigate distributed computation in dynamic networks in which the network topology changes from round to round. We consider a worst-case model in which the communication links for each round are chosen by an adversary, and nodes do not know who their neighbors for the current round are before they broadcast their messages. The model captures mobile networks and wireless networks, in which mobility and interference render communication unpredictable. In contrast to much of the existing work on dynamic networks, we do not assume that the network eventually stops changing; we require correctness and termination even in networks that change continually. We introduce a stability property called T -interval connectivity (for T >= 1), which stipulates that for every T consecutive rounds there exists a stable connected spanning subgraph. For T = 1 this means that the graph is connected in every round, but changes arbitrarily between rounds.