Decentralization of process nets with centralized control

ABSTRACT

The behavior of a net of interconnected, communicating processes is described in terms of the joint actions in which the processes can participate. A distinction is made between centralized and decentralized action systems. In the former, a central agent with complete information about the state of the system controls the execution of the actions; in the latter no such agent is needed. Properties of joint action systems are expressed in temporal logic. Centralized action systems allow for simple description of system behavior. Decentralized (two-process) action systems again can be mechanically compiled into a collection of CSP processes. A method for transforming centralized action systems into decentralized ones is described. The correctness of this method is proved, and its use is illustrated by deriving a process net that distributedly sorts successive lists of integers.

REFERENCES

• 1: BACK, R.J.R., and R. KURKI-SUONIO, A case study in constructing distributed algorithms: Distributed exchange sort. Manuscript, 1983.
• 2: BACK, R.J.R., and R. KURKI-SUONIO, Fairness and justice in decentralized action systems. Manuscript, 1983.
• 3: K. M. Chandy , J. Misra, A distributed algorithm for detecting resource deadlocks in distributed systems, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.157-164, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806693]
• 4: Fiorella de Cindio , Giorgio De Michelis , Lucia Pomello , Carla Simone, Superposed Automata Nets, Selected Papers from the First and the Second European Workshop on Application and Theory of Petri Nets, p.269-279, September 28-30, 1980
• 5: Nissim Francez, Distributed Termination, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.42-55, Jan. 1980 [doi>10.1145/357084.357087]
• 6: GERGELY, T., and L. URY, Representation and verification of communicating sequential processes. Computational Linguistics and Computer Languages XV, 1982, 157-174.
• 7: 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]
• 8: Zohar Manna , Amir Pnueli, How to cook a temporal proof system for your pet language, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.141-154, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567082]
• 9: Reference Manual for the Ada Programming Language. Proposed Standard Document, U.S. Department of Defense, July 1980.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Centralization/decentralization

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

General Terms:
Management