Skip to Main content Skip to Navigation
Conference papers

Timed Negotiations

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 [2]. In this paper, we introduce the model of timed negotiations and consider the problem of computing the minimum and the maximum execution time of a negotiation. The latter can be solved using the algorithm of [10] computing costs in negotiations, but surprisingly minimum execution time cannot. In this paper, we propose 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 ∆ P 2-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.
Document type :
Conference papers
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Loic Helouet Connect in order to contact the contributor
Submitted on : Monday, October 12, 2020 - 4:12:56 PM
Last modification on : Friday, October 8, 2021 - 6:50:31 PM
Long-term archiving on: : Wednesday, January 13, 2021 - 7:14:22 PM


Files produced by the author(s)



Sundararaman Akshay, Blaise Genest, Loic Helouet, Sharvik Mital. Timed Negotiations. FOSSACS 2020 - 23rd International Conference on Foundations of Software Science and Computation Structures, Apr 2020, Dublin (physical conference cancelled), Ireland. pp.1-36, ⟨10.1007/978-3-030-45231-5\_3⟩. ⟨hal-02964695⟩



Record views


Files downloads