Chennai Mathematical Institute

Seminars




2:00 pm, Lecture Hall 1
Timed Negotiations

Loic Helouet
INRIA Rennes.
26-02-20


Abstract

Negotiations were introduced recently 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. In this work, 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 efficiently using a generic cost calculus algorithm proposed by [Esparza et al,2017], 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 [Esparza&al,2017], that only considered sound and deterministic negotiations. Further, we uncover the precise complexities of these questions, ranging from PTIME to Delta2P-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.

Joint work with S. Akshay, B. Genest, S. Mittal