marina@ai.toronto.edu (Marina Haloulos) (11/29/89)
Department of Computer Science, University of Toronto
(GB = Gailbraith Building, 35 St. George Street)
-------------------------------------------------------------
THEORY SEMINAR
GB119, at 3:00 p.m., Thursday 7 December 1989
Dr. Baruch Awerbuch
M.I.T.
"Online Tracking of Mobile Users"
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. A polynomial-time algorithm that
constructs such a regional matching is presented. The communication
overhead of our tracking mechanism is within a polylogarithmic factor of
the lower bound.
Joint work with David Peleg.