A Self Stabilizing Algorithm for Constructing Breadth-First Trees

--Shing-Tsaang Huang, Nian-Shing Chen
Information Processing Letters 41 (1992) 109-117

back to My Homepage
back to Research page

1. Introduction

• Breadth First Tree property - A BFT of a connected graph is a spanning tree of the graph with the property that along the tree edges, each node has a minimum distance to the root.
• This is a static protocol - Once the system is in a legitimate state (a correct BFT), the system will remain in deadlock until a fault occurs.
• The algorithm meets the following three requirements
  • In each illegitimate state, at least one node is enabled
  • When the system is in a legitimate state, the system is deadlocked
  • Regardless of initial state, system is guaranteed to converge in finite steps
• Major contribution of paper is to prove by bounded function
• Algorithm assumes a distributed demon

2. The algorithm

• BFT ≡ ( ∀i : i ≠ r : L ( i ) = L ( p_i ) + 1 ∧ L ( p_i ) = min ({ L ( j ) | j ∈ N_i}))
• Root has no rule
• Other nodes
  • (R0) L ( i ) ≠ L ( p_i ) + 1 ∧ L ( p_i ) < n → L ( i ) : = L ( p_i ) + 1
  • (R1) Let k be a nbr of i such that L( k ) = min ({ L ( j ) | j ∈N_j }),
    • L ( p_i ) > L ( k ) → L ( i ) : = L ( k ) + 1, p_i : = k.
• (R0) - If a node's level is not it's parent's level + 1, and its parent is not at fault, then the node is enabled.
• (R1) - If a node points has a parent whose level is not the minimum among all the node's nbrs, then the node is enabled.

Please report all broken links and comments to jam0cam@yahoo.com

Created 3/15/06

Last Updated: 3/15/06