Adapting to asynchronous dynamic networks (extended abstract)

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 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.

REFERENCES

• 1: Yehuda Afek, Baruch Awerbuch, and Eli Gafni. Applying static network protocols to dynamic networks. In Proc. 28th IEEE Symp. on Foundations of Computer Science, pages 358-370, October 1987.
• 2: Yehuda Afek and Moty Ricklin. Sparser: A paradigm for running distributed algorithms, unpublished manuscript, 1990.
• 3: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 4: Baruch Awerbuch. Reducing complexities of the distributed max-flow and breadth-first-search algorithms by means of network synchronization. Networks, 15(4):425-437, Winter 1985.
• 5: Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Fast deterministic cover algorthms. Unpublished manuscript, November 1991.
• 6: Baruch Awerbuch and Robert G. GaUager. Distributed B FS algorithms. In Proc. 26th IEEE Syrup. an Foun. dations of Computer Science, October 1985.
• 7: Baruch Awerbuch , Robert G. Gallager, A new distributed algorithm to find breadth first search trees, IEEE Transactions on Information Theory, v.33 n.3, p.315-322, May 1, 1987 [doi>10.1109/TIT.1987.1057314]
• 8: Baruch Awerbuch , Boaz Patt-Shamir , George Varghese, Self-stabilization by local checking and correction (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.268-277, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185378]
• 9: Baruch Awerbuch and David Peleg. Network synchronization with polylogarithmic overhead. In Proc. 31st IEEE Syrup. on Foundations of Computer Science, pages 514-522, 1990.
• 10: Baruch Awerbuch and David Peleg. Sparse partitions. In Proc. 31st IEEE Symp. on Foundations of Computer Science, pages 503-513, 1990.
• 11: Baruch Awerbuch and Michael Sipser. Dynamic networks are as fast as static networks. In Proc. 29th IEEE Symp. on Foundations of Computer Science, pages 206-220, October 1988.
• 12: C.T. Chou, I.S. Gopal, and S. Zaks. Synchronizing asynchronous bounded-delay networks. Research Report RC-12274, IBM Yorktown, October 1986.
• 13: S. Even , S. Rajsbaum, The use of a synchronizer yields maximum computation rate in distributed networks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.95-105, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100227]
• 14: Alan Fekete , Nancy A. Lynch , Liuba Shrira, A Modular Proof of Correctness for a Network Synchronizer (Research Summary), Proceedings of the 2nd International Workshop on Distributed Algorithms, p.219-256, July 08-10, 1987
• 15: Jeffrey Jaffe. Using signalling messages instead of clocks. Unpublished manuscript., 1980.
• 16: Richard Koo , Sam Toueg, Checkpointing and rollback-recovery for distributed systems, IEEE Transactions on Software Engineering, v.13 n.1, p.23-31, Jan. 1987 [doi>10.1109/TSE.1987.232562]
• 17: K. B. Lakshmanan , K. Thulasiraman, On the Use of Synchronizers for Asynchronous Communication Networks, Proceedings of the 2nd International Workshop on Distributed Algorithms, p.257-277, July 08-10, 1987
• 18: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 19: T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In Proc. 29th IEEE Symp. on Foundations of Computer Science, pages 256-271. IEEE, October 1988.
• 20: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 21: Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
• 22: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 23: David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, SIAM Journal on Computing, v.18 n.4, p.740-747, Aug. 1989 [doi>10.1137/0218050]
• 24: Prabhakar Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. In Proc. 27th IEEE Symp. on Foundations of Computer Science, pages 10-i 8, May 1986.
• 25: Baruch Shieber , Shlomo Moran, Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: maximum matchings, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.282-292, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10615]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Theory