The complexity of problems in systems of communicating sequential processes (Extended Abstract)

ABSTRACT

There is a wide-spread belief among computer scientists that systems of communicating sequential processes are harder to analyze than purely sequential processes. The belief is largely based on the observation that the parallelism in such systems leads to a large number of possible interleavings of the actions of the different processes. We will show that other evidence supporting this belief is that the properties we are trying to analyze about these systems are themselves intrinsically complex. They are properties that make no sense when they are applied to purely sequential processes, or even parallel systems of sequential processes that have no ability to communicate with each other.

REFERENCES

• 1: Chandra, A. K., and L. J. Stockmeyer. "Alternation". Proc. 17th IEEE Symp. on Foundations of Computer Science, 1976, 98-108.
• 2: Chandra, A. K., and L. J. Stockmeyer. "Provably Difficult Combinatorial Games". IBM Research Report RC6957, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1978, 43 pp.
• 3: R. Devillers, Game interpretation of the deadlock avoidance problem, Communications of the ACM, v.20 n.10, p.741-745, Oct. 1977 [doi>10.1145/359842.359854]
• 4: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 5: Dijkstra, E. "Cooperating Sequential Processes". In Programming Languages, F. Genuys, ed., Academic Press, NY, 1968.
• 6: S. Even , R. E. Tarjan, A Combinatorial Problem Which Is Complete in Polynomial Space, Journal of the ACM (JACM), v.23 n.4, p.710-719, Oct. 1976 [doi>10.1145/321978.321989]
• 7: Feldman, J. "A Programming Methodology for Distributed Computing (among other things)". Technical Report TR9, Dept. of Computer Science, University of Rochester, 1977, 51 pp.
• 8: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 9: Kozen, D. "On Parallelism in Turing Machines". Proc. 17th IEEE Symp. on Foundations of Computer Science, 1976, 89-97.
• 10: Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
• 11: Raymond E. Miller , Chee-Keng Yap, On the formal specification and analysis for loosely connected processes, Proceedings of the International Conference on Mathematical Studies of Information Processing, p.33-66, August 23-26, 1978
• 12: Milne, G., and R. Milner. "Concurrent Processes and their Syntax". University of Edinburgh Report, 1977, 30 pp.
• 13: Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
• 14: Rivest, R., and V. Pratt. "The Mutual Exclusion Problem for Unreliable Processes: Preliminary Report". Proc. 17th Annual Symposium on Foundations of Computer Science, 1976, 1-8.
• 15: Schaefer, T. G. "Complexity of Some Perfect Information Games". Journal of Computer and System Sciences, vol. 16, 1978, 185-225.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees