Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In our model, a graph describes a net of processes communicating through ports and, at the same time, its computation history consisting of a partial ordering of events. Stand-alone evolution of processes is specified by context-free productions. From productions and a basic synchronization mechanism, a set of context-sensitive rewriting rules that models the evolution of processes connected to the same ports can be derived. A computation is a sequence of graphs obtained by successive rewritings. The result of a finite computation is its last graph, whereas the result of an infinite computation is the limit, infinite graph defined through a completion technique based on metric spaces. A result characterizes a concurrent computation, since it abstracts from any particular interleaving of concurrent events, while in the meantime providing information about termination, partial or complete deadlocks, and fairness. Not every result is acceptable, however, but only the computations that produce a result no longer rewritable are successful. Infinite successful computations are shown to coincide with weakly fair computations, and a scheduler yielding all and only such computations is defined.

REFERENCES

• 1: E Astesiano , G F Mascari , G Reggio , M Wirsing, On the parameterized algebraic specification of concurrent systems, Proc. of the international joint conference on theory and practice of software development (TAPSOFT) Berlin, March 25-29, 1985 on Mathematical foundations of software development, Vol. 1: Colloquium on trees in algebra and programming (CAAP'85), p.342-358, April 1985, Berlin, Germany
• 2: ASTESlANO, E., MAZZANTI, F., REGGIO, G., AND ZUCCA, E. Formal specification of a concurrent architecture in a real project. In Proceedings of the 8th A CM International Symposium on Computing (Firenze, Italy, Mar. 27-29), G. Valle and G. Bucci, Eds. North-Holland, Amsterdam, 1985.
• 3: Paul Boehm , Harald-Reto Fonio , Annegret Habel, Amalgamation of graph transformations: a synchronization mechanism, Journal of Computer and System Sciences, v.34 n.2-3, p.377-408, April/June 1987 [doi>10.1016/0022-0000(87)90030-4]
• 4: BRAMS, G.W. R~seaux de Petri: Th~orie et Pratique, vol. I and II. Masson, Paris, 1983.
• 5: S. D. Brookes , C. A. R. Hoare , A. W. Roscoe, A Theory of Communicating Sequential Processes, Journal of the ACM (JACM), v.31 n.3, p.560-599, July 1984 [doi>10.1145/828.833]
• 6: Ilaria Castellani , Ugo Montanari, Graph Grammars for distributed systems, Proceedings of the 2nd International Workshop on Graph-Grammars and Their Application to Computer Science, p.20-38, October 04-08, 1982
• 7: CASTELLANI, I., FRANCESCHI, P., ANt> MONTANARI, O. Labeled event structures: A model for observable concurrency. In Proceedings of IFIP TC 2m Working Conference: Formal Description of Programming Concepts II, D. Bjcmer, Ed. Garmisch-Partenkirchen, 1982; North-Holland, Amsterdam, 1983, pp. 383-400.
• 8: CHANDRA, A. K. Computable nondeterministic functions. In Proceedings of the 19th Annual ACM SIGACT Symposium on Theory of Computing. ACM, New York, 1978, pp. 127-131.
• 9: William D Clinger, Foundations of Actor Semantics, Massachusetts Institute of Technology, Cambridge, MA, 1981
• 10: CORRADINI, A. Aspetti Modellistici ed implementativi di GDS, un Formalismo per la Specifica di Sistemi Distribuiti. Master's dissertation. Computer Science Dept., Univ. of Pisa, Pisa, Italy, Apr. 1984.
• 11: CORRADINI, A., DEGANO, e., ANt> MONTANARI, U. Specifying highly concurrent data structure manipulation. In Proceedings of the 8th ACM International Symposium on Computing (Firenze, Italy, Mar. 27-29), G. Valle and G. Bucci, Eds. North-Holland, Amsterdam, 1985, pp. 93-103.
• 12: DE BAKKER, J. W., ANt> ZUCKER, J.i. Processes and the denotational semantics of concurrency. Inf. Cont. 54, 1/2 (1982), 70-121.
• 13: DEGANO, P., AND MONTANARI, U. A model for distributed systems based on graph rewriting. Note Cnet 111. Computer Science Dept., Univ. of Pisa, Pisa, Italy, 1983.
• 14: Pierpaolo Degano , Ugo Montanari, Liveness properties as convergence in metric spaces, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.31-38, December 1984 [doi>10.1145/800057.808663]
• 15: P. Degano , U. Montanari, Distributed systems, partial orderings of events, and event structures, Control Flow and Data Flow: concepts of distributed programming, Springer-Verlag New York, Inc., New York, NY, 1987
• 16: P Degano , U Montanari, Specification languages for distributed systems, Proc. of the international joint conference on theory and practice of software development (TAPSOFT) Berlin, March 25-29, 1985 on Mathematical foundations of software development, Vol. 1: Colloquium on trees in algebra and programming (CAAP'85), p.29-51, April 1985, Berlin, Germany
• 17: Pierpaolo Degano , Ugo Montanari, Concurrent histories: a basis for observing distributed systems, Journal of Computer and System Sciences, v.34 n.2-3, p.422-461, April/June 1987 [doi>10.1016/0022-0000(87)90032-8]
• 18: Pierpaolo Degano , Rocco De Nicola , Ugo Montanari, Partial ordering derivations for CCS, Fundamentals of Computation Theory, p.520-533, September 09-13, 1985
• 19: DEGANO, e., DE NICOLA, R., AND MONTANARI, U. Observational congruences for concurrency models. In Proceedings of the 3rd IFIP Working Conference on the Formal Description of Programming Concepts, M. Wirsing Ed. North-Holland, Amsterdam, 1986.
• 20: DUGUNDJI, J. Topology. Allyn and Bacon, Boston, Mass., 1966.
• 21: Hartmut Ehrig, Aspects of concurrency in graph grammars, Proceedings of the 2nd International Workshop on Graph-Grammars and Their Application to Computer Science, p.58-81, October 04-08, 1982
• 22: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 23: LAUER, P. E., TORRIGIANI, P. R., AND SHIELDS, M.W. COSY: A system specification language based on paths and processes. Acta Inf. 12 (1979), 109-158.
• 24: Robin Milner, Flowgraphs and Flow Algebras, Journal of the ACM (JACM), v.26 n.4, p.794-818, Oct. 1979 [doi>10.1145/322154.322167]
• 25: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 26: MILNER, R. Calculi for synchrony and asynchrony. Theoret. Comput. Sci. 25 (1983), 267-310.
• 27: MONTANAm, U., AND SIMONELLI, C. On distinguishing concurrency from nondeterminism, R6seaux de Petri et parall61ism (Colleville sur mer, 1980). Note Cnet 7. Computer Science Dept., Univ. of Pisa, Pisa, Italy, 1980.
• 28: Manfred Nagl, A Tutorial and Bibliographical Survey on Graph Grammars, Proceedings of the International Workshop on Graph-Grammars and Their Application to Computer Science and Biology, p.70-126, October 30-November 03, 1978
• 29: NmLSFN, M., PLOTKIN, G. D., AND WlNSKEL, G. Petri nets, event structures and domains, Part 1. Theoret, Comput. Sci. 13 (1981), 85-108.
• 30: NIVAT, M. Infinite words, infinite trees, infinite computations. In Foundations of Computer Science III, J. W. de Bakker, and J. van Leeuwen, Eds. vol. II. Mathematical Centre Tracts, vol. 109. Amsterdam, 1979, pp. 1-52.
• 31: NlVAT, M. Behaviours of processes and synchronized systems of processes. In Theoretical Foundations of Programming Methodology, M. Broy, and G. Schmidt, Eds. Reidel, Dordrecht, 1982, pp. 473-550.
• 32: C. A. Petri, Concurrency, Proceedings of the Advanced Course on General Net Theory of Processes and Systems: Net Theory and Applications, p.251-260, October 08-19, 1979
• 33: PLOrKIN, G.D. An operational semantics for CSP. In Proceedings of the IFIP TC 2--Working Conference: Formal Description of Programming Concepts II, D. Bjcrner, Ed. (Garmisch-Partenkirchen, West Germany, June 1982) North-Holland, Amsterdam, 1983, pp. 199-223.
• 34: SCOTT, D.S. Data types as latfices. SIAMJ. on Comp. 5 (1976), 522-587.
• 35: Jack C. Wileden, Relationships Between Graph Grammars and the Design and Analysis of Concurrent Software, Proceedings of the International Workshop on Graph-Grammars and Their Application to Computer Science and Biology, p.456-463, October 30-November 03, 1978
• 36: WINKOWSKI, J. Behaviours of concurrent systems. Theoret. Comput. Sci. 12 (1980), 39-60.
• 37: Glynn Winskel, Event Structure Semantics for CCS and Related Languages, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.561-576, July 12-16, 1982

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Hardware description languages

General Terms:
Design, Languages, Measurement, Theory, Verification