A distributed alternative to finite-state-machine specifications

ABSTRACT

A specification technique, formally equivalent to finite-state machines, is offered as an alternative because it is inherently distributed and more comprehensible. When applied to modules whose complexity is dominated by control, the technique guides the analyst to an effective decomposition of complexity, encourages well-structured error handling, and offers an opportunity for parallel computation. When applied to distributed protocols, the technique provides a unique perspective and facilitates automatic detection of some classes of error. These applications are illustrated by a controller for a distributed telephone system and the full-duplex alternating-bit protocol for data communication. Several schemes are presented for executing the resulting specifications.

REFERENCES

• 1: John R. Cameron, JSP and JSD: the Jackson approach to software development (2nd ed), IEEE Press, Piscataway, NJ, 1989
• 2: CCITT, Functional Specification and Description Language (SDL). In Recommendations Z. 101- Z. I04, Vol. VI, Fascicle VI.7, Geneva, 1981.
• 3: DAVIS, A.M. The design of a family of application-oriented requirements languages. Computer 15, 5 (May 1982), 21-28.
• 4: John DeTreville, Phoan: An intelligent system for distributed control synthesis, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.96-103, April 1984
• 5: HAILPERN, B.T., AND OWlCKI, S.S. Modular verification of computer communication protocols. IEEE Trans. Commun. COM-31, 1 (Jan. 1983), 56-68.
• 6: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 7: M. A. Jackson, Principles of Program Design, Academic Press, Inc., Orlando, FL, 1975
• 8: M. A Jackson, System development (Prentice-Hall International series in computer science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1983
• 9: JACOB, R.J.K. Executable specifications for a human-computer interface. Naval Research Laboratory, Washington, D.C., Feb. 1983.
• 10: LESK, M.E. A lexical analyzer generator. CSTR 39, Bell Laboratories, Murray Hill, N.J., 1975.
• 11: RIDDLE, W.E. An approach to software system behavior description. Comput. Lang. 4 (1979), 29-47.
• 12: RIDDLE, W.E. An approach to software system modelling and analysis. Comput. Lang. 4 (1979), 49-66.
• 13: ROCgSTROM, A., AND SARACCO, R. SDL--CCITT Specification and Description Language. IEEE Trans. Commun. COM-30, 6 (June 1982), 1310-1318.
• 14: SUNSHINE, C.A. et al. Specification and verification of communication protocols in AFFIRM using state transition models. IEEE Trans. Softw. Eng. SE-8, 5 (Sept. 1982), 460-489.
• 15: Andrew S. Tanenbaum, Computer Networks, Prentice Hall PTR, Upper Saddle River, NJ, 1985
• 16: ZAVE, P. A distributed alternative to finite-state-machine specifications. Bell Laboratories Tech. Memo. 82-11384-17, Murray Hill, N.J., Dec. 1982.
• 17: ZAVE, P. An operational approach to requirements specification for embedded systems. IEEE Trans. Softw. Eng. SE-8, 3 (May 1982), 250-269.
• 18: Pamela Zave, The operational versus the conventional approach to software development, Communications of the ACM, v.27 n.2, p.104-118, Feb. 1984 [doi>10.1145/69610.357982]

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Tools; Methodologies (e.g., object-oriented, structured)

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Specification techniques

General Terms:
Theory