Journal of the ACM Bibliography

Baruch Awerbuch and David Peleg. Online tracking of mobile users. Journal of the ACM, 42(5):1021-1058, September 1995. [BibTeX entry]

This 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


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database