Technical Report CS0590

Title: Self Stabilization of Dynamic Systems Assuming Only Read/Write Atomicity
Authors: S. Dolev, A. Israeli and S. Moran
Abstract: Self stabilizing protocols for distributed systems in the shared memory model are defined and studied. The protocols presented here 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 dynamic networks, in which the topology of lhe network may change during the execution. Three dynamic self-stabilizing protocols are presented. The first protocol is a spanning tree protocol for systems with any connected communication graph. The second protocol is a mutual exclusion protocol for tree structured systems. The third protocol is a self stabilizing protocol for mutual exclusion, for systems with a general (connected) communication graph. This last protocol is obtained by combining the previous two protocols. The combination employs a simple technique called/air protocol composition. which is enabled by both the self-stability and by the flexibility of dynamic protocols.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion