TY - GEN
T1 - On the analysis of cooperation and antagonism in networks of communicating processes
AU - Kanellakis, Paris C.
AU - Smolka, Scott A.
N1 - Publisher Copyright:
© 1985 ACM.
PY - 1985/8/1
Y1 - 1985/8/1
N2 - We propose a new method for the analysis of cooperative and antagonistic properties of communicating finite state processes (FSPs). This algebraic technique is based on a composition operator and the notion of "possibility equivalence" among FSPs. We demonstrate its utility by showing that potential blocking, lockout, and termination can be efficiently decided for loosely connected networks of tree FSPs. If not all acyclic FSPs are trees, then the cooperative properties become NP-complete and the antagonistic ones PSPACE-complete. For tightly coupled networks of tree FSPs, we also have NP-hardness. For the considerably harder cyclic case, we provide a natural extension of the method as well as a subcase reducible to integer programming with a constant number of variables.
AB - We propose a new method for the analysis of cooperative and antagonistic properties of communicating finite state processes (FSPs). This algebraic technique is based on a composition operator and the notion of "possibility equivalence" among FSPs. We demonstrate its utility by showing that potential blocking, lockout, and termination can be efficiently decided for loosely connected networks of tree FSPs. If not all acyclic FSPs are trees, then the cooperative properties become NP-complete and the antagonistic ones PSPACE-complete. For tightly coupled networks of tree FSPs, we also have NP-hardness. For the considerably harder cyclic case, we provide a natural extension of the method as well as a subcase reducible to integer programming with a constant number of variables.
UR - https://www.scopus.com/pages/publications/84934920988
U2 - 10.1145/323596.323599
DO - 10.1145/323596.323599
M3 - Conference contribution
AN - SCOPUS:84934920988
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 23
EP - 38
BT - Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985
A2 - Strong, Ray
A2 - Malcolm, Michael
PB - Association for Computing Machinery
T2 - 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985
Y2 - 5 August 1985 through 7 August 1985
ER -