×

zbMATH — the first resource for mathematics

Occurrence nets then and now: the path to structured occurrence nets. (English) Zbl 1330.68215
Kristensen, Lars M. (ed.) et al., Applications and theory of Petri nets. 32nd international conference, PETRI NETS 2011, Newcastle, UK, June 20–24, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21833-0/pbk). Lecture Notes in Computer Science 6709, 1-16 (2011).
Summary: This lecture, in honour of the late Carl Adam Petri, tells of my early interactions with him and summarizes a small sequence of research projects at Newcastle University from 1977 onwards that relate to occurrence nets, ending with a description of a planned new project on “structured occurrence nets”. The areas of actual or planned application include deadlock avoidance, error recovery, atomicity, failure analysis, system synthesis and system verification.
For the entire collection see [Zbl 1216.68030].

MSC:
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68-03 History of computer science
Software:
Workcraft
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Avizienis, A., Laprie, J.C., et al.: Basic Concepts and Taxonomy of Dependable and Secure Computing. IEEE Transactions on Dependable and Secure Computing 1, 11–33 (2004) · Zbl 05113026
[2] Best, E., Randell, B.: A Formal Model of Atomicity in Asynchronous Systems. Acta Informatica 16, 93–124 (1981) · Zbl 0511.68033
[3] Bilinski, K., Dagless, E.L., et al.: Behavioral Synthesis of Complex Parallel Controllers. In: Proc. of 9th International Conference on VLSI Design, pp. 186–191. IEEE, Los Alamitos (1996)
[4] Brauer, W. (ed.): Net Theory and Applications. Proceedings of the Advanced Course on General Net Theory of Processes and Systems. LNCS, vol. 340. Springer, Heidelberg (1980)
[5] Campbell, R., Habermann, A.N.: The Specification of Process Synchronization by Path Expressions. In: Proc. of Symposium on Operating Systems, pp. 89–102 (1981)
[6] Esparza, J., Heljanko, K.: Unfoldings: a Partial-order Approach to Model Checking. Springer, Heidelberg (2008) · Zbl 1153.68035
[7] Herlihy, M., Moss, J.E.B.M.: Transactional Memory: Architectural Support for Lock-Free Data Structures. In: Proc. of 20th Annual International Symposium on Computer Architecture, pp. 289–300 (1993)
[8] Holt, A.W., Shapiro, R.M., et al.: Information System Theory Project (Appl. Data Research [1] ADR 6606). RADC-TR-68-305, US Air Force, Rome Air Development Center (1968)
[9] Horning, J.J., Lauer, H.C., et al.: A Program Structure for Error Detection and Recovery. In: Gelenbe, E., Kaiser, C. (eds.) Operating Systems. LNCS, vol. 16, pp. 171–187. Springer, Heidelberg (1974) · Zbl 0295.68026
[10] Jones, C., Lomet, D.B., et al.: The Atomic Manifesto: A Story in Four Quarks. SIGMOD Record 34, 63–69 (2005) · Zbl 05444309
[11] Khomenko, V., Koutny, M., et al.: Logic Synthesis for Asynchronous Circuits Based on STG Unfoldings and Incremental SAT. Fundamenta Informaticae 70, 49–73 (2006) · Zbl 1095.68065
[12] Khomenko, V., Koutny, M.: Verification of Bounded Petri Nets Using Integer Programming. Formal Methods in System Design 30, 143–176 (2007) · Zbl 1112.68104
[13] Koutny, M.: O Problemie Pociagów Merlina-Randella (in Polish). PhD Thesis, Department of Mathematics, Warsaw University of Technology, Warsaw, Poland (1984)
[14] Koutny, M.: On the Merlin-Randell Problem of Train Journeys. In: Paul, M., Robinet, B. (eds.) Programming 1984. LNCS, vol. 167, pp. 179–190. Springer, Heidelberg (1984) · Zbl 0594.68038
[15] Koutny, M.: Train Journeys in the Merlin-Randell Problem. TR-205, Computing Laboratory, Newcastle University (1985) · Zbl 0573.90094
[16] Koutny, M., Randell, B.: Structured Occurrence Nets: A formalism for Aiding System Failure Prevention and Analysis Techniques. Fundamenta Informaticae 97, 41–91 (2009) · Zbl 1187.68328
[17] Larus, J., Kozyrakis, C.: Transactional Memory. Communications of the ACM 51, 80–88 (2008) · Zbl 05395108
[18] Lauer, P.E., Campbell, R.H.: A Description of Path Expressions by Petri Nets. In: Proc. of 2nd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 95–105. ACM, New York (1975) · Zbl 0361.68055
[19] Lomet, D.B.: Process Structuring, Synchronization, and Recovery Using Atomic Actions. ACM SIGPLAN Notices 12, 128–137 (1977)
[20] McMillan, K.L.: A Technique of State Space Search Based on Unfolding. Formal Methods in System Design 6, 45–65 (1995) · Zbl 0829.68085
[21] Merlin, P.M.: A Study of the Recoverability of Computing Systems. PhD Thesis, University of California, Irvine (1974)
[22] Merlin, P.M., Schweitzer, P.J.: Deadlock Avoidance in Store-And-Forward Networks. In: Jerusalem Conference on Information Technology, pp. 577–581 (1978)
[23] Merlin, P.M., Randell, B.: Notes on Deadlock Avoidance on the Train Set. MRM/144, Computing Laboratory, Newcastle University (1978), http://homepages.cs.ncl.ac.uk/brian.randell/MRM144.pdf
[24] Merlin, P.M., Randell, B.: State Restoration in Distributed Systems. In: Proc. of 8th International Symposium on Fault-Tolerant Computing, pp. 129–134. IEEE Computer Society Press, Los Alamitos (1978)
[25] Petri, C.A.: Nicht-sequentielle Prozesse. ISF-Bericht ISF-76-6, Gesellschaft für Mathematik und Datenverarbeitung Bonn (1976)
[26] Petri, C.A.: General Net Theory. In: Proc. of 1976 Joint IBM/Univ. of Newcastle upon Tyne Seminar on Computing System Design, Newcastle upon Tyne, Computing Laboratory , pp. 131–169 (1977) , http://homepages.cs.ncl.ac.uk/brian.randell/GeneralNetTheory.pdf
[27] Petri, C.A.: Communication Disciplines. In: Proc. of 1976 Joint IBM/Univ. of Newcastle upon Tyne Seminar on Computing System Design, Newcastle upon Tyne, Computing Laboratory, pp. 171–183 (1977), http://homepages.cs.ncl.ac.uk/brian.randell/CommunicationDisciplines.pdf
[28] Poliakov, I., Khomenko, V., et al.: Workcraft – A Framework for Interpreted Graph Models. In: Franceschinis, G., Wolf, K. (eds.) PETRI NETS 2009. LNCS, vol. 5606, pp. 333–342. Springer, Heidelberg (2009) · Zbl 05571880
[29] Randell, B.: System Structure for Software Fault Tolerance. IEEE Trans. on Software Engineering SE-1, 220–232 (1975)
[30] Randell, B., Koutny, M.: Failures: Their definition, modelling and analysis. In: Jones, C.B., Liu, Z., Woodcock, J. (eds.) ICTAC 2007. LNCS, vol. 4711, pp. 260–274. Springer, Heidelberg (2007) · Zbl 1147.68599
[31] Randell, B., Koutny, M.: Structured Occurrence Nets: Incomplete, Contradictory and Uncertain Failure Evidence. TR-1170, School of Computing Science, Newcastle University (2009) · Zbl 1187.68328
[32] Snow, C.R.: Train Spotting. Newcastle upon Tyne, Computing Laboratory, Newcastle University (1997), http://history.cs.ncl.ac.uk/anniversaries/40th/webbook/trainset/index.html
[33] Wood, W.G.: A Decentralised Recovery Control Protocol. In: Proc. of 11th International Symposium on Fault-Tolerant Computing, pp. 159–164. IEEE Computer Society Press, Los Alamitos (1981)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.