Local management of a global resource in a communication network
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 347-357
- https://doi.org/10.1109/sfcs.1987.38
Abstract
We introduce a new primitive, the Resource Controller, which abstracts the problem of controlling the total amount of resources consumed by a distributed algorithm. We present an efficient distributed algorithm to implement this abstraction. The message complexity of our algorithm per participating node is polylogarithmic in the size of the network, compared to the linear cost per node of the naive algorithm. The implementation of our algorithm is simple and practical and the techniques used are interesting because a global quantity is managed in a distributed way. The Resource Controller can be used to construct efficient algorithms for a number of important problems, such as the problem of bounding the worst-case message complexity of a protocol and the problem of dynamically assigning unique names to nodes participating in a protocol.Keywords
This publication has 6 references indexed in Scilit:
- Applying static network protocols to dynamic networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Parallel symmetry-breaking in sparse graphsPublished by Association for Computing Machinery (ACM) ,1987
- Detecting global termination conditions in the face of uncertaintyPublished by Association for Computing Machinery (ACM) ,1987
- Probabilistic analysis of a network resource allocation algorithmInformation and Control, 1986
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983
- Termination detection for diffusing computationsInformation Processing Letters, 1980