LOCAL-MANAGEMENT OF A GLOBAL RESOURCE IN A COMMUNICATION-NETWORK

This paper introduces a new distributed data object called Resource Co ntroller that provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of resources that may be managed by such an object include; number of messages sent, num ber of nodes participating in the protocol, and total CPU time consume d. The Resource Controller object is accessed through a procedure that can be invoked at any node in the network. Before consuming a unit of resource at some node, the controlled algorithm should invoke the pro cedure at this node, requesting a permit to consume a unit of the reso urce. The procedure returns either a permit or a rejection. The key ch aracteristics of the Resource Controller object are the constraints th at it imposes on the global resource consumption. An (M, W)-Controller guarantees that the total number of permits granted is at most M; it also ensures that, if a request is rejected, then at least M - W permi ts art eventually granted, even if no more requests are made after the rejected one. In this paper, we describe several message and space-ef ficient implementations of the Resource Controller object. fn particul ar, we present an (M, W)-Controller whose message complexity is O(n lo g(2)n log(M/(W + 1)) where n is the total number of nodes. This is in contrast to the O(nM) message complexity of a fully centralized contro ller which maintains a global counter of the number of granted permits at some distinguished node and relays all the requests to that node.