A static-tree-based algorithm for the `any one from any subset of a set of critical sections´ problem in distributed computing systems

Author

Satyanarayanan, R. ; Muthukrishnan, C.R.

Author_Institution

Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Madras, India

fYear

1994

fDate

22-26 Aug 1994

Firstpage

56

Abstract

In the basic version of the distributed mutual exclusion problem, only one resource is under contention. If there are many types and instances of shared resources in a distributed system, a node may want to access the first available resource from any given subset of these resources. In this paper, we present a static tree based solution to this problem. The number of messages generated per critical section execution can be from 0 to 2(N-1), where N is the number of nodes in the system. A significant advantage of the presented algorithm is that the upper bound on the number of messages generated per critical section execution, namely 2(N-1), is independent of the number of resources covered by the algorithm

Keywords

communication complexity; distributed algorithms; multiprocessing systems; resource allocation; trees (mathematics); concurrency; critical section execution; distributed computing systems; distributed mutual exclusion problem; message complexity; message generation; node access; resource contention; shared resources; static tree based algorithm; subset; upper bound; Computational Intelligence Society; Computer science; Concurrent computing; Control systems; Costs; Distributed algorithms; Distributed computing; Identity-based encryption; PROM; Permission;

fLanguage

English

Publisher

ieee

Conference_Titel

TENCON '94. IEEE Region 10's Ninth Annual International Conference. Theme: Frontiers of Computer Technology. Proceedings of 1994

Print_ISBN

0-7803-1862-5

Type

conf

DOI

10.1109/TENCON.1994.369336

Filename

369336