Paper Info
Title
Distributed mutual exclusion on hypercubes
Abstract
Hypercube have been commercially available in the past few years to their high degree of connectivity, symmetry, and low degree of diameter. In this paper, we analyse the performance in number of messages on d-dimensional hypercube, for two groups of distributed algorithms for mutual exclusion, a permission-based mutual exclusion group, and a token-based mutual exclusion group.In the permission-based mutual exclusion algorithm, a node enters in the critical section only after receiving permission from all others nodes, this algorithm requires d2d messages.In the token-based mutual exclusion algorithm, a node is allowed to access its critical section if and only if it holds the token. In this algorithm, there is a node, called root, which knows the last node to get the token among the current requesting nodes. When a node wants to enter critical section, it sends request message to the root, which in turn informs the last node that new node will get the token next, and updates its last node. As result, the requesting nodes form a distributed queue, each of which records only the element next to it, this algorithm requires 2d messages in the worst case.
Year
DOI
Venue
1996
10.1145/230908.230917
Operating Systems Review
Keywords
Field
DocType
efficient mutual exclusion algorithm,token-based mutual exclusion algorithm,high degree,token-based mutual exclusion group,new node,permission-based mutual exclusion algorithm,permission-based mutual exclusion group,hypercubes,distributed algorithm,last node,low degree,critical section,mutual exclusion
Permission,Ricart–Agrawala algorithm,Suzuki-Kasami algorithm,Maekawa's algorithm,Computer science,Critical section,Computer network,Distributed algorithm,Mutual exclusion,Security token,Distributed computing
Journal
Volume
Issue
ISBN
30
3
90-5199-240-8
Citations 
PageRank 
References 
2
0.37
12
Authors
1
Name
Order
Citations
PageRank
Mohamed Naimi119616.15