TY - GEN

T1 - Adapting to asynchronous dynamic networks

AU - Awerbuch, Baruch

AU - Patt-Shamir, Boaz

AU - Peleg, David

AU - Saks, Michael

N1 - Funding Information:
In this paper we show that the model of asynchronous, dynamic-topology network is equivalent, up to polylogarith-mic 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 *Dept. of Mathematics and Lab. for Computer Science, MIT, Cambridge, MA 02139. Supported by Air Force Contract TNDGAFOSR-86-O078, ARO contract DAAL03-86-K-0171, NSF contractCCR8611442,andaspecialgrantfrom IBM. tLab. for Computer Science, MIT, Cambridge, MA 02139. Supported by ONR contract NOO014-85-K-0168, by NSF grants CCR-8915206, and by DARPA contracts NOO014-89-J-1988. t Department of Applied Mathematics, The Weizmann Institute, Rehovot 76100, Israel. Supported in part by an Allen Fellowship, by a Bantrelt Fellowship and by a Walter and Elise Haas Career Development Award. $RutgersUniversity andUCSD.SupportedinpartbyNSFcon-tract CCR-8911388.

PY - 1992/7/1

Y1 - 1992/7/1

N2 - 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 polylogarith-mic 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.

AB - 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 polylogarith-mic 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.

UR - http://www.scopus.com/inward/record.url?scp=0026971188&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026971188&partnerID=8YFLogxK

U2 - 10.1145/129712.129767

DO - 10.1145/129712.129767

M3 - Conference contribution

AN - SCOPUS:0026971188

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 557

EP - 570

BT - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992

PB - Association for Computing Machinery

T2 - 24th Annual ACM Symposium on Theory of Computing, STOC 1992

Y2 - 4 May 1992 through 6 May 1992

ER -