A SELF-STABILIZING ALGORITHM FOR CONSTRUCTING BREADTH-1ST TREES

作     者：HUANG, ST CHEN, NS 

作者机构：NATL SUN YAT SEN UNIVDEPT INFORMAT MANAGEMENTKAOHSIUNGTAIWAN 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1992年第41卷第2期

页      面：109-117页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：FAULT TOLERANCE SELF-STABILIZING ALGORITHMS BREADTH-1ST TREES 

摘      要：A self-stabilizing algorithm for constructing breadth-first trees is proposed. Its self-stabilizing property is proven. A convincing and straightforward way to prove a system self-stabilizing is: First prove that the system can always make a computation step as long as the system is not stabilized, and give a bounded function whose value decreases for each computation step. But in some cases, it may be hard or even unlikely to find such a bounded function. However, by transforming the original set of rules into another set of rules so that both sets of rules have the equivalent effect, it may become easier to find such a bounded function from the transformed rules. The provided proof adopts this concept.