Recoverability of Communication Protocols—Implications of a Theoretical Study

Philip M. Merlin, David J. Farber

Research output: Contribution to journalArticlepeer-review

631 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1036-1043
Number of pages8
JournalIEEE Transactions on Communications
Issue number9
Publication statusPublished - 1976 Sept
Externally publishedYes

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Recoverability of Communication Protocols—Implications of a Theoretical Study'. Together they form a unique fingerprint.

Cite this