Request-based token passing for self-stabilizing mutual exclusion |
| |
Authors: | Jun Kiniwa |
| |
Affiliation: | Department of Applied Economics, University of Hyogo, 8-2-1 Gakuen nishi-machi, Nishi-ku, Kobe-shi 651-2197, Japan |
| |
Abstract: | This paper presents a new method for request-based self-stabilizing token passing. A token is passed via a dynamic BFS (breadth-first search) tree rooted at a requesting process. When one of the tree edges reaches a process that has a token, the process is aware of the occurrence of a request. Then the token is passed towards the root. Even if multiple tokens stay at distinct roots, it can be shown that they will be merged into a single token. Furthermore, each request-rooted tree continues to grow until the request is serviced. As a result, the tree with a request that has long been neglected grows larger and larger, which makes it easier for the requesting process to get a token. Such advantages can be achieved by using bounded memory. We also evaluate the stabilization time and the efficiency of servicing k requests, called k-covering time, of our method. |
| |
Keywords: | Self-stabilization Token passing Request-based protocol Mutual exclusion Dynamic BFS spanning tree |
本文献已被 ScienceDirect 等数据库收录! |
|