The slide mechanism with applications in dynamic networks

ABSTRACT

This paper presents a simple and efficient building block, called slide, for constructing communication protocols in dynamic networks whose topology frequently changes. We employ slide to derive (1) an end-to-end communication protocol with optimal amortized message complexity, and (2) a general method to efficiently and systematically combine dynamic and static algorithms. (Dynamic algorithms are designed for dynamic networks, and static algorithms work in networks with stable topology.) The new end-to-end communication protocol has amortized message communication complexity O(n) (assuming that the sender is allowed to gather enough data items before transmitting them to the receiver), where n is the total number of nodes in the network (the previous best bound was (O(m), where m is the total number of links in the network). This protocol also has bit communication complexity O(nD), where D is the data item size in bits (assuming data items are large enough; i.e., for D = &Ohgr;(nm log n)). In addition we give, as a byproduct, an end-to-end communication protocol using O(n2m) messages per data item, which is considerably simpler than other protocols known to us (the best known end-to-end protocol has message complexity O(nm)[AG91]). The protocols above combine in an interesting way several ideas: the information dispersal algorithm of Rabin [Rab89], the majority insight of [AFWZ88, AAF+], and the slide protocol.. The second application of slide develops a systematic mechanism to combine a dynamic algorithm with a static algorithm for the same problem, such that the combined algorithm automatically adjusts its communication complexity to the network conditions. That is the combined algorithm solves the problem in a dynamic network, and if the network stabilizes for a long enough period of time then the algorithm's communication complexity matches that of the static algorithm. This approach has been first introduced in [AM88] in the context of topology update algorithms.

REFERENCES

• AAF+: Y. Afek, H. Attiya, A. Fekete, M. Fischer, N. Lynch, Y. Mansour, D. Wang, and L. Zuck. Reliable communication over unreliable channels.
• AAG87: Y. Afek, B. Awerbuch, and E. Gafni. Applying static network protocols to dynamic networks. In Proc. of the 28ih IEEE Annual $ymp. on Foundation of Computer Science, pages 358-370, October 1987.
• AAM89: Y. Afek, B. Awerbuch, and H. Moriel. A complexity preserving reset procedure. Technical Report MIT/LCS/TM-389, MIT, May 1989.
• AE86: B. Awerbuch and S. Even. Reliable broadcast protocols in unreliable networks. NET- WORKS, 16(4):381-396, 1986. Previously titled "A Rigorous Treatment of a Communication Protocol: Broadcast as a Case Study.".
• AFWZ88: H. Attiya, M. J. Fischer, D. Wang, and L. D. Zuck. Reliable communication using unreliable channels. Manuscript, 1988.
• AG88: 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]
• AG91: 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]
• AGH90: 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]
• AM88: B. Awerbuch and Y. Mansour. An efficient topology update protocol for dynamic networks. Unpublished manuscript, January 1988.
• AMS89: B. Awerbuch, Y. Mansour, and N. Shavit. Polynomial end to end communication, in Proc. of the 30th IEEE Annual Symp. on Foundation of Computer Science, pages 358-363, October 1989.
• AP90: B. Awerbuch and D. Peleg. Sparse partitions. In Proc. of the 31st IEEE Annual $ymp. on Foundaiion of Computer Science, pages 503-513, October 1990.
• APSV91: 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]
• AS88: B. Awerbuch and M. Sipser. Dynamic networks are as fast as static networks. In Proc. of the 29th IEEE Annual Syrup. on Foundation of Computer Science, pages 206-220, October 1988.
• Awe85: 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]
• BGP89: P. Berman, J. A. Garay, and K. J. Perry. Towards optimal distributed consensus. In Proc. of the 30th IEEE Annual Symp. on Foundation of Computer Science, pages 410-415, October 1989.
• CL85: 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]
• DF88: Edsger W. Dijkstra , W. H. Feijen, A Method of Programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• DS80: W. Dijkstra and C. S. Scholten. Termination detection for diffusing computations. Information Processing Letters, 11-1:1-4, August 1980.
• Fin79: S.G. Finn. Resynch procedures and fail-safe network protocol. IEEE Trans. on Comm., COM-27:840-845, June 1979.
• MRR80: J. M. McQuillan, I. Richer, and E. C. Rosen. The new routing algorithm for the arpanet. IEEE Trans. on Communication, COM-28(5), May 1980.
• MS80: P.M. Merlin and P. J. Schweitzer. Deadlock avoidance in store-and-forward networks 1: Store-and-forward deadlock. IEEE Transaction on Communications, 28(3):345-354, March 1980.
• Rab89: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• Vis83: U. Vishkin. A distributed orientation algorithm. IEEE Trans. Info. Theory, June 1983.
• Wec80: S. Wecker. Dna: the digital network architecture. IEEE Transactions on Communecation, COM-28:510-526, April 1980.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks; Network communications
      C.2.2 Network Protocols
          Subjects: Protocol verification

General Terms:
Algorithms, Design, Theory, Verification