For the most recent entries see the Petri Nets Newsletter.

Self-Stabilizing Depth-First Token Passing on Rooted Networks.

Johnen, Colette; Alari, Gianluigi; Beauquier, Joffroy; Datta, Ajoy K.

In: Mavronicolas, M.; Tsigas, Ph.: Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany, pages 260-274. Springer, September 1997.

Abstract: We present a deterministic distributed depth-first token passing protocol on a rooted network. This protocol does not use either the processor identifiers or the size of the network, but assumes the existence of a distinguished processor, called the root of the network. The protocol is self-stabilizing, meaning that starting from an arbitrary state (in response to an arbitrary perturbation modifying the memory state), it is guaranteed to reach a state with no more than one token in the network. The protocol implements a strictly fair token circulation - during a round, every processor obtains the token exactly once. The proposed protocol has extremely small memory requirement - only O(1) bits of memory per incident network link.

Keywords: Mutual exclusion, self-stabilization, spanning tree, token passing.

Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography