Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2006-11-20
LNCS 634 (1992) 133-144
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
The algorithm analysed by Na\"{i}mi, Trehe and Arnold was the very first distributed algorithm to solve the mutual exclusion problem in complete networks by using a dynamic logical tree structure as its basic distributed data structure, viz. a path reversal transformation in rooted n-node trees; besides, it was also the first one to achieve a logarithmic average-case message complexity. The present paper proposes a direct and general approach to compute the moments of the cost of path reversal. It basically uses one-one correspondences between combinatorial structures and the associated probability generating functions: the expected cost of path reversal is thus proved to be exactly $H_{n-1}$. Moreover, time and message complexity of the algorithm as well as randomized bounds on its worst-case message complexity in arbitrary networks are also given. The average-case analysis of path reversal and the analysis of this distributed algorithm for mutual exclusion are thus fully completed in the paper. The general techniques used should also prove available and fruitful when adapted to the most efficient recent tree-based distributed algorithms for mutual exclusion which require powerful tools, particularly for average-case analyses.
No associations
LandOfFree
Analysis of an Efficient Distributed Algorithm for Mutual Exclusion (Average-Case Analysis of Path Reversal) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Analysis of an Efficient Distributed Algorithm for Mutual Exclusion (Average-Case Analysis of Path Reversal), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of an Efficient Distributed Algorithm for Mutual Exclusion (Average-Case Analysis of Path Reversal) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-338514