Fast allocation of nearby resources in a distributed system

Abstract

this paper, the problem is generalized to a distributed system resource allocation problem which is local in two senses. First, although the system and number of users can be very large, there is a limit to the overlap in resource demands of different users. The second condition can be thought of as a property of the geography of the network - the resources are (or can be) located in the network in such a way that connunication between a user and any of its required resources is fast. Both types of locality conditions are satisfied by the Dining Philosophers problem. Under these two conditions, one would hope that waiting chains could be avoided, so that the worst-case time to grant a user's requests is independent of the total size of the network and the total number of users