Optimal maintenance of a spanning tree

ABSTRACT

In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is O(V), where V is the number of nodes in the network. The message size used by the algorithm is O(log |ID|) where |ID| is the size of the name space of the nodes. Typically, log |ID| = O(log V).

Previous algorithms that adapt to dynamic networks involved Ω (E) messages per topological change—inherently paying for re-computation of the tree from scratch.

Spanning trees are essential components in many distributed algorithms. Some examples include broadcast (dissemination of messages to all network nodes), multicast, reset (general adaptation of static algorithms to dynamic networks), routing, termination detection, and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions.

REFERENCES

• 1: Yehuda Afek , Baruch Awerbuch , Eli Gafni, Applying static network protocols to dynamic networks, Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), p.358-370, October 12-14, 1987 [doi>10.1109/SFCS.1987.7]
• 2: Yehuda Afek , Baruch Awerbuch , Eli Gafni , Yishay Mansour , Adi Rosén , Nir Shavit, Slide—the key to polynomial end-to-end communication, Journal of Algorithms, v.22 n.1, p.158-186, Jan. 1997 [doi>10.1006/jagm.1996.0819]
• 3: Afek, Y., Awerbuch, B., and Moriel, H. 1989. Overhead of resetting a communication protocol is independent of the size of the network. (May) Unpublished manuscript.
• 4: Eli Gafni , Yehuda Afek, End-to-end communication in unreliable networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.131-148, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62570]
• 5: Yehuda Afek , Eli Gafni, Bootstrap network resynchronization (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.295-307, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112625]
• 6: Yehuda Afek , Eli Gafni , Adi Rosén, The slide mechanism with applications in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.35-46, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135430]
• 7: Yehuda Afek , Shay Kutten , Moti Yung, Memory-efficient self stabilizing protocols for general networks, Proceedings of the 4th international workshop on Distributed algorithms, p.15-28, June 1991, Bari, Italy
• 8: A. Arora , M. Gouda, Distributed Reset, IEEE Transactions on Computers, v.43 n.9, p.1026-1038, September 1994 [doi>10.1109/12.312126]
• 9: Joshua Auerbach , Madan Gopal , Marc Kaplan , Shay Kutten, Multicast group membership management, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.166-175, February 2003 [doi>10.1109/TNET.2002.808411]
• 10: 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]
• 11: Baruch Awerbuch, On the effects of feedback in dynamic network protocols, Journal of Algorithms, v.11 n.3, p.342-373, Sep. 1990 [doi>10.1016/0196-6774(90)90018-A]
• 12: Baruch Awerbuch , Israel Cidon , Inder Gopal , Marc Kaplan , Shay Kutten, Distributed control for PARIS, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.145-159, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93412]
• 13: B. Awerbuch , I. Cidon , S. Kutten, Communication-optimal maintenance of replicated information, Proceedings of the Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, p.492-502 vol.2, October 22-24, 1990 [doi>10.1109/FSCS.1990.89570]
• 14: Baruch Awerbuch , Israel Cidon , Shay Kutten , Yishay Mansour , David Peleg, Optimal Broadcast with Partial Knowledge, SIAM Journal on Computing, v.28 n.2, p.511-524, April 1999 [doi>10.1137/S0097539795279931]
• 15: Baruch Awerbuch , Oded Godlreich , Amir Herzberg, A quantitative approach to dynamic networks, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.189-203, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93419]
• 16: Baruch Awerbuch , Oded Goldreich , Ronen Vainish , David Peleg, A trade-off between information and communication in broadcast protocols, Journal of the ACM (JACM), v.37 n.2, p.238-256, April 1990 [doi>10.1145/77600.77618]
• 17: B. Awerbuch , Y. Mansour , N. Shavit, Polynomial end-to-end communication, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.358-363, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63503]
• 18: Baruch Awerbuch , Silvio Micali, Dynamic deadlock resolution protocols, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.196-207, October 27-29, 1986 [doi>10.1109/SFCS.1986.16]
• 19: 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, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185378]
• 20: Baruch Awerbuch , Leonard J. Schulman, The maintenance of common data in a distributed system, Journal of the ACM (JACM), v.44 n.1, p.86-103, Jan. 1997 [doi>10.1145/256292.256298]
• 21: B. Awerbuch , M. Sipser, Dynamic networks are as fast as static networks, Proceedings of the [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, p.206-219, October 24-26, 1988 [doi>10.1109/SFCS.1988.21938]
• 22: Baratz, A. E., Gray, J. P., Green Jr., P. E., Jaffe, J. M., and Pozefski, D. P. 1985. SNA networks of small systems. IEEE J. Select. Areas Commun. SAC-3, 3 (May), 416--426.
• 23: David Barnes , Basir Sakandar, Cisco LAN Switching Fundamentals, Cisco Press, 2004
• 24: Jochen Behrens , J. J. Garcia-Luna-Aceves, Distributed, scalable routing based on link-state vectors, Proceedings of the conference on Communications architectures, protocols and applications, p.136-147, August 31-September 02, 1994, London, United Kingdom
• 25: Bellur, B., and Ogier, R. G. 1999. A reliable, efficient topology broadcast protocol for dynamic networks. In Proceedings of IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA.
• 26: Marc Bui , Franck Butelle , Christian Lavault, A distributed algorithm for constructing a minimum diameter spanning tree, Journal of Parallel and Distributed Computing, v.64 n.5, p.571-577, May 2004 [doi>10.1016/j.jpdc.2004.03.009]
• 27: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 28: C. Cheng , I. Cimet , S. Kumar, A protocol to maintain a minimum spanning tree in a dynamic topology, Symposium proceedings on Communications architectures and protocols, p.330-337, August 16-18, 1988, Stanford, California, United States
• 29: C. Cheng , R. Riley , S. P. R. Kumar , J. J. Garcia-Luna-Aceves, A loop-free extended Bellman-Ford routing protocol without bouncing effect, Symposium proceedings on Communications architectures & protocols, p.224-236, September 25-27, 1989, Austin, Texas, United States
• 30: Serafino Cicerone , Gabriele Di Stefano , Daniele Frigioni , Umberto Nanni, A fully dynamic algorithm for distributed shortest paths, Theoretical Computer Science, v.297 n.1-3, p.83-102, 17 March 2003 [doi>10.1016/S0304-3975(02)00619-9]
• 31: Cidon, I., and Gopal, I. S. 1988. PARIS: An approach to integrated high-speed private networks. Int. J. Digital Analog Cabled Syst. 1, 2, (April-June), 77--86.
• 32: Cidon, I., Gopal, I. S., Kaplan, M., and Kutten, S. 1995a. A distributed control architecture of high-speed networks. IEEE Trans. Commun. 43, 5 (May) 1950--1960.
• 33: Cidon, I., Gopal, I. S., and Kutten, S. 1995b. New models and algorithms for future networks. IEEE Trans. Inf. Theory 41, 3 (May), 769--780.
• 34: Israel Cidon , Tony Hsiao , Asad Khamisy , Abhay Parekh , Raphael Rom , Moshe Sidi, OPENET: an open and efficient control platform for ATM networks, Journal of High Speed Networks, v.8 n.3, p.195-210, 1999
• 35: Cohen, R., and Segall, A. 1988. A distributed query protocol for high-speed networks. In Proceedings of the 9th International Conference on Computer Communication (ICCC88), (Tel Aviv, Israel, Oct.-Nov.) 299--302.
• 36: Dijkstra, E. W., and Scholten, C. S. 1980. Termination detection for diffusing computations. Inf. Proc. Lett. 11, 1 (Aug.) 1--4.
• 37: Shlomi Dolev , Amos Israeli , Shlomo Moran, Self-stabilization of dynamic systems assuming only read/write atomicity, Distributed Computing, v.7 n.1, p.3-16, November 1993 [doi>10.1007/BF02278851]
• 38: Michael Elkin, A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281128]
• 39: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 40: Finn, S. G. 1979. Resynch procedures and a fail-safe network protocol. IEEE Trans. Commun. COM-27, 6 (June) 840--845.
• 41: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 42: Frederickson, G. N. 1985. Data structures for on-line updating of minimum spanning trees. SIAM J. Comput. 14, 781--798.
• 43: Gafni, E. 1987. Topology resynchronization: A new paradigm for fault tolerance in distributed algorithms. In Proceedings of the 2nd Workshop on Distributed Algorithms (WDAG'87) Amsterdam, The Netherlands, July 8--10), Lecture Notes in Computer Science, vol. 312, Springer-Verlag, New York,
• 44: Gafni, E., and Afek, Y. 1987. Local fail-safe resynch procedure. unpublished manuscript, (Apr.).
• 45: Gallager, R. G. 1976. A shortest path routing algorithm with automatic resynch. Tech. repo. MIT LIDS, (Mar).
• 46: Gallager, R. G. 1977. A minimum delay routing algorithm using distributed computation. IEEE Trans. Commun. 25, 1, 73--85.
• 47: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 48: J. J. Garcia-Luna-Aceves, A unified approach to loop-free routing using distance vectors or link states, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.212-223, Sep. 1989
• 49: J. J. Garcia-Lunes-Aceves, Loop-free routing using diffusing computations, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.130-141, Feb. 1993 [doi>10.1109/90.222913]
• 50: Guerin, R., Rank, J., Sarkar, S., and Vergetis, E. 2003. Forming connected topologies in bluetooth adhoc networks. In Proceedings of ITC'18 (Berlin, Germany, Sept.).
• 51: Humblet, P. A. 1981. An adaptive distributed Dijkstra shortest path algorithm. Tech. Rep. CICS-P-60, Center for Intelligent Control Systems, MIT, Cambridge, MA, (May).
• 52: Humblet, P. 1991. Another adaptive distributed shortest path algorithm. IEEE Trans. Commun. 39, 6, 995--1003.
• 53: P. A. Humblet , S. R. Soloway, Topology broadcast algorithms, Computer Networks and ISDN Systems, v.16 n.3, p.179-186, Jan. 1989 [doi>10.1016/0169-7552(89)90066-4]
• 54: IETF. http://www.ietf.org/proceedings/02nov/179.htm.
• 55: Giuseppe F. Italiano, Distributed Algorithms for Updating Shortest Paths (Extended Abstract), Proceedings of the 5th International Workshop on Distributed Algorithms, p.200-211, October 07-09, 1991
• 56: Italiano, G. F., and Ramaswami, R. 1998. Maintaining spanning trees of small diameter. Algorithmica, 22, 3, 275--304.
• 57: Jaffe, J., and Moss, F. 1982. A responsive distributed routing protocol. IEEE Trans. Commun. COM-30, 7, II (Jul.), 1758--1762.
• 58: Korach, E., and Markovitz, M. 1986. Algorithms for distributed spanning tree construction in dynamic networks. Tech. Rep. 401, Dept of CS, Technion, Haifa, Israel (Feb).
• 59: E. Korach , S. Moran , S. Zaks, Optimal lower bounds for some distributed algorithms for a complete network of processors, Theoretical Computer Science, v.64 n.1, p.125-132, April 1989 [doi>10.1016/0304-3975(89)90103-5]
• 60: Shay Kutten , Avner Porat, Maintenance of a Spanning Tree in Dynamic Networks, Proceedings of the 13th International Symposium on Distributed Computing, p.342-355, September 27-29, 1999
• 61: McQuillan, J., Richer, I., and Rosen, E. 1980. The new routing algorithm for the arpanet. IEEE Trans. Commun., 28, 5 (May), 711--719.
• 62: G. A. Marin , C. P. Immanuel , P. F. Chimento , I. S. Gopal, Overview of the NBBS architecture, IBM Systems Journal, v.34 n.4, p.564-589, 1995
• 63: Merlin, P., and Segall, A. 1979. Failsafe distributed routing protocol. IEEE Trans. Comm. 27 (Sept.), 1280--1287.
• 64: R. Ogier , F. Templin , M. Lewis, Topology Dissemination Based on Reverse-Path Forwarding (TBRPF), RFC Editor, 2004
• 65: Radia Perlman, Interconnections (2nd ed.): bridges, routers, switches, and internetworking protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 66: B. Rajagopalan , M. Fairman, A new responsive distributed shortest-path rounting algorithm, Symposium proceedings on Communications architectures & protocols, p.237-246, September 25-27, 1989, Austin, Texas, United States
• 67: K. V.S. Ramarao , S. Venkatesan, On finding and updating shortest paths distributively, Journal of Algorithms, v.13 n.2, p.235-257, June, 1992 [doi>10.1016/0196-6774(92)90017-7]
• 68: Segall, A. 1983. Distributed network protocols. IEEE Trans. Inf. Syst. IT-29, 1 (Jan.), 23--35.
• 69: Segall, A., and Sidi, M. 1981, A failsafe distributed protocol for minimum delay routing. IEEE Trans. Commun., COM-29, 5 (May), 689--695.
• 70: Spinelli, J.M., and Gallager, R. G. 1989. Broadcasting topology information in computer networks. IEEE Trans. Commun. (May).
• 71: Andrew Tanenbaum, Computer Networks, Prentice Hall Professional Technical Reference, 2002
• 72: Turner, J. S. 1988. Design of a broadcast packet switching network. IEEE Trans. Commun. 36, 6 (Jun.), 734--743.
• 73: Vishkin, U. 1983. A distributed orientation algorithm. IEEE Trans. Inf. Theory, IT-29, 4 (July), 624--629.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Algorithms, Performance

Keywords:
Distributed algorithms, amortized complexity, dynamic networks, leader election, optimal message complexity, spanning tree, topological changes