Abstract
Negotiations were introduced in [6] as a model for concurrent systems with multiparty decisions. What is very appealing with negotiations is that it is one of the very few non-trivial concurrent models where several interesting problems, such as soundness, i.e. absence of deadlocks, can be solved in PTIME [3]. In this paper, we introduce the model of timed negotiations and consider the problem of computing the minimum and the maximum execution times of a negotiation. The latter can be solved using the algorithm of [10] computing costs in negotiations, but surprisingly minimum execution time cannot.
This paper proposes new algorithms to compute both minimum and maximum execution time, that work in much more general classes of negotiations than [10], that only considered sound and deterministic negotiations. Further, we uncover the precise complexities of these questions, ranging from PTIME to \(\varDelta _2^P\)-complete. In particular, we show that computing the minimum execution time is more complex than computing the maximum execution time in most classes of negotiations we consider.
Supported by DST/CEFIPRA/INRIA Associated team EQuaVE and DST/SERB Matrices grant MTR/2018/000744.
Chapter PDF
Similar content being viewed by others
References
S. Akshay, B. Genest, L. Hélouët, and S. Mital. Timed negotiations (extended version). In Research report, https://hal.inria.fr/hal-02337887, 2020.
J. Desel. Reduction and design of well-behaved concurrent systems. In CONCUR ’90, Theories of Concurrency: Unification and Extension, Amsterdam, The Netherlands, August 27-30, 1990, Proceedings, volume 458 of Lecture Notes in Computer Science, pages 166–181. Springer, 1990.
J. Desel, J. Esparza, and P. Hoffmann. Negotiation as concurrency primitive. Acta Inf. 56(2):93–159, 2019.
J. Esparza. Decidability and complexity of petri net problems - an introduction. In Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, Dagstuhl, September 1996, volume 1491 of Lecture Notes in Computer Science, pages 374–428. Springer, 1998.
J. Esparza and J. Desel. Free Choice Petri Nets. Cambridge University Press, 1995.
J. Esparza and J. Desel. On negotiation as concurrency primitive. In CONCUR 2013 - Concurrency Theory - 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings, volume 8052 of Lecture Notes in Computer Science, pages 440–454. Springer, 2013.
J. Esparza and J. Desel. On negotiation as concurrency primitive II: deterministic cyclic negotiations. In FOSSACS’14, volume 8412 of Lecture Notes in Computer Science, pages 258–273. Springer, 2014.
J. Esparza and P. Hoffmann. Reduction rules for colored workflow nets. In Fundamental Approaches to Software Engineering - 19th International Conference, FASE 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceedings, volume 9633 of Lecture Notes in Computer Science, pages 342–358. Springer, 2016
J. Esparza, D. Kuperberg, A. Muscholl, and I. Walukiewicz. Soundness in negotiations. Logical Methods in Computer Science, 14(1), 2018.
J. Esparza, A. Muscholl, and I. Walukiewicz. Static analysis of deterministic negotiations. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–12, 2017.
S. Haddad. A reduction theory for coloured nets. In Advances in Petri Nets 1989, volume 424 of Lecture Notes in Computer Science, pages 209–235. Springer, 1990.
P. Hoffmann. Negotiation games. In Javier Esparza and Enrico Tronci, editors, Proceedings Sixth International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2015, Genoa, Italy, 21-22nd September 2015., volume 193 of EPTCS, pages 31–42, 2015.
M. W. Krentel. The complexity of optimization problems. Journal of computer and system sciences 36(3):490–509, 1988.
P.M. Merlin. A Study of the Recoverability of Computing Systems. PhD thesis, University of California, Irvine, CA, USA, 1974.
C. H. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC ’82, pages 255–260, New York, NY, USA, 1982. ACM
R.H. Sloan and U.A. Buy. Reduction rules for time petri nets. Acta Inf., 33(7):687–706, 1996.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
Akshay, S., Genest, B., Hélouët, L., Mital, S. (2020). Timed Negotiations. In: Goubault-Larrecq, J., König, B. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2020. Lecture Notes in Computer Science(), vol 12077. Springer, Cham. https://doi.org/10.1007/978-3-030-45231-5_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-45231-5_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45230-8
Online ISBN: 978-3-030-45231-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)