| Adapting to Asynchronous Dynamic Networks (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Baruch Awerbuch Boaz Patt-Shamir y David Peleg z Michael Saks x Abstract The computational power of different communication models is a fundamental question in the theory of distributed computation. For example, in the synchronous model messages are assumed to be delivered within one time unit, whereas in the asynchronous model message delays may be arbitrary. Another important parameter of the model is the assumptions about the topology. In the dynamic topology model, links are assumed to crash and recover dynamically, but their status is known to the incident node processors. A meaningful computation can be carried out if the topology stabilizes for a sufficiently long period. 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 delay... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||