F. Haddix (USA)
Algorithms, parallel processing, mutual exclusion, self stabilization.
We introduce the probabilistic unidirectional self stabilizing double token ring, providing mutual exclusion, and loosely based on Dijkstra’s 1974 construction, in which there is one distinguished node and N - 1 other nodes. As in the Dijkstra algorithm, this algorithm uses a simple value pass-through protocol at nodes other than the distinguished node. Because the double token algorithm uses two Boolean variables, rather than the integer variable used by Dijkstra, it is highly scalable. Logically, a privilege is conveyed by either of two tokens, except at the distinguished node, which requires both tokens for privilege and execution. This approach has the advantages of delay insensitivity, simple implementation, and high scalability, requiring no modification as N increases. By delay insensitivity, we mean that the algorithm is insensitive to variations in processor speed or internodal transmission times. The probabilistic double token ring algorithm has an O(N lg N) expected convergence span. As with the unidirectional Dijkstra algorithm, the response span is O(N). The response time and the simplicity (including constant state space and communications requirements) of the other nodes are the principal advantages of the double token ring algorithm.
Important Links:
Go Back
