SELF-STABILIZING DEPTH-FIRST MULTI-TOKEN CIRCULATION IN TREE NETWORKS

Abstract

Self stabilization is one of the new paradigms to investigate fault tolerance in distributed algorithm design. The multi-token or the l-exclusion problem is the logical generalization of standard mutual exclusion problem where l processes can enter their critical section at the same time. Self stabilizing single token circulation or the standard mutual exclusion problem has been investigated by a number of authors; recently authors in [16] have proposed a self stabilizing multi-token protocol for the ring networks. We propose a new self stabilizing algorithm (protocol) for depth first circulation of multiple tokens in a tree network. The algorithm uses only bounded integers and the correctness is proved by using induction.

Keywords:

• Token
• Multi-token
• Self-stabilization
• Tree networks
• Mutual exclusion

Notes

Corresponding author. Tel.: [phone], Fax: [phone], e-mail: sritnani@cs. colostate.edu