Abstract
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 most M; it also ensures that, if a request is rejected, then at least M—W permits 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 is O(n log2n 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 the node.
- AFEK, Y., AWERBUCH, B., AND GAFNI, E. 1987. Applying static network protocols to dynamic networks. In Proceedings of the 28th IEEE Annual Symposium on Foundations of Computer Science. IEEE, New York, pp. 358-370.Google Scholar
- AFEK, Y., LANDAU, G. M,, SCHIEBER, B., AND YUNG, M. 1988. The power of Multimedia: Combining point-to-point and multiaccess networks. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing. (Toronto, Ont., Canada, Aug. 15-17). ACM, New York, pp. 90-104. Google Scholar
- AWERBUCH, B. 1985. Complexity of network synchronization. J. ACM 32, 804-823. Google Scholar
- AWERBUCH, B. 1988. On the effects of feedback in dynamic network protocols. In Proceed/rigs of the 29th IEEE Annual Symposium on Foundations of Computer Science. 231-245.Google Scholar
- BnR-YEHUDA, R., A~D KUTrEN, S. 1988. Fault tolerant distributed majority commitment. J. Algorithms 9, 568-582. Google Scholar
- DIJKSTRA, E. W., AND SCHOLTEN, C. S. 1980. Termination detection for diffusing computations. Inf. Proc. Lett. 11, 1-4.Google Scholar
- GALLAGER, R. G., HUMBLEr, P. A., AND SI~IRA, P. M. 1983. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Prog. Lang. Syst. 5, 66-77. Google Scholar
- GOLDBERG, A., aND PLOTKIN, S. 1987. Parallel (A + I) coloring of constant-degree graphs. Inf. Proc. Lett. 25, 4, 241-245. Google Scholar
- GOt. DBERG, A. V., PLOTKIN, S. A., AND SHANNON, G. E. 1988. Parallel symmetry-breaking in sparse graphs. SIAM J. Disc. Math. 1,434-446. Google Scholar
- LYNCH, N. A., GRIFFETH, N. D., FISCHER, M. J., AND GUIBAS, L. J. 1986. Probabilistic analysis of a network resource allocation algorithm. Inf. Cont. 68, 47-85. Google Scholar
Index Terms
- Local management of a global resource in a communication network
Recommendations
Workload balancing and adaptive resource management for the swift storage system on cloud
The demand for big data storage and processing has become a challenge in today's industry. To meet the challenge, there is an increasing number of enterprises adopting distributed storage systems. Frequently, in these systems, storage nodes intensively ...
Resource virtualization methodology for on-demand allocation in cloud computing systems
The resources' heterogeneity and unbalanced capability, together with the diversity of resource requirements in cloud computing systems, have produced great contradictions between resources' tight coupling characteristics and user's multi-granularities ...
Local Resource Shaper for MapReduce
CLOUDCOM '14: Proceedings of the 2014 IEEE 6th International Conference on Cloud Computing Technology and ScienceResource capacity is often over provisioned to primarily deal with short periods of peak load. Shaping these peaks by shifting them to low utilization periods (valleys) is referred to as "resource consumption shaping". While originally aimed at the data ...
Comments