SELF-STABILIZATION OF DYNAMIC-SYSTEMS ASSUMING ONLY READ WRITE ATOMICITY

Three self-stabilizing protocols for distributed systems in the shared memory model are presented. The first protocol is a mutual-exclusion protocol for tree structured systems. The second protocol is a spannin g tree protocol for systems with any connected communication graph. Th e third protocol is obtained by use of fair protocol combination, a si mple technique which enables the combination of two self-stabilizing d ynamic protocols. The result protocol is a self-stabilizing, mutual-ex clusion protocol for dynamic systems with a general (connected) commun ication graph. The presented protocols improve upon previous protocols in two ways: First, it is assumed that the only atomic operations are either read or write to the shared memory. Second, our protocols work for any connected network and even for dynamic networks, in which the topology of the network may change during the execution.