In this paper we show that the model of asynchronous, dynamic-topology network is equivalent, up to polylogarithmic factors, to the synchronous, static (i.e., fixed-topology) model. Specifically, we present a simulation methodology of synchronous static protocols that can withstand arbitrary link delays and changing topology at the expense of only polylogarithmic blowup in the running time, the number of messages, and the space requirement. Previous methods entailed a linear blowup in at least one of these resources.

The generality of our method is demonstrated by a series of improvements for important applications, including Breadth First Search, computing compact efficient routing tables, and packet routing on asynchronous networks.

Click here