An Analysis Framework for Distributed Hierarchical Directories

作者：Sharma Gokarna^*; Busch Costas

来源：Algorithmica, 2015, 71(2): 377-408.

DOI：10.1007/s00453-013-9803-2

• Distributed directories
• Distributed queuing
• Dynamic executions
• Hierarchical clustering
• Competitive analysis
• Time window
• Distributed coordination

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 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 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.

• 出版日期2015-2