Distributed Computation in Dynamic Networks : Technical Report

Download Now Date Added: Nov 2009
Format: PDF

In this paper, the authors investigate distributed computation in dynamic networks in which the network topology changes from round to round. They 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 allows the study of the fundamental computation power of dynamic networks. In particular, it 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, they do not assume that the network eventually stops changing; they require correctness and termination even in networks that change continually.