AbstractThis paper deals with the problem of maintaining a distributed directory server that enables us to keep track of mobile users in a distributed network. The paper introduces the graph-theoretic concept of regional matching, and demonstrates how finding a regional matching with certain parameters enables efficient tracking. The communication overhead of our tracking mechanism is within a polylogarithmic factor of the lower bound. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: B.4.4 [Input/Output and Data Communications]: Performance Analysis and Design Aids; C.2.2 [Computer-Communication Networks]: Network Protocols; D.4.4 [Operating Systems]: Communications Management -- network communications; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism and concurrency
General Terms: Design, Protocols, Reliability, Theory, Verification
Additional Key Words and Phrases: Bounded packet header, bounded protocol, ideal transmission cost, lookahead, non-FIFO channels, receiver-driven protocol, recoverable protocol, recovery cost, sequence transmission problem
Selected references
- Yehuda Afek, Baruch Awerbuch, and Eli Gafni. Applying static network protocols to dynamic networks. In 28th Annual Symposium on Foundations of Computer Science, pages 358-370, Los Angeles, California, 12-14 October 1987. IEEE.
- Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804-823, October 1985.
- Baruch Awerbuch, Yair Bartal, and Amos Fiat. Competitve distributed file allocation. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 164-173, San Diego, California, 16-18 May 1993.
- Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network decomposition and locality in distributed computation. In 30th Annual Symposium on Foundations of Computer Science, pages 364-369, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
- Baruch Awerbuch, Shay Kutten, and David Peleg. Competitive distributed job scheduling (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 571-580, Victoria, British Columbia, Canada, 4-6 May 1992.
- Baruch Awerbuch and David Peleg. Network synchronization with polylogarithmic overhead. In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 514-522, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Baruch Awerbuch and David Peleg. Sparse partitions (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 503-513, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Michael Saks. Adapting to asynchronous dynamic networks (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 557-570, Victoria, British Columbia, Canada, 4-6 May 1992.
- Yair Bartal, Amos Fiat, and Yuval Rabani. Competitive algorithms for distributed data management (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 39-50, Victoria, British Columbia, Canada, 4-6 May 1992.
- Yair Bartal and Adi Rosén. The distributed k-server problem -- a competitive distributed translator for k-server algorithms. In 33rd Annual Symposium on Foundations of Computer Science, pages 344-353, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- R. G. Gallager, P. A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems, 5(1):66-77, January 1983.
- Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558-565, July 1978.
- Nathan Linial and Michael Saks. Decomposing graphs into regions of small diameter. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 320-330, San Francisco, California, 28-30 January 1991.
- Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for on-line problems. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 322-333, Chicago, Illinois, 2-4 May 1988.
- David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510-530, July 1989.