Self-stabilization of dynamic systems assuming only read/write atomicity
Tóm tắt
Three self-stabilizing protocols for distributed systems in the shared memory model are presented. The first protocol is a mutual-exclusion prootocol for tree structured systems. The second protocol is a spanning tree protocol for systems with any connected communication graph. The thrid protocol is obtianed by use offair protoco combination, a simple technique which enables the combination of two self-stabilizing dynamic protocols. The result protocol is a self-stabilizing, mutualexclusion protocol for dynamic systems with a general (connected) communication 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 network, in which the topology of the network may change during the excution.
Tài liệu tham khảo
Brown GM, Gouda MG, Wu CL: A self-stabilizing token system In: Proc 20th Annual Hawaii International Conference on System sciences pp. 218–223, 1987
Burns JE, Pachl J: Uniform self-stabilizing rings, ACM Trans Program Lang Syst 1(2): 330–344 (1989).
Burns JE: Self-stabilizing rings without demons. Tech Rep GITICS-87/36, Georgia Institute of Technology, 1987
Dijkstra, EW: Self-stabilizing systems in spite of distributed control. Commun ACM 17(11): 643–644 (1974)
Dijkstra EW: Self-stabilizing systems in spite of distributed control (EWD 391). Reprinted in: Selected writing on computing: a personal perspective. Springer, Berlin Heidelberg New York 1982, pp 41–46
Dijkstra EW: A belated proff of self-stabilization. Distrib Comput 1(1): 5–6 (1986)
Dolev S, Israeli A, Moran S: Self-stabilization of dynamic systems assuming only read/write atomicity (preliminary version) Proc MCC Workshop on Self-Stabilization, Austin, Texas, November 1989. Also in: Proc 9th Annual ACM Symposium on Principles of Distributed Computing, pp 103–117, 1990
Israeli a., Jalfon M: Token management schemes and random walks yield self-stabilizing mutual exclusion. In: Proc 9th Annual ACM Symposium on Principles of Distributed Computing pp 119–131, 1990
Israeli A, Jalfon M: Uniform self-stabilizing ring orientation. Inf Comput 104: 175–196 (1993). Also in: Van Leeuwen J, Santor N (eds) Distributed Algorithms (Proceedings of the Fourth International Workshop on Distributed Algorithms, Bari, Italy, September 1990). Lect Notes Comput Sci, vol 486. Springer, Berlin Heidelber New York 191, pp 1–14
Katz S, Perry KJ: Self-stabilizing extensions for meassage-passing systems. Distrib Comput 7: 17–26 (1993). Also in: Proc 9th Annual ACM Symposium on Principles of Distributed Computing, pp. 91–101, 1990.
Kruijer HSM: Self-stabilization (in spite of distributed control) in tree-structured systems. Inf Process Lett 8(2): 91–95 (1979)
Loui MC, Abu-Amara HH: Memory requirements for agree ment among unreliable asynchronous processes. In: Preparata FP (ed) Advances in computing research. JAI Press 1987, pp 163–183
Peterson GL, Fischer MJ: Economical solutions for the crtical section problem in a distributed system. In: Proc ACM symposium on Theory of Computing, pp 91–97, 1977
Tajibnapis WP: A correctness proof of a topology information maintenance protocol for a distributed computer network. Commun ACM 20(7): 477–485 (1977)
Tanenbaum AS: Computer networks. Prentice-Hall, 1981, pp 205–231.
Tchuente M: Sur l'auto-stabilisation dans un r'eseau d'ordinateurs, RAIRO Inf Theor 15: 47–66 (1981)