Local management of a global resource in a communication network
Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael Saks · Journal of the ACM · 1996
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 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 mostM; it also ensures that, if a request is rejected, then at leastM—Wpermits are 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. In particular, we present an (M, W)-Controller whose message complexity isO(nlog2nlog(M/(W+ 1)) wherenis the total number of nodes. This is in contrast to theO(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 the node.