Recoverability of Communication Protocols--Implications of a Theoretical Study

TLDR

The work builds on Petri nets, a formal computational model for representing processes. The study introduces a formal framework for analyzing and synthesizing recoverable computer communication protocols, including a new time‑Petri net model to overcome prior limitations. The authors extend Petri nets to model failures and define recoverability, then introduce a time‑Petri net that incorporates execution‑time constraints, which they use to design and analyze practical communication protocols. The authors derive necessary and sufficient conditions for recoverability, show that processes meeting these conditions in the PN model have practical limitations, demonstrate that the time‑Petri net is suitable for studying practical recoverable processes, and use it to design and analyze protocols with interesting properties.

Abstract

A study is presented which permits the formal analysis and synthesis of recoverable computer communication protocols. This study is based on a formal representation of processes by a model of computation, the Petri nets (PN's). The PN model is generalized to include a representation of the possible failures, and then, the concept of "recoverability" is formally defined. A set of necessary and sufficient conditions which a process must satisfy in order to be recoverable is derived. In the PN model, the processes that satisfy these conditions are shown to have some practical limitations. A new model, the time-Petri net (TPN), is introduced to remove these limitations. This new model allows the introduction of constraints in the execution times of its part. As shown in this paper, the TPN appears to be a suitable model for the study of practical recoverable processes. Several practical communication protocols are formally designed and analyzed using this new model, and some interesting properties of these protocols are formally derived.