Convergence of iteration systems. (English) Zbl 0818.68072
Summary: An iteration system is a set of assignment statements whose computation proceeds in steps: at each step, an arbitrary subset of the statements is executed in parallel. The set of statements thus executed may differ at each step; however, it is required that each statement is executed infinitely often along the computation. The convergence of such systems (to a fixed point) is typically verified by showing that the value of a given variant function is decreased by each step that causes a state change. Such a proof requires an exponential number of cases (in the number of assigment statements) to be considered. In this paper, we present alternative methods for verifying the convergence of iteration systems. In most of these methods, upto a linear number of cases need to be considered.
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
Software:
UNITYReferences:
| [1] | Arbib MA: Brains, machines and mathematics. Springer, Berlin Heidelberg New York 1987 |
| [2] | Burns JE, Gouda MG, Miller RE: On relaxing interleaving assumptions. Proc MCC Workshop on Self-Stabilizing Systems. MCC Tech Rep #STP-379-89 |
| [3] | Brown GM, Gouda MG, Wu CL: Token systems that selfstabilize. IEEE Trans Comput 38(6):845–852 (1989) · doi:10.1109/12.24293 |
| [4] | Bertsekas DP, Tsitsiklis JN: Parallel and distributed computation. Prentice-Hall, New Jersey 1989 |
| [5] | Chandy KM, Misra J: Parallel program, design: a foundation. Addison-Wesley 1988 · Zbl 0717.68034 |
| [6] | Dijkstra EW: The solution to a cyclic relaxation problem (1973) Reprinted in: Selected writings on computing: a personal perspective. Springer, Berlin Heidelberg New York 1982, pp 34–35 |
| [7] | Dijkstra EW: Self-stabilizing systems in spite of distributed control. Commun ACM 17(11):643–644 (1973) · Zbl 0305.68048 · doi:10.1145/361179.361202 |
| [8] | Gries D: The science of programming. Springer, Berlin Heidelberg New York 1981 · Zbl 0472.68003 |
| [9] | Gouda MG, Evangelist M: Convergence response tradeoffs in concurrent systems. MCC Tech Rep #STP-124-89 (also subumitted to ACM TOPLAS) |
| [10] | Grumberg O, Francez N, Makovsky JA, deRoever WP: A proof rule for fair termination of guarded commands. Inf Contr 66: 83–102 (1985) · Zbl 0577.68022 · doi:10.1016/S0019-9958(85)80014-0 |
| [11] | Harary F: Graph theory. Addison-Wesley 1972 |
| [12] | Hoare CAR: Communicating sequential processes. Prentice-Hall International 1985 |
| [13] | Kohonen T: Self-organization and associative memory. Springer, Berlin Heidelberg New York 1984 |
| [14] | Kung HT, Leiserson CE: Systolic arrays (for VLSI). In: Sparse Matrix Proc, 1978 |
| [15] | Lynch NA: I/O automata: a model for discrete event systems. Proc 22nd Annu Conf on Information Sciences and Systems, 1988 |
| [16] | Robert F: Discrete iterations – a metric study. Springer, Berlin Heidelberg New York 1986 · Zbl 0639.39005 |
| [17] | Wolfram S: Theory and applications of cellular automata, advanced series on complex systems, vol. 1. World Scientific, 1986 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
