J. Kiniwa (Japan)
self-stabilization, token passing, request-based protocol, dynamic BFS spanning tree, lockout-free
This paper presents a new method for a request-based self-stabilizing token passing. A self-stabilizing dy namic BFS tree rooted at each request source pro cess is combined with token passing. That is, a to ken knows the request occurrence by touching the tree edge, and is passed toward the root. Even if more than two tokens stay at distinct roots, it can be shown that they will be merged into a unique token. An other feature is to attach power to each tree and it is periodically raised until the request is serviced. As a result, such a tree with a request which has long been neglected grows larger and larger. Since a large tree easily reaches a token, our method is lockout-free. Finally, some properties of our method, stabilization time, space complexity, and the efficiency of servicing k requests, called k-covering time, are shown.
Important Links:
Go Back
