×

Negotiation as concurrency primitive. (English) Zbl 1422.68168

This paper introduces negotiations, a model of concurrency close to Petri nets, with multi-party negotiations as concurrency primitive. The soundness problem consists in deciding if it is always possible for a negotiation to terminate successfully, whatever the current state is. Given a sound negotiation, the summarization problem aims at computing an equivalent one-step negotiation with the same input/output behavior. The soundness and summarization problems can be solved by means of simple algorithms acting on the state space of the negotiation, which, however, face the well-known state explosion problem. Alternative algorithms that avoid the construction of the state space are studied. In particular, reduction rules that simplify a negotiation while preserving the sound/non-sound character of the negotiation and its summary are defined. It is shown that defined rules are complete for the class of weakly deterministic acyclic negotiations, meaning that they reduce all sound negotiations in this class, and only them, to equivalent one-step negotiations. This provides algorithms for both the soundness and the summarization problems that avoid the construction of the state space. The class of deterministic negotiations is studied. The second main result shows that the rules are also complete for this class, even if the negotiations contain cycles. Moreover, an algorithm that completely reduces all sound deterministic negotiations, and only them, in polynomial time is presented.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Atdelzater, T.F., Atkins, E.M., Shin, K.G.: QoS negotiation in real-time systems and its application to automated flight control. IEEE Trans. Comput. 49(11), 1170-1183 (2000)
[2] Berthelot, G.: Transformations and decompositions of nets. In: Advances in Petri Nets, LNCS, vol. 254, pp. 359-376. Springer (1986)
[3] Bacarin, E., Madeira, E.R.M., Medeiros, C.B., van der Aalst, W.M.P.: SpiCa’s multi-party negotiation protocol: Implementation using YAWL. Int. J. Cooper. Inf. Syst. 20(3), 221-259 (2011)
[4] Capkovic, F.: Cooperation and negotiation of agents by means of Petri net-based models. In: 17th International Conference on Methods and Models in Automation and Robotics (MMAR), pp. 256-261 (2012)
[5] Desel, J., Esparza, J.: Free Choice Petri Nets. Cambridge University Press, New York (1995) · Zbl 0836.68074
[6] Desel, J., Esparza, J.: Negotiations and Petri nets. In: Proceedings of the International Workshop on Petri Nets and Software Engineering (PNSE’15), CEUR Workshop. CEUR-WS.org, vol. 1372, pp. 41-57 (2015) · Zbl 1366.68203
[7] Desel, J.: Struktur und Analyse von Free-Choice-Petrinetzen. DUV Informatik. Deutscher Universitätsverlag, Wiesbaden (1992) · Zbl 0790.68090
[8] Davis, R., Smith, R.G.: Negotiation as a metaphor for distributed problem solving. Artif. Intell. 20(1), 63-109 (1983)
[9] Esparza, J., Desel, J.: On negotiation as concurrency primitive. In: CONCUR, Lecture Notes in Computer Science, vol. 8052. Springer, pp. 440-454 (2013) · Zbl 1390.68468
[10] Esparza, J., Desel, J.: On negotiation as concurrency primitive II: Deterministic cyclic negotiations. In: FoSSaCS, Lecture Notes in Computer Science. Springer, pp. 258-273, vol. 8412 (2014) · Zbl 1405.68211
[11] Esparza, J., Hoffmann, P.: Reduction rules for colored workflow nets. In: Proceedings of the 19th International Conference on Fundamental Approaches to Software Engineering, FASE 2016, Lecture Notes in Computer Science, vol. 9633. Springer, pp. 342-358 (2016)
[12] Esparza, J., Hoffmann, P., Saha, R.: Polynomial analysis algorithms for free choice probabilistic workflow nets. In: Proceedings of the 13th International Conference on Quantitative Evaluation of Systems, QEST 2016, Lecture Notes in Computer Science, vol. 9826. Springer, pp. 89-104 (2016) · Zbl 1383.90016
[13] Esparza, J., Muscholl, A., Walukiewicz, I.: Static analysis of deterministic negotiations. In: Proceedings of LICS’17 (2017, to appear) · Zbl 1458.68132
[14] Esparza, J.: Decidability and complexity of Petri net problems—an introduction. In: Petri Nets, LNCS, vol. 1491. Springer, pp. 374-428 (1996) · Zbl 0926.68087
[15] Favre, C., Völzer, H., Müller, P.: Diagnostic information for control-flow analysis of workflow graphs (a.k.a. free-choice workflow nets). In: Proceedings of the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2016, Lecture Notes in Computer Science, vol. 9636. Springer, pp. 463-479 (2016) · Zbl 1420.68145
[16] Genrich, H.J., Thiagarajan, P.S.: A theory of bipolar synchronization schemes. Theor. Comput. Sci. 30, 241-318 (1984) · Zbl 0547.68054
[17] Haddad, S.; Rozenberg, G. (ed.), A reduction theory for coloured nets, No. 424, 209-235 (1988), Berlin
[18] Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley Longman, Boston (2006) · Zbl 0980.68066
[19] Haddad, S., Pradat-Peyre, J.-F.: New efficient Petri nets reductions for parallel programs verification. Parallel Process. Lett. 16(1), 101-116 (2006)
[20] Jennings, N.R., Faratin, P., Lomuscio, A.R., Parsons, S., Wooldridge, M.J., Sierra, C.: Automated negotiation: prospects, methods and challenges. Group Decis. Negot. 10(2), 199-215 (2001)
[21] Ji, S., Tian, Q., Liang, Y.: A Petri-net-based modeling framework for automated negotiation protocols in electronic commerce. In: PRIMA, LNCS, vol. 4078. Springer, pp. 324-336 (2005)
[22] Papadimitriou, C.H., Yannakakis, M.: The complexity of facets (and some facets of complexity). In: Lewis, H.R., Simons, B.B., Burkhard, W.A., Landweber, L.H. (eds.) STOC. ACM, pp. 255-260 (1982) · Zbl 0571.68028
[23] Salaün, G., Ferrara, A., Chirichiello, A.: Negotiation among web services using LOTOS/CADP. In: ECOWS, LNCS, vol. 3250. Springer, pp. 198-212 (2004)
[24] van der Aalst, W.M.P.: The application of Petri nets to workflow management. J. Circuits Syst. Comput. 08(01), 21-66 (1998)
[25] van Dongen, B.F., van der Aalst, W.M.P., Verbeek, H.M.W.: Verification of EPCs: Using reduction rules and Petri nets. In: CAiSE, LNCS, vol. 3520. Springer, pp. 372-386 (2005)
[26] Verbeek, H.M.W., Wynn, M.T., van der Aalst, W.M.P., ter Hofstede, A.H.M.: Reduction rules for reset/inhibitor nets. J. Comput. Syst. Sci 76(2), 125-143 (2010) · Zbl 1187.68330
[27] Winsborough, W.H., Seamons, K.E., Jones, V.E.: Automated trust negotiation. In: Proceedings of the DARPA Information Survivability Conference and Exposition, 2000. DISCEX’00, vol. 1. IEEE, pp. 88-102 (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.