UNIFORM SELF-STABILIZING ALGORITHMS FOR MUTUAL EXCLUSION

A self-stabilizing algorithm is a distributed algorithm that can solve problems, even when started in any arbitrary network configuration. T his paper describes a self-stabilizing algorithm that solves mutual ex clusion problems for three networks and complete networks. In a tree n etwork or in a complete network, because of their symmetrical nature, mutual exclusion problems cannot be solved by uniform deterministic al gorithms (all processors execute the same programs and do not assume t he existence of mutually distinct identifiers). Thus, the algorithms i ntroduced in this paper are superior to the existing ones in the follo wing respects: (1) uniformity of algorithms; (2) forwardness of little atomic action of processor (read/write demon); and (3) finiteness of the state number of the processors.