IRE Transactions on Communications Systems · 1982 · 107 citations · 10 references
ComputingComputer ScienceComputer SystemsComputer NetworksFault-tolerant SystemsFormal MethodsCommunication NetworksInternet Protocol SuiteNetwork ArchitectureNetwork Fault ToleranceNetwork ProtocolsPetri NetsInvariantsNetwork Level Of ServicePetri Net Model CheckingPetri Net ModelsPetri Net VerificationStructural InvariantsTransition NetsTransport Protocol Design
Petri nets theory is introduced as a foundation for modeling the ECMA transport protocol. The authors model the ECMA transport protocol with Petri nets, detailing connection/disconnection phases, data transfer using a window mechanism and control frames, and predicate/transition nets. Correctness of the protocol, including data transfer and overall service, is proven via Petri net reductions, linear invariants, and invariant analysis.
After a brief introduction to the theory of Petri nets, the ECMA transport protocol is presented. Then a model of the connection and disconnection phases is developed. Properties of correctness are demonstrated, using Petri net theory results, namely, reductions and linear invariants techniques. Predicate/transition nets are introduced and the underlying network service is modeled. Then a model of the data transfer phase is described. It allows correction of the errors signaled by the network level, by using a window mechanism and control frames for acknowledgments and rejections. The correctness of the data transfer is demonstrated using invariants. The service provided to the upper level is thus validated.
10
Formal verification of parallel programs
Robert Keller · Communications of the ACM · 1976 · 791 citations · Full text
N.V. Stenning · Computer Networks (1976) · 1976 · 173 citations