An Analysis Framework for Distributed Hierarchical Directories

We provide a novel analysis framework for distributed hierarchical directories for an arbitrary set of dynamic (online) requests. We first present a generic algorithm for implementing a distributed directory that can support dynamic requests and prove an upper bound on the competitive ratio for communication cost experienced by this algorithm using the analysis framework. We then give bounds for the dynamic performance of several known distributed directory protocols. For the protocols that work in general network topologies, we obtain $\mathcal {O}(\log^{2} n\cdot\log D)$ competitive ratio, where n and D are the number of nodes and the diameter, respectively, of the network. Moreover, for the protocols that work in specific network topologies, we obtain $\mathcal {O}(\log D)$ competitive ratio. Our analysis framework captures both the time and the distance restrictions in ordering dynamic requests through a notion of time windows, which may be of independent interest. To the best of our knowledge, this is the first competitive dynamic analysis for distributed hierarchical directories.