Local management of a global resource in a communication network

This paper introduces a new distributed data object called Resource Controller 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, number of nodes participating in the protocol, and total CPU time consumed. 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 procedure at this node, requesting a permit to consume a unit of the resource. The procedure returns either a permit or a rejection. The key characteristics of the Resource Controller object are the constraints that 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 permits art eventually granted, even if no more requests are made after the rejected one. In this paper, we describe several message and space-efficient implementations of the Resource Controller object. fn particular, we present an (M, W)-Controller whose message complexity is O(n log(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 controller which maintains a global counter of the number of granted permits at some distinguished node and relays all the requests to that node.