Compact , Adaptive Placement Schemes for Non-Uniform Capacities
Compact , Adaptive Placement Schemes for Non-Uniform Capacities
复制标题
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
A. Brinkmann;de Kay Salzwedel;de Christian Scheideler
中科院分区：
文献类型：
--
作者：
A. Brinkmann;de Kay Salzwedel;de Christian Scheideler
在本文中，我们研究的问题，设计紧凑的，自适应的策略分布对象之间的一组异构的服务器。理想情况下，这种策略应该允许以低的时间和空间复杂度计算对象的位置，并且它应该能够以接近最小量的对象替换来适应服务器能力的变化，使得对象总是根据它们的能力分布在服务器之间。以前的技术只能部分地处理这些要求。例如，标准散列技术可以用于实现对象在一组服务器之间的非均匀分布以及对象位置的时间和空间有效计算，但是它们通常不能很好地适应能力的变化。我们提出了两种基于哈希的策略，可以实现上述所有目标。此外，我们给出了这些策略的应用程序列表，证明它们可以有效地用于分布式数据管理，Web缓存和自适应随机图，这可能是对等网络的兴趣。
In this paper we study the problem of designing compact, adaptive strategies for the distribution of objects among a heterogeneous set of servers. Ideally, such a strategy should allow the computation of the position of an object with a low time and space complexity, and it should be able to adapt with a near-minimum amount of replacements of objects to changes in the capabilities of the servers so that objects are always distributed among the servers according to their capabilities. Previous techniques are able to handle these requirements only in part. For example, standard hashing techniques can be used to achieve a non-uniform distribution of objects among a set of servers and the time and space efficient computation of the position of the objects, but they usually do not adapt well to a change in the capabilities. We present two strategies based on hashing that achieve all of the goals above. Furthermore, we give a list of applications for these strategies demonstrating that they can be used efficiently for distributed data management, web caches, and adaptive random graphs, which may be of interest for peer-to-peer networks.