一致性的自我穩定環結構協定

Abstract

一個自我穩定系統不管在任何干擾下,都能回復到適合的型態. Dijkstra 首先使用一個特定的節點達到自我穩定,並提出在非質數個節點的環結構 中必需要一個特定的節點才能達到自我穩定. J.E.Burns和J.Pachl提出不 需要特定節點的自我穩定系統.黃興燦教授提出選領導者的方法,加諸任何 需要特定節點的自我穩定系統,結合成為不需要特定節點的自我穩定系統. 我們根據黃教授的方法,提出一個不需要特定節點的自我穩定系統.我們提 出的自我穩定系統並不保證互斥,而容許多重進入. A self-stabilizing system has the property that, no matter how it is perturbed, it eventually returns to a legitimate configuration. Dijkstra originally introduced the self- stabilization problem and solved that by a distinguished processor. He observed that a distinguished processor is essential is number of processors in the ring is composite. J.E. Burns and J.Pachl presented a uniform self-stabilizing ring which does not require a distinguished processor. Shing-Tsaan Huang introduced Leader Election Protocol which superimposes on all non-uniform self-stabilizing ring to be uniform. Based on Leader Election Protocol, we introduce our configuration and ring protocol. Our stable configuration does not guarantee mutual exclusive critiria but a multi-entry critical section.