Upper Bounds for Static Resource Allocation in a Distributed System
Upper Bounds for Static Resource Allocation in a Distributed System
复制标题
DOI：
10.1016/0022-0000(81)90015-5
复制
发表时间：
1981-10
期刊：
影响因子：
--
通讯作者：
N. Lynch
中科院分区：
文献类型：
--
作者：
N. Lynch
本文所考虑的问题是对分布式计算机系统研究中出现的问题的简化。考虑一个网络，其中有大量的“资源”和这些资源的大量潜在用户。每个用户需要一组固定的资源（例如，为了执行一个程序）。每个用户的需求都假定是先验的。用户对各自的资源集发起请求时，彼此之间是异步的。问题是设计一种算法，保证每个用户最终控制其资源。如果用户在接收资源之前的等待时间较短，则认为该问题的一种解决方案优于另一种解决方案。在实际的分布式计算机系统中，某些资源可能有几个可互换的实例。但是，有一类分配策略会将每个用户绑定到其每个资源的特定（例如，最近的）实例。本文的问题适用于这类策略。假设存在大量分布广泛的用户，但从两个意义上说，问题仍然是“局部的”。首先，可以以这样一种方式定位网络中的资源，即它们通常位于请求用户的“附近”。其次，资源需求模式不是高度“连接”的：例如，每个用户的资源不是很多，或者每个资源的用户不是很多（至少，与整个网络中存在的总数相比不是很多）。在这两种情况下，每个用户的等待时间不应该是整个网络规模的函数，而应该是局部参数的函数（例如每个用户的最大资源数量和每个资源的最大用户数量），这似乎是合理的。对网络中一个位置的所有资源进行集中控制并不总是可取的。这个位置将成为一个瓶颈，而且长距离通信固有的延迟将导致等待时间
The problem considered in this paper is a simplification of one arising in the study of distributed computer systems. A network is considered, in which are located a large number of “resources” and a large number of potential users of those resources. Each user requires a certain fixed set of resources (for instance, in order to execute a program). Each user’s needs are assumed to be known a priori. Users originate requests for their respective sets of resources asynchronously with respect to each other. The problem is to design an algorithm guaranteeing each user eventual control over its resources. One solution to this problem is considered to be better than another if users have shorter waiting times before receiving their resources. In an actual distributed computer system, there might be several interchangeable instances of some resources. However, one class of allocation strategies would bind each user to a particular (for example, the nearest) instance of each of its resources. The problem of this paper applies to this class of strategies. It is assumed that there are a very large number of widely distributed users, but that the problem is nevertheless “local” in two senses. First, it is possible to locate the resources in the network in such a way that they are generally “nearby” requesting users. Second, the resource-need pattern is not very highly “connected”: for instance, there are not very many resources for each user or users for each resource (at least, not very many compared to the total number which are present in the entire network). Under these two conditions, it seems reasonable that each user’s waiting time should not be a function of the size of the entire network, but rather a function of local parameters only (such as the maximum number of resources for each user and the maximum number of users for each resource). It is not always desirable to centralize control over all of the resources at one location in the network. That location would become a bottleneck, and moreover the delays inherent in long-distance communication would cause waiting time for the