A Log (N) Distributed Mutual Exclusion Algorithm Based on Path Reversal |
| |
| Affiliation: | 1. Faculty of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin 34185-1416, Iran;2. Singapore Institute of Technology, Singapore 13868, Singapore;3. School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore;4. Singapore Institute of Manufacturing Technology, Singapore 638075, Singapore |
| |
| Abstract: | In this paper, we present a distributed algorithm for mutual exclusion based on path reversal. The algorithm does not use logical clocks to serialize the concurrent events, and all the variables are bounded. When a process invokes a critical section, it sends a request to the tail of a queue. A dynamical rooted tree gives the path to this tail. The algorithm requires onlyO(log(n)) messages on average, wherenis the number of processes in the network. The performance analysis of the algorithm is based on generating formal power series. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
