Dynamic Networks are as fast as static networks (Preliminary Version)
Baruch Awerbuch, Michael Sipser · 1988
This paper gives an efficient simulation to show that dynamic networks are as fast as static ones up to a constant multiplicative factor. That is, any task can be performed in a dynamic asynchronous network essentially as fast as in a static synchronous network. The simulation protocol is based on a new approach, perceiving "locality " as the key to fast adaptation to changes in network topology. The heart of our simulation is a new technique, called a dynamic synchronizer which achieves "local" simulation of a global "clock" in a dynamic asynchronous network. Using this result we obtain improved solutions to a number of well known problems on dynamic networks. It can also be used to improve the solution to certain static network problems. 1 Introduction The Dynamic Asynchronous network, where links may repeatedly fail and recover, is a realistic model of existing commercial communication networks, such the ARPANET [23]. Design and analysis of protocols for such networks is much more...