.png){kind=icon}
返回
A fast token-chasing mutual exclusion algorithm in arbitrary network topologies
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1996.0078.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We present a simple and efficient mutual exclusion algorithm whose optimal message passing complexity is O(N), where N is the number of processors in the network. The message complexity is measured by counting the number of communication hops in a network for a given topology. This algorithm reduces its message passing complexity by a token-chasing method, and enhances its effectiveness by dynamically adjusting state information stored in each processor. Moreover, this algorithm shortens the request delay by fully taking advantage of the network dynamic status information. The performance of the algorithm is also modeled for analytical evaluation. We have conducted a group of experiments on a network of workstations for comparisons between our algorithm and two other existing mutual exclusion algorithms. The experimental results show the effectiveness of our algorithm, especially when a large number of requests access the critical region in a distributed system. Finally, the token-chasing algorithm is further enhanced for fault tolerance under message loss and link crash conditions. (C) 1996 Academic Press, Inc.
Keyword:
DISTRIBUTED SYSTEMS
