S Akshay
email: akshayss@cse.iitb.ac.in

Blaise Genest
email: blaise.genest@irisa.fr

Loic Helouet
email: loic.helouet@inria.fr

Sharvik Mital

Timed Negotiations

. 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.

, 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.

Introduction

Distributed systems are notoriously difficult to analyze, mainly due to the explosion of the number of configurations that have to be considered to answer even simple questions. A challenging task is then to propose models on which analysis can be performed with tractable complexities, preferably within polynomial time. Free choice Petri nets are a classical model of distributed systems that allow for efficient verification, in particular when the nets are 1-safe [START_REF] Esparza | Decidability and complexity of petri net problems -an introduction[END_REF][START_REF] Esparza | Free Choice Petri nets[END_REF].

Recently, [START_REF] Esparza | On negotiation as concurrency primitive[END_REF] introduced a new model called negotiations for workflows and business processes. A negotiation describes how processes interact in a distributed system: a subset of processes in a node of the system take a synchronous decisions among several outcomes. The effect of this outcome sends contributing processes to a new set of nodes. The execution of a negotiation ends when processes reach a final configuration. Negotiations can be deterministic (once an outcome is fixed, each process knows its unique successor node) or not.

Negotiations are an interesting model since several properties can be decided with a reasonable complexity. The question of soundness, i.e., deadlock-freedom: whether from every reachable configuration one can reach a final configuration, is PSPACE-complete. However, for deterministic negotiations, it can be decided in PTIME [START_REF] Esparza | On negotiation as concurrency primitive II: deterministic cyclic negotiations[END_REF]. The decision procedure uses reduction rules. Reduction techniques were originally proposed for Petri nets [START_REF] Desel | Reduction and design of well-behaved concurrent systems[END_REF][START_REF] Esparza | Reduction rules for colored workflow nets[END_REF][START_REF] Haddad | A reduction theory for coloured nets[END_REF]17]. The main idea is to define transformations rules that produce a model of smaller size w.r.t. the original model, while preserving the property under analysis. In the context of negotiations, [START_REF] Esparza | On negotiation as concurrency primitive II: deterministic cyclic negotiations[END_REF][START_REF] Desel | Negotiation as concurrency primitive[END_REF] proposed a sound and complete set of soundness-preserving reduction rules and algorithms to apply these rules efficiently. The question of soundness for deterministic negotiations was revisited in [START_REF] Esparza | Soundness in negotiations[END_REF] and showed NLOGSPACEcomplete using anti patterns instead of reduction rules. Further, they show that the PTIME result holds even when relaxing determinism [START_REF] Esparza | Soundness in negotiations[END_REF]. Negotiation games have also been considered to decide whether one particular process can force termination of a negotiation. While this question is EXPTIME complete in general, for sound and deterministic negotiations, it becomes PTIME [START_REF] Hoffmann | Negotiation games[END_REF].

While it is natural to consider cost or time in negotiations (e.g. think of the Brexit negotiation where time is of the essence, and which we model as running example in this paper), the original model of negotiations proposed by [START_REF] Esparza | On negotiation as concurrency primitive[END_REF] is only qualitative. Recently, [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF] has proposed a framework to associate costs to the executions of negotiations, and adapt a static analysis technique based on reduction rules to compute end-to end cost functions that are not sensitive to scheduling of concurrent nodes. For sound and deterministic negotiations, the end-to end cost can be computed in O(n.(C + n)), where n is the size of the negotiation and C the time needed to compute the cost of an execution. Requiring soundness or determinism seem perfectly reasonable, but asking sound and deterministic negotiations is too restrictive: it prevents a process from waiting for decisions of other processes to know how to proceed.

In this paper, we revisit time in negotiations. We attach time intervals to outcomes of nodes. We want to compute maximal and minimal executions times, for negotiations that are not necessarily sound and deterministic. Since we are interested in minimal and maximal execution time, cycles in negotiations can be either bypassed or lead to infinite maximal time. Hence, we restrict this study to acyclic negotiations. Notice that time can be modeled as a cost, following [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF], and the maximal execution time of a sound and deterministic negotiation can be computed in PTIME using the algorithm from [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF]. Surprisingly however, we give an example (Example 3) for which the minimal execution time cannot be computed in PTIME by this algorithm.

The first contribution of the paper shows that reachability (whether at least one run of a negotiation terminates) is NP-complete, already for (untimed) deterministic acyclic negotiations. This implies that computing minimal or maximal execution time for deterministic (but unsound) acyclic negotiations cannot be done in PTIME (unless NP=PTIME). We characterize precisely the complexities of different decision variants (threshold, equality, etc.), with complexities ranging from (co-)NP-complete to ∆ P 2 .

We thus turn to negotiations that are sound but not necessarily deterministic. Our second contribution is a new algorithm, not based on reduction rules, to compute the maximal execution time in PTIME for sound negotiations. It is based on computing the maximal execution time of critical paths in the nego-tiations. However, we show that minimal execution time cannot be computed in PTIME for sound negotiations (unless NP=PTIME): deciding whether the minimal execution time is lower than T is NP-complete, even for T given in unary, using a reduction from a Bin packing problem. This shows that minimal execution time is harder to compute than maximal execution time.

Our third contribution consists in defining a class in which the minimal execution time can be computed in (pseudo) PTIME. To do so, we define the class of k-layered negotiations, for k fixed, that is negotiations where nodes can be organized into layers of at most k nodes at the same depth. These negotiations can be executed without remembering more than k nodes at a time. In this case, we

show that computing the maximal execution time is PTIME, even if the negotiation is neither deterministic nor sound. The algorithm, not based on reduction rules, uses the k-layer restriction in order to navigate in the negotiation while considering only a polynomial number of configurations. For minimal execution time, we provide a pseudo PTIME algorithm, that is PTIME if constants are given in unary. Finally, we show that the size of constants do matter: deciding whether the minimal execution time of a k-layered negotiation is less than T is NP-complete, when T is given in binary. We show this by reducing from a Knapsack problem, yet again emphasizing that the minimal execution time of a negotiation is harder to compute than its maximal execution time.

This paper is organized as follows. Section 2 introduces the key ingredients of negotiations, determinism and soundness, known results in the untimed setting, and provides our running example modeling the Brexit negotiation. Section 3 introduces time in negotiations, gives a semantics to this new model, and formalizes several decision problems on maximal and minimal durations of runs in timed negotiations. We recall the main results of the paper in Section 4. Then, Section 5 considers timed execution problems for deterministic negotiations, Section 6 for sound negotiations, and section 7 for layered negotiations. Proof details for the last three technical sections are given in the Appendices A, B and C.

Negotiations: Definitions and Brexit example

In this section, we recall the definition of negotiations, of some subclasses (acyclic and deterministic), as well as important problems (soundness and reachability).

Definition 1 (Negotiation [START_REF] Esparza | On negotiation as concurrency primitive[END_REF][START_REF] Esparza | Static analysis of deterministic negotiations[END_REF]). A negotiation over a finite set of processes P is a tuple N = (N, n 0 , n f , X ), where:

-N is a finite set of nodes. Each node is a pair n = (P n , R n ) where P n ⊆ P is a non empty set of processes participating in node n, and R n is a finite set of outcomes of node n (also called results), with R n f = {r f }. We denote by R the union of all outcomes of nodes in N .

n 0 is the first node of the negotiation and n f is the final node. Every process in P participates in both n 0 and n f .

-For all n ∈ N , X n :

P n × R n → 2 N is a map defining the transition relation from node n, with X n (p, r) = ∅ iff n = n f , r = r f . We denote X : N × P × Fig. 1. A (sound but non-deterministic) negotiation modeling Brexit. R → 2 N the partial map defined on n∈N ({n} × P n × R n ), with X (n, p, a) = X n (p, a) for all p, a.
Intuitively, at a node n = (P n , R n ) in a negotiation, all processes of P n have to agree on a common outcome r chosen from R n . Once this outcome r is chosen, every process p ∈ P n is ready to move to any node prescribed by X (n, p, r). A new node m can only start when all processes of P m are ready to move to m.

Example 1. We illustrate negotiations by considering a simplified model of the Brexit negotiation, see Figure 1. There are 3 processes, P = {EU, P M, P a}. At first EU decides whether or not to enforce a backstop in any deal (outcome backstop) or not (outcome no-backstop). In the meantime, P M decides to proroge P a, and P a can choose or not to appeal to court (outcome court/no court). If it goes to court, then P M and P a will take some time in court (c-meet, defend), before P M can meet EU to agree on a deal. Otherwirse, P a goes to recess, and P M can meet EU directly. Once EU and P M agreed on a deal, P M tries to convince P a to vote the deal. The final outcome is whether the deal is voted, or whether Brexit is delayed.

Definition 2 (Deterministic negotiations). A process p ∈ P is deterministic iff, for every n ∈ N and every outcome r of n, X (n, p, r) is a singleton. A negotiation is deterministic iff all its processes are deterministic. It is weakly nondeterministic [START_REF] Esparza | Soundness in negotiations[END_REF] (called weakly deterministic in [START_REF] Desel | Negotiation as concurrency primitive[END_REF]) iff, for every node n, one of the processes in P n is deterministic. Last, it is very weakly non-deterministic [START_REF] Esparza | Soundness in negotiations[END_REF] (called weakly deterministic in [START_REF] Esparza | On negotiation as concurrency primitive[END_REF]) iff, for every n, every p ∈ P n and every outcome r of n, there exists a deterministic process q such that q ∈ P n for every n ∈ X (n, p, r).

In deterministic negotiations, once an outcome is chosen, each process knows the next node it will be involved in. In (very)-weakly non-deterministic negotiations, the next node might depend upon the outcome chosen in other nodes by other processes. However, once the outcomes have been chosen for all current nodes, there is only one next node possible for each process. Observe that the class of deterministic negotiations is isomorphic to the class of free choice workflow nets [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF]. Coming back to example 1, the Brexit negotiation is nondeterministic, because process P M is non-deterministic. Indeed, consider outcomes c-meet: it allows two nodes, according to whether the backstop is enforced or not, which is a decision taken by process EU . However, the Brexit negotiation is very weakly non-deterministic, as the other processes are deterministic.

Semantics: A configuration [2] of a negotiation is a mapping M : P → 2 N .
Intuitively, it tells for each process p the set M (p) of nodes p is ready to engage in.

The semantics of a negotiation is defined in terms of moves from a configuration to the next one. The initial M 0 and final M f configurations, are given by M 0 (p) = {n 0 } and M f (p) = ∅ respectively for every process p ∈ P . A configuration M enables node n if n ∈ M (p) for every p ∈ P n . When n is enabled, a decision at node n can occur, and the participants at this node choose an outcome r ∈ R n . The occurrence of (n, r) produces the configuration M given by M (p) = X (n, p, r) for every p ∈ P n and M (p) = M (p) for remaining processes in P \ P n .

Moving from

M to M after choosing (n, r) is called a step, denoted M n,r --→ M . A run of N is a sequence (n 1 , r 1 ), (n 2 , r 2 )...(n k , r k ) such that there is a sequence of configurations M 0 , M 1 , . . . , M k and every (n i , r i ) is a step between M i-1 and M i .
A run starting from the initial configuration and ending in the final configuration is called a final run. By definition, its last step is (n f , r f ).

An important class of negotiations in the context of timed negotiations are acyclic negotiations, where infinite sequence of steps are impossible:

Definition 3 (Acyclic negotiations). The graph of a negotiation N is the labeled graph G N = (V, E) where V = N , and E = {((n, (p, r), n ) | n ∈ X (n, p, r)}, with pairs of the form (p, r) being the labels. A negotiation is acyclic iff its graph is acyclic. We denote by P aths(G N ) the set of paths in the graph of a negotiation. These paths are of the form π = (n 0 , (p 0 , r 0 ), n 1 ) . . .

(n k-1 , (p k , r k ), n k ).
The Brexit negotiation of Fig. 1 is an example of acyclic negotiation. Despite their apparent simplicity, negotiations may express involved behaviors as shown with the Brexit example. Indeed two important questions in this setting are whether there is some way to reach a final node in the negotiation from (i) the initial node and (ii) any reachable node in the negotiation.

Definition 4 (Soundness and Reachability).

1. A negotiation is sound iff every run from the initial configuration can be extended to a final run. The problem of soundness is to check if a given negotiation is sound.

2. The problem of reachability asks if a given negotiation has a final run.

Notice that the Brexit negotiation of Fig. 1 is sound (but not deterministic).

It seems hard to preserve the important features of this negotiation while being both sound and deterministic. The problem of soundness has received considerable attention. We summarize the results about soudness in the next theorem:

Theorem 1. Determining whether a negotiation is sound is PSPACE-Complete.

For (very-)weakly non-deterministic negotiations, it is co-NP-complete [START_REF] Esparza | Soundness in negotiations[END_REF]. For acyclic negotiations, it is in DP and co-NP-Hard [START_REF] Esparza | On negotiation as concurrency primitive[END_REF]. Determining whether an acyclic weakly non-deterministic negotiation is sound is in PTIME [START_REF] Desel | Negotiation as concurrency primitive[END_REF][START_REF] Esparza | Soundness in negotiations[END_REF]. Finally, deciding soundness for deterministic negotiation is NLOGSPACE-complete [START_REF] Esparza | Soundness in negotiations[END_REF].

Checking reachability is NP-complete, even for deterministic acyclic negotiations (surprisingly, we did not find this result stated before in the literature):

Proposition 1.

Timed Negotiations

In many negotiations, time is an important feature to take into account. For instance, in the Brexit example, with an initial node starting at the begining of September 2019, there are 9 weeks to pass a deal till the 31 st October deadline.

We extend negotiations by introducing timing constraints on outcomes of nodes, inspired by time Petri nets [START_REF] Merlin | A Study of the Recoverability of Computing Systems[END_REF] and by the notion of negotiations with costs [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF]. We use time intervals to specify lower and upper bounds for the duration of negotiations. More precisely, we attach time intervals to pairs (n, r)

where n is a node and r an outcome. In the rest of the paper, we denote by γ + (n, r)) the lower bound (resp. the upper bound) of γ(n, r).

I
Example 2. In the Brexit example, we define the following timed constraints γ.

We only specify the outcome names, as the timing only depends upon them.

Backstop and no-backstop both take between 1 and 2 weeks: γ(backstop) = γ(no-backstop) = [START_REF] Desel | Reduction and design of well-behaved concurrent systems[END_REF][START_REF] Desel | Negotiation as concurrency primitive[END_REF]. In case of no-court, recess takes 5 weeks γ(recess) = Semantics: A timed valuation is a map µ : P → R ≥0 that associates a nonnegative real value to every process. A timed configuration is a pair (M, µ) where M is a configuration and µ a timed valuation. There is a timed step from (M, µ)

to (M , µ ), denoted (M, µ) (n,r) ---→ (M , µ ), if (i) M (n,r) ---→ M , (ii) p / ∈ P n implies µ (p) = µ(p) (iii) p ∈ P n implies (µ (p) -max p ∈Pn µ(p )) ∈ γ(n, r)
Intuitively a timed step (M, µ)

(n,r)

---→ (M , µ ) depicts a decision taken at node n, and how long each process of P n waited in that node before taking decision (n, r). The last process engaged in n must wait for a duration contained in γ(n, r). However, other processes may spend a time greater than γ + (n, r).

A timed run is a sequence of steps ρ = (M 1 , µ 1 )

e1 -→ (M 2 , µ 2 ) . . . (M k , µ k )
where each

(M i , µ i ) ei -→ (M i+1 , µ i+1 ) is a timed step. It is final if M k = M f . Its execution time δ(ρ) is defined as δ(ρ) = max p∈P µ k (p).
Notice that we only attached timing to processes, not to individual steps.

With our definition of runs, timing on steps may not be monotonous (i.e., nondecreasing) along the run, while timing on processes is. Viewed by the lens of concurrent systems, the timing is monotonous on the partial orders of the system rather than the linearization. It is not hard to restrict paths, if necessary, to have a monotonous timing on steps as well. In this paper, we are only interested in execution time, which does not depend on the linearization considered.

Given a timed negotiation N , we can now define the minimum and maximum execution time, which correspond to optimistic or pessimistic views:

Definition 7.
Let N be a timed negotiation. Its minimum execution time, denoted mintime(N ) is the minimal δ(ρ) over all final timed run ρ of N . We define the maximal execution time maxtime(N ) of N similarly.

Given T ∈ N, the main problems we consider in this paper are the following:

-The mintime problem, i.e., do we have mintime(N ) ≤ T ?.

In other words, does there exist a final timed run ρ with δ(ρ) ≤ T ?

-The maxtime problem, i.e., do we have maxtime(N ) ≤ T ?.

In other words, does δ(ρ) ≤ T for every final timed run ρ?

These questions have a practical interest : in the Brexit example, the question "is there a way to have a vote on a deal within 9 weeks ?" is indeed a minimum execution time problem. We also address the equality variant of these decision problems, i.e., mintime(N ) = T : is there a final run of N that terminates in exactly T time units and no other final run takes less than T time units?

Similarly for maxtime(N ) = T .

Example 3. We use Fig. 1 to show that it is not easy to compute the minimal execution time, and in particular one cannot use the algorithm from [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF] to compute it. Consider the node n with P n = {P M, P a} and R n = {court, no court}.

If the outcome is court, then P M needs 2 weeks before he can talk to EU and P a needs at least 3 weeks before he can debate. However, if the outcome is no court, then P M need not wait before he can talk to EU , but P a wastes 5 weeks in recess. This means that one needs to remember different alternatives which could be faster in the end, depending on the future. On the other hand, the algorithm from [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF] attaches one minimal time to process P a, and one minimal time to process P M . No matter the choices (0 or 2 for P M and 3 or 5 for P a), there will be futures in which the chosen number will over or underapproximate the real minimal execution time (this choice is not explicit in [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF]) 4 . For maximum execution time, it is not an issue to attach to each node a unique maximal execution time. The reason for the asymmetry between minimal execution time and maximal execution time of a negotiation is that the execution time of a path is max p∈P µ k (p), for µ k the last timed valuation, hence breaking the symmetry between min and max.

High Level view of the main results

In this section, we give a high-level description of our main results. Formal statements can be found in the sections where they are proved. We gather in Fig. 2 the precise complexities for the minimal and the maximal execution time problems for 3 classes of negotiations that we describe in the following. Since we are interested in minimum and maximum execution time, cycles in negotiations can be either bypassed or lead to infinite maximal time. Hence, while we define timed negotiations in general, we always restrict to acyclic negotiations (such as Brexit) while stating and proving results.

In [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF], a PTIME algorithm is given to compute different costs for negotiations that are both sound and deterministic. One limitation of this result is that it cannot compute the minimum execution time, as explained in Example 3. A second limitation is that the class of sound and deterministic negotiations is quite restrictive: it cannot model situations where the next node a process participates in depends on the outcome from another process, as in the Brexit example. We thus consider classes where one of these restrictions is dropped.

We first consider (Section 5) negotiations that are deterministic, but without the soundness restriction. We show that for this class, no timed problem we consider can be solved in PTIME (unless NP=PTIME). Further, we show that the equality problems (maxtime/mintime(N ) = T ), are complete for the complexity class DP, i.e., at the second level of the Boolean Hierarchy [START_REF] Papadimitriou | The complexity of facets (and some facets of complexity)[END_REF].

We then consider (Section 6) the class of negotiations that are sound, but not necessarily deterministic. We show that maximum execution time can be solved in PTIME, and propose a new algorithm. However, the minimum execution time cannot be computed in PTIME (unless NP=PTIME). Again for the mintime equality problem we have a matching DP-completeness result.

Finally, in order to obtain a polytime algorithm to compute the minimum execution time, we consider the class of k-layered negotiations (see Section 7):

Given k ∈ N, we can show that maxtime(N ) can be computed in PTIME for k-layered negotiations. We also show that while the mintime(N ) ≤ T ? problem is weakly NP-complete for k-layered negotiations, we can compute mintime(N ) in pseudo-PTIME, i.e. in PTIME if constants are given in unary.

Deterministic Sound k-layered Max ≤ T Max = T co-NP-complete (Thm. 3) DP-complete (Prop. 2) PTIME (Prop. 3) PTIME (Thm. 6) Min ≤ T NP-complete (Thm. 3) NP-complete (Thm. 5) pseudo-PTIME (Thm. 8) NP-complete (Thm. 7) Min = T DP-complete (Prop. 2) DP-complete (Prop. 4) pseudo-PTIME (Thm. 8)
Fig. 2. Results for acyclic timed negotiations. DP refers to the complexity class, Difference Polynomial time [START_REF] Papadimitriou | The complexity of facets (and some facets of complexity)[END_REF], the second level of the Boolean Hierarchy. hardness holds even for very weakly non-deterministic negotiations, and T in unary. hardness holds even for sound and very weakly non-deterministic negotiations.

Deterministic Negotiations

We start by considering the class of deterministic acyclic negotiations. We show that both maximal and minimal execution time cannot be computed in PTIME (unless NP=PTIME), as the threshold problems are (co-)NP-complete.

Theorem 3. The mintime(N ) ≤ T decision problem is NP complete, and the maxtime(N ) ≤ T decision problem is co-NP complete for acyclic deterministic timed negotiations.

Proof. For mintime(N ) ≤ T , containment in NP is easy: we just need to guess a run ρ (of polynomial size as N is acyclic), consider the associated timed run ρ - where all decisions are taken at their earliest possible dates, and check whether

δ(ρ -) ≤ T , which can be done in time O(|N |+log T ).
For the hardness, we give the proof in two steps. First, we start with a proof of Proposition 1 that reachability problem is NP-hard using reduction of 3-CNF SAT, i.e., given a formula φ, we build a deterministic negotiation N φ s.t. φ is satisfiable iff N φ has a final run. In a second step, we introduce timings on this negotiation and show that mintime(N φ ) ≤ T iff φ is satisfiable.

Step 1: Reducing 3-CNF-SAT to Reachability problem.

Given a boolean formula φ with variables v i , 1 ≤ i ≤ n and clauses c j , 1 ≤ j ≤ m, for each variable v i we define the sets of clauses

S i,t = {c j |v i is present in c j } and S i,f = {c j |¬v i is present in c j }.
Clauses in S i,t and S i,f are naturally ordered: c i < c j iff i < j. We denote these elements S i,t (1) < S i,t (2) < . . ..

Similarly for set S i,f . Now, we construct a negotiation N φ (as depicted in Figure 3) with a process V i for each variable v i and a process C j for each clause c j :

-Initial node n 0 has a single outcome r taking each process C j to node Lone cj , and each process V i to node Lone vi .

-Lone cj has three outcomes: if literal v i ∈ c j , then t i is an outcome, taking

V i to P air cj ,vi , and if literal ¬v i ∈ c j , then f i is an outcome, taking V i to P air cj ,¬vi .

-The outcomes of Lone vi are true and false. Outcome true brings v i to node T lone vi,1 and outcome false brings v i to node F lone vi,1 .

-We have a node T lone vi,j for each j ≤ |S i,t | and F lone vi,j for each j ≤ |S i,f |, with V i as only process. Let c r = S i,t (j). Node T lone vi,j has two outcomes

vton bringing V i to T lone vi,j+1 (or n f if j = |S i,t |)
, and vtoc i,r bringing V i to P air cr,vi . The two outcomes from F lone vi,j are similar.

-Node P air cr,vi has V i and C r as its processes and one outcome ctof which takes process C j to final node n f and process V i to T lone vi,j+1 (with c r = S i,t (j)), or to n f if j = |S i,t |. Node P air cr,¬vi is defined in the same way from F lone vi,j .

With this we claim that N φ has a final run iff φ is satisfiable which completes the first step of the proof. We give a formal proof of this claim in Appendix A.

Observe that the negotiation N φ constructed is deterministic and acyclic (but it is not sound). Vi Ck

fi v t o ci ,k ti 4 ti 5 V1 Vi Vn C1 Cj Ck Cm ctof c t o f ctof n0 Lonev i Lonec j Lonec k T lonev i,1 F lonev i,1 F lonev i,r F lonev i,r+1 P airc j ,¬vi nf [2, 2] [2, 2] Fig. 3. A part of N φ where clause cj is (i2 ∨ ¬i ∨ ¬i3) and clause c k is (i4 ∨ ¬i ∨ i5).
Timing is [0, 0] whereever not mentioned

Step 2: Before we introduce timing on N φ , we introduce a new outcome r at n 0 which takes all processes to n f . Now, the timing function γ associated with the N φ is: γ(n 0 , r) = [2, 2] and γ(n 0 , r ) = [START_REF] Knuth | Fundamental Algorithms, volume 1 of The Art of Computer Programming[END_REF][START_REF] Knuth | Fundamental Algorithms, volume 1 of The Art of Computer Programming[END_REF] and γ(n, r) = [0, 0], for all node n = n 0 and all r ∈ R n . Then, mintime(N φ ) ≤ 2 iff φ has a satisfiable assignment: if mintime(N φ ) ≤ 2, there is a run with decision r taken at n 0 which is final. But existence of any such final run implies satisfiability of φ. For reverse implication, if φ is satisfiable, then the corresponding run for satisfying assignment takes 2 units time, which means that mintime(N φ ) ≤ 2.

Similarly, we can prove that the MaxTime problem is co-NP complete by changing γ(n 0 , r ) = [1, 1] and asking if maxtime(N φ ) > 1 for the new N φ . The answer will be yes iff φ is satisfiable.

We now consider the related problem of checking if mintime(N ) = T (or if maxtime(N ) = T ). These problems are harder than their threshold variant under usual complexity assumptions: they are DP-complete (Difference Polynomial

V1 Vn C1 Cm V 1 V n C 1 C m r r r r Structure of Nφ V1 Vn C1 Cm V 1 V n C 1 C m r r r r vton vton ctof ctof r r r r Structure of N φ V 1 V n C 1 C m rall rall rall rall V1 Vn C1 Cm V 1 V n C 1 C m r, rall r, rall r, rall r, rall r all r all r all r all vton vton ctof ctof n0 nsep nf nall [0, 0] [0, 0] [2, 2] [1, 1] Fig. 4. Structure of N φ,φ
time class, i.e., second level of the Boolean Hierarchy, defined as intersection of a problem in NP and one in co-NP [START_REF] Papadimitriou | The complexity of facets (and some facets of complexity)[END_REF]).

Proposition 2. The mintime(N ) = T and maxtime(N ) = T decision problems are DP-complete for acyclic deterministic negotiations.

Proof. We only give the proof for mintime (the proof for maxtime is given in Appendix A). Indeed, it is easy to see that this problem is in DP, as it can be written as mintime(N ) ≤ T which is in NP and ¬(mintime(N

) ≤ T -1)),
which is in co-NP. To show hardness, we use the negotiation constructed in the above proof as a gadget, and show a reduction from the SAT-UNSAT problem (a standard DP-complete problem).

The SAT-UNSAT Problem asks given two Boolean expressions φ and φ , both in CNF forms with three literals per clause, is it true that φ is satisfiable and φ is unsatisfiable? SAT-UNSAT is known to be DP-complete [START_REF] Papadimitriou | The complexity of facets (and some facets of complexity)[END_REF]. We reduce this problem to mintime(N ) = T .

Given φ, φ , we first make the corresponding negotiations N φ and N φ as in the previous proof. Let n 0 and n f be the initial and final nodes of N φ and n 0 and n f be the initial and final nodes of N φ .(Similarly, for other nodes we write above the nodes to signify they belong to N φ ).

In the negotiation N φ , we introduce a new node n all , in which all the processes participate (see Figure 4). The node n all has a single outcome r all which sends all the processes to n f . Also, for node n 0 , apart from the outcome r which sends all processes to different nodes, there is another outcome r all which sends all the processes to n all . Now we merge the nodes n f and n 0 and call the merged node n sep . Also nodes n 0 and n f now have all the processes of N φ and N φ participating in them. This merged process gives us a new negotiation N φ,φ in which the structure above n sep is same as N φ while below it is same as N φ . Node n sep now has all the processes of N φ and N φ participating in it. The outcomes of n sep will be same as that of n 0 (r all , r). For both the outcomes of n sep the processes corresponding to N φ directly go to n f of the N φ,φ . Similarly n 0 of N φ,φ which is same n 0 of N φ, sends processes corresponding to N φ directly to n sep for all its outcomes. We now define timing function γ for N φ,φ which is as follows: γ(Lone vi , r) = [1, 1] for all v i ∈ φ and r ∈ {true, false}, γ(n all , r all ) = [2, 2] and γ(n, r) = [0, 0] for all other outcomes of nodes. With this construction, one can conclude that mintime(N φ,φ ) = 2 iff φ is satisfiable and φ is unsatisfiable (see Appendix for details). This completes the reduction and hence proves DP-hardness.

Finally, we consider a related problem of computing the min and max time.

To consider the decision variant, we rephrase this problem as checking whether an arbitrary bit of the minimum execution time is 1. Perhaps surprisingly, we obtain that this problem goes even beyond DP, the second level of the Boolean Hierarchy and is in fact hard for ∆ P 2 (second level of the polynomial hierarchy), which contains the entire Boolean Hierarchy. Formally, Theorem 4. Given an acyclic deterministic timed negotiation and a positive integer k,computing the k th bit of the maximum/minimum execution time is

∆ P 2 -complete.
Finally, we remark that if we were interested in the optimization variant and not the decision variant of the problem, the above proof can be adapted to show that these variants are OptP-complete (as defined in [START_REF] Mark | The complexity of optimization problems[END_REF]). But as optimization is not the focus of this paper, we avoid formal details of this proof.

Sound Negotiations

Sound negotiations are negotiations in which every run can be extended to a final run, as in Fig. 1. In this section, we show that maxtime(N ) can be computed in PTIME for sound negotiations, hence giving PTIME complexities for the maxtime(N ) ≤ T ? and maxtime(N ) = T ? questions. However, we

show that mintime(N ) ≤ T is NP-complete for sound negotiations, and that

mintime(N ) = T is DP-complete, even if T is given in unary. Consider the graph G N of a negotiation N . Let π = (n 0 , (p 0 , r 0 ), n 1 ) • • • (n k , (p k , r k ), n k+1
) be a path of G N . We define the maximal execution time of a path π as the value δ + (π) = i∈0..k γ + (n i , r i ). We say that a path π = (n 0 , (p 0 , r 0 ), n 1 )

• • • (n , (p , r ), n +1 ) is a path of some run ρ = (M 1 , µ 1 ) (n1,r 1 ) -→ • • • (M k , µ k ) if r 0 , . . . , r is a subword of r 1 , . . . , r k .
Lemma 1. Let N be an acyclic and sound timed negotiation. Then maxtime(N )

= max π∈P aths(G N ) δ + (π) + γ + (n f , r f ).
Proof. Let us first prove that maxtime(N ) ≥ max π∈P aths(G N ) δ + (π)+γ + (n f , r f ).

Consider any path π of G N , ending in some node n. First, as N is sound, we can compute a run ρ π such that π is a path of ρ π , and ρ π ends in a configuration in which n is enabled. We associate with ρ π the timed run ρ + π which associates to every node the latest possible execution date. We have easily δ(ρ + π ) ≥ δ(π), and then we obtain max π∈P aths(G N ) δ(ρ + π ) ≥ max π∈P aths(G N ) δ(π). As maxtime(N ) is the maximal duration over all runs, it is hence necessarily greater

than max π∈P aths(G N ) δ(ρ + π ) + γ + (n f , r f ).
We now prove that maxtime(N ) ≤ max π∈P aths(G N ) δ + (π)+γ + (n f , r f ). Take

any timed run ρ = (M 1 , µ 1 ) (n1,r1) -→ • • • (M k , µ k )
of N with a unique maximal node n k . We show that there exists a path π of ρ such that δ(ρ) ≤ δ + (π) by induction on the length k of ρ. The initialization is trivial for

k = 1. Let k ∈ N. Because n k is the unique maximal node of ρ, we have δ(ρ) = max p∈Pn k µ k-1 (p) + γ + (n k , r k ).
We choose one p k-1 maximizing µ k-1 (p). Let < k be the maximal index of a decision involving process p k-1 (i.e. p k-1 ∈ P n ). Now, consider the timed run ρ subword of ρ, but with n as unique maximal node (that is, it is ρ where nodes n i , i > has been removed, but also where some nodes n i , i < have been removed if they are not causally before n (in particular, P ni ∩ P n = ∅).

By definition, we have that δ(ρ) = δ(ρ A direct consequence is that maxtime(N ) ≤ T and maxtime(N ) = T problems can be solved in polynomial time when N is sound. Notice that if N is deterministic but not sound, then Lemma 1 does not hold: we only have an inequality.

) + γ + (n , r ) + γ + (n k , r k ).
We now turn to mintime(N ). We show that it is strictly harder to compute for sound negotiations than maxtime(N ). The hardness part is obtained by reduction from the Bin Packing problem. The reduction is similar to Knapsack, that we will present in Thm. 7. The difference is that we use bins in parallel, rather than 2 process, one for the weight and one for the value. The hardness is thus strong, but the negotiation is not k-layered for a bounded k (It is 2 + 1 bounded, with depending on the input). A detailed proof is given in Appendix B.

We show that mintime(N ) = T is harder to decide than mintime(N ) ≤ T , with a proof similar to Prop. 2. An open question is whether the minimal execution time can be computed in PTIME if the negotiation is both sound and deterministic. The reduction from Bin Packing does not work with deterministic (and sound) negotiations.

k-Layered Negotiations

In the previous sections, we have considered sound negotiations, and deterministic negotiations. For both classes, computing the minimal execution time cannot be done in PTIME (unless NP=PTIME), even if constants are given in unary.

In this section, we consider k-layeredness (see Section 2), a syntactic property that can be efficiently verified (it suffices to compute the depth of each node, which can be done in polynomial time).

Algorithmic properties

Let k be a fixed integer. We first show that the maximum execution time can be computed in PTIME for k-layered negotiations. Let N i be the set of nodes at layer i. We define for every layer i the set S i of subsets of nodes X ⊆ N i which can be jointly enabled and such that for every process p, there is exactly one node n(X, p) in X with p ∈ n(X, p). Formally, we define S i inductively. We start with S 0 = {n 0 }. We then define S i+1 from the contents of layer S i : we have Y ∈ S i+1 iff n∈Y P n = P and there exist X ∈ S i and an outcome r m ∈ R m for every m ∈ X, such that n ∈ X (n(X, p), p, r m ) for each n ∈ Y and p ∈ P n . We then keep for each subset X ∈ S i and each node n ∈ X, the maximal time f i (n, X) ∈ N associated with n and X. From S i+1 and f i , we inductively compute f i+1 in the following way: for all X ∈ S i with successor Y ∈ S i+1 for outcomes (r p ) p∈P , we denote f i+1 (Y, n, X) = max p∈P (n) f i (X, n(X, p)) + γ + (n(X, p), r p ). If there are several choices of (r p ) p∈P leading to the same Y , we take r p with the maximal f i (X, n(X, p)) + γ + (n(X, p), r p ). We then define f i+1 (Y, n) = max X∈Si f i+1 (Y, n, X). Again, the initialization is trivial, with f 0 ({n 0 }, n 0 ) = 0. The maximal execution time of N is f ({n f }, n f ). k * = max X∈ i Si |X| ≤ k. We say that N is k * -thread bounded, meaning that there cannot be more that k * nodes in the same context X of any layer.

Usually, k * is strictly smaller than k = max i |N i |, as N i = X∈Si X.

Consider again the Brexit example

Minimal Execution Time

As with sound negotiations, computing minimal time is much harder than computing the maximal time for k-layered negotiations: Let us now show that the problem is NP-hard. We proceed by reduction from the Knapsack decision problem. Let us consider a set of items U = {u 1 , . . . u n } of respective values v 1 , . . . v n and weight w 1 , . . . , w n and a knapsack of maximal capacity W . The knapsack problem asks, given a value V whether there exists a subset of items U ⊆ U such that ui∈U v i ≥ V and such that ui∈U w i ≤ W .

We build a negotiation with 2n processes P = {p 1 , . . . p 2n }, as shown in Fig. 5. Intuitively, p i , i ≤ n will serve to encode the value of selected items as timing, while p i , i > n will serve to encode the weight of selected items as timing.

Concerning timing constraints for outcomes we do the following: Outcomes 0, yes and no are associated with [0, 0]. Outcome c i is associated with [w i , w i ], the weight of u i . Last, outcome b i is associated with a more complex function,

such that i b i ≤ W iff i v i ≥ V . For that, we set [ (vmax-vi)W n•vmax-V , vmaxW n•vmax-vi ] for outcome b i
, where v max is the largest value of an item, and V is the total value we want to reach at least. Also, we set [ (vmax)W n•vmax-V , vmaxW n•vmax-vi ] for outcome a i . We set T = W , the maximal weight of the knapsack. Now, consider a final run ρ in N . The only choices in ρ are outcomes yes or no from C 1 , . . . , C n . Let I be the set of indices such that yes is the outcome from all C i in this path. We obtain δ(ρ) = max( i / ∈I a i + i∈I b i , i∈I c i ). We have δ(ρ) ≤ T = W iff i∈I w i ≤ W , that is the sum of the weights is lower than W , and i /

∈I (vmax)W n•vmax-V + i∈I (vmax-vi)W n•vmax-V ≤ W . That is, n • v max -i∈I v i ≤ n • v max -V , i.e. i∈I v i ≥ V .
Hence, there exists a path ρ with δ(ρ) ≤ T = W iff there exists a set of items of weight less than W and of value more than V .

It is well known that Knapsack is weakly NP-hard, that is, it is NP-hard only when weights/values are given in binary. This means that Thm. 7 shows that minimum execution time ≤ T is NP-hard only when T is given in binary. We can actually show that for k-layered negotiations, the mintime(N ) ≤ T problem can be decided in PTIME if T is given in unary (i.e. if T is not too large): Proof. We will remember for each layer i a set T i of functions τ from nodes N i of layer i to a value in {1, . . . , T, ⊥}. Basically, we have τ ∈ T i if there exists a path ρ reaching X = {n ∈ N i | f (n) = ⊥}, and this path reaches node n ∈ X after τ (n) time units. As for S i , for all p, we should have a unique node n(τ, p) such that p ∈ n(f, p) and τ (n(τ, p)) = ⊥. Again, it is easy to initialize T 0 = {τ 0 }, with τ 0 (n 0 ) = 0, and τ 0 (n) = ⊥ for all n = n 0 .

Inducively, we build T i+1 in the following way: τ i+1 ∈ T i+1 iff there exists a τ i ∈ T i and r p ∈ R n(τi,p) for all p ∈ P such that for all n with τ i+1 (n) = ⊥, we

have τ i+1 (n) = max p τ i (n(τ i , p)) + γ(n(τ i , p), r p ).
We have that the minimum execution time for N is min τ ∈Tn τ (n τ ), for n the depth of n f . There are at most T k functions τ in any T i , and there are at most |N | layers to consider, giving the complexity.

As with Thm. 6, we can more accurately state the complexity as

O(d(N ) • C(N ) • ||R|| k * • T k * -1
). The k * -1 is because we only need to remember minimal functions τ ∈ T i : if τ (n) ≥ τ (n) for all n, then we do not need to keep τ in T i .

In particular, for the knapsack encoding in the proof of Thm. 7, we have k * = 3,

||R|| = 2 and C(N ) = 4.
Notice that if k is part of the input, then the problem is strongly NP-hard, even if T is given in unary, as e.g. encoding bin packing with bins result to a 2 + 1-layered negotiations.

Conclusion

In this paper, we considered timed negotiations. We believe that time is of the essence in negotiations, as examplified by the Brexit negotiation. It is thus important to be able to compute in a tractable way the minimal and maximal execution time of negotiations.

We showed that we can compute in PTIME the maximal execution time for acyclic negotiations that are either sound or k-layered, for k fixed. We showed that we cannot compute in PTIME the maximal execution time for negotiations that are not sound nor k-layered, even if they are deterministic and acyclic (unless NP=PTIME). We also showed that surprisingly, computing the minimal execution time is much harder, with strong NP-hardness results in most of the classes of negotiations, contradicting a claim in [START_REF] Esparza | Static analysis of deterministic negotiations[END_REF]. We came up with a new reasonable class of negotiations, namely k-layered negotiations, which enjoys a pseudo PTIME algorithm to compute the minimal execution time. That is, the algorithm is PTIME when the timing constants are given in unary. We showed that this restriction is necessary, as the problem becomes NP-hard for constants given in binary, even when the negotiation is sound and very weakly non-deterministic. The problem to know whether the minimal execution time can be computed in PTIME for deterministic and sound negotiation remains open. Proof. For mintime(N ) ≤ T , containment in NP is easy: we just need to guess a run ρ (of polynomial size as N is acyclic), consider the associate timed run ρ - where all decisions are taken at their earliest possible dates, and check whether δ(ρ -) ≤ T , which can be done in time O(|N |+log T ).

For the hardness, we give the proof in two steps. First, we start with a proof of Proposition 1 that reachability problem is NP-hard using reduction of 3-CNF SAT, i.e., given a formula φ, we build a deterministic negotiation N φ s.t. φ is satisfiable iff N φ has a final run. In a second step, we introduce timings on this negotiation and show that mintime(N φ ) ≤ T iff φ is satisfiable.

Step 1: Reducing 3-CNF-SAT to Reachability problem.

Given a boolean formula φ with variables v i , 1 ≤ i ≤ n and clauses c j , 1 ≤ j ≤ m, for each variable v i we define the sets of clauses S i,t = {c j |v i is present in c j } and S i,f = {c j |¬v i is present in c j }. Clauses in S i,t and S i,f are naturally ordered: c i < c j iff i < j. We denote these elements S i,t (1) < S i,t (2) < . . .. Similarly for set S i,f . Now, we construct a negotiation N φ with a process V i for each variable v i and a process C j for each clause c j :

-Initial node n 0 has a single outcome r taking each process C j to node Lone cj , and each process V i to node Lone vi .

-Lone cj has three outcomes: if literal v i ∈ c j , then t i is an outcome, taking V i to P air cj ,vi , and if literal ¬v i ∈ c j , then f i is an outcome, taking V i to P air cj ,¬vi .

-The outcomes of Lone vi are true and false. Outcome true brings v i to node T lone vi,1 and outcome false brings v i to node F lone vi,1 .

-We have a node T lone vi,j for each j ≤ |S i,t | and F lone vi,j for each j ≤ |S i,f |, with V i as only process. Let c r = S i,t (j). Node T lone vi,j has two outcomes vton bringing V i to T lone vi,j+1 (or n f if j = |S i,t |), and vtoc i,r bringing V i to P air cr,vi . The two outcomes from F lone vi,j are similar.

-Node P air cr,vi has V i and C r as its processes and one outcome ctof which takes process C j to final node n f and process V i to T lone vi,j+1 (with c r = S i,t (j)), or to n f if j = |S i,t |. Node P air cr,¬vi is defined in the same way from F lone vi,j .

v to ci ,j ctof ti 2 fi 3 Vi C k fi v t o ci ,k ti 4 ti 5 V1 Vi Vn C1 Cj C k Cm vton ctof ctof c t o f ctof n0 Lonev i Lonec j Lonec k T lonev i,1 F lonev i,1 F lonev i,r F lonev i,r+1 P airc j ,¬vi nf [2, 2] [2, 2] Fig. 3. A part of N φ where clause cj is (i2 ∨ ¬i ∨ ¬i3) and clause c k is (i4 ∨ ¬i ∨ i5).
Timing is [0, 0] whereever not mentioned Claim. N φ has a final run iff φ is satisfiable.

Proof. First we show that if there is a run ρ from n 0 to n f then φ is satisfiable.

In ρ, all processes reached n f . So each process V i takes either outcome true or false in ρ. Let val the valuation associated each variable v i with the choice true or false by V i . We now show that all clause c r have at least one literal true in val. In ρ, process C r reaches the final node n f : it must have gone via one node either P air cr,vi or P air cr,¬vi , for some i. Wlog, let us assume that C r went to P air cr¬vi . The only way it is possible is for process V i to have been in

F lone vi,j , with c r = S i,f (j). This is possible only if V i decided outcome false at Lone vi . So this implies that literal ¬v i of c j is true in val. Hence φ is satisfiable.

Conversely, we show that if φ is satisfiable then N φ has final run. Let val a satisfiable assignment val : V → {true,false} for φ. We build a run ρ which is final. After reaching Lone vi , V i will decide the outcome according to the value of val(v i ) and reach F lone vi,1 or T lone vi,1 accordingly. Let G i (val) be the set of clause c j such that i is the minimal literal of c j true under val. When there is a choice between two outcomes vton and vtoc i,k for process V i , the run chooses

vtoc i,k iff k ∈ G i (val). Concerning C j , it appears in exactly one G i (val), because val satisfies φ. If val(v i ) = true, run ρ chooses outcome t i for V i in node Lone cj ,
and outcome

f i if val(v i ) = false.
Observe that the same variable v i can be associated with several clauses c j , but then all these clauses go to the same type of nodes i.e. P air cj ,vi if val(v i ) = true and P air cj ,¬vi if val(v i ) = false.

This run ρ is final: Every process C j reaches n f after participating in exactly one node P air cj ,vi or P air cj ,¬vi . Every process V i reaches n f after participating in zero or more node P air cj ,vi or P air cj ,¬vi (it participates in exactly |G i | such nodes).

With this we claim that N φ has a final run iff φ is satisfiable which completes the first step of the proof. Observe that the negotiation N φ constructed is deterministic and acyclic (but it is not sound).

Step 2: Before we introduce timing on N φ , we introduce a new outcome r at n 0 which takes all processes to n f . Now, the timing function γ associated with the N φ is: γ(n 0 , r) = [2, 2] and γ(n 0 , r ) = [START_REF] Knuth | Fundamental Algorithms, volume 1 of The Art of Computer Programming[END_REF][START_REF] Knuth | Fundamental Algorithms, volume 1 of The Art of Computer Programming[END_REF] and γ(n, r) = [0, 0], for all node n = n 0 and all r ∈ R n . Then, mintime(N φ ) ≤ 2 iff φ has a satisfiable assignment: if mintime(N φ ) ≤ 2, there is a run with decision r taken at n 0 which is final. But existence of any such final run implies satisfiability of φ. For reverse implication, if φ is satisfiable, then the corresponding run for satisfying assignment takes 2 units time, which means that mintime(N φ ) ≤ 2.

Similarly, we can prove that the MaxTime problem is Co-NP complete by changing γ(n 0 , r ) = [1, 1] and asking if maxtime(N φ ) > 1 for the new N φ . The answer will be yes iff φ is satisfiable.

As a side note, we observe that the NP-hardness for mintime could also have been proved without introducing the new result r but then it would have been possible that N φ had no final run making mintime(N φ ) ≤ 2 vacuous.

We now consider the related problem of checking if mintime(N ) = T (or if maxtime(N ) = T ). These problems are harder than their threshold variant un- Proof. Indeed, it is easy to see that this problem is in DP, as it can be written as mintime(N ) ≤ T which is in NP and ¬(mintime(N ) ≤ T -1)), which is in co-NP. To show hardness, we use the negotiation constructed in the above proof as a gadget, and show a reduction from the SAT-UNSAT problem (a standard DP-complete problem).

V1 Vn C1 Cm V 1 V n C 1 C m r r r r Structure of Nφ V1 Vn C1 Cm V 1 V n C 1 C m r r r r vton vton ctof ctof r r r r Structure of N φ V 1 V n C 1 C m rall rall rall rall V1 Vn C1 Cm V 1 V n C 1 C m r, rall r, rall r, rall r, rall r all r all r all r all vton vton ctof ctof n0 nsep nf nall [0, 0] [0, 0] [2, 2] [1, 1]
SAT-UNSAT Problem : Given two Boolean expressions φ and φ , both in CNF forms with three literals per clause, is it true that φ is satisfiable and φ is unsatisfiable? SAT-UNSAT is known to be DP -Complete [START_REF] Papadimitriou | The complexity of facets (and some facets of complexity)[END_REF]. We reduce this problem to mintime(N ) = T .

Given φ, φ , we first make the corresponding negotiations N φ and N φ as in the previous proof. Let n 0 and n f be the initial and final nodes of N φ and n 0 and n f be the inital and final nodes of N φ .(Similarly, for other nodes we write above the nodes to signify they belong to N φ ). In the negotiation N φ , we introduce a new node n all (see Figure 4), in which all the processes participate. The node n all has a single outcome r all which sends all the processes to n f . Also, for node n 0 , apart from the outcome r which sends all processes to different nodes, there is another outcome r all which sends all the processes to n all . Now we merge the nodes n f and n 0 and call the merged node n sep . Also nodes n 0 and n f now have all the processes of N φ and N φ participating in them.

This merged process gives us a new negotiation N φ,φ in which the structure above n sep is same as N φ while below it is same as N φ . Node n sep now has all the processes of N φ and N φ participating in it. The outcomes of n sep will be same as that of n 0 (r all , r). For both the outcomes of n sep the processes corresponding to N φ directly go to n f of the N φ,φ . Similarly n 0 of N φ,φ which is same n 0 of N φ, sends processes corresponding to N φ directly to n sep for all its outcomes.

We now define timing function γ for N φ,φ which is as follows:

γ(Lone vi,r ) = [START_REF] Desel | Reduction and design of well-behaved concurrent systems[END_REF][START_REF] Desel | Reduction and design of well-behaved concurrent systems[END_REF] for all v i ∈ φ and r ∈ {true, false}, γ(n all , r all ) = [2, 2] and γ(n, r) = [0, 0] for all other outcomes of nodes.

The claim is that Claim. mintime(N φ,φ ) = 2 iff φ is satisfiable and φ is unsatisfiable.

Proof. If mintime(N φ,φ ) = 2, this implies that φ is satisfiable, for if it was not satifiable then for no run, all the processes corresponding to φ could reach n sep and therefore the negotiation could not complete and hence MinTime would be infinite. Also φ is unsatisfiable because if it would have been satisfiable then there would have been a final run in which the processes after reaching n sep choose the outcome r from n sep and complete the negotiation. The time for that run would be 1 unit and therefore the mintime(N φ,φ ) = 2.

For the other side of the implication, we can argue similarly that if φ is satisfiable then the processes of N φ would complete the structure above n sep and reach n sep in 0 units of time. From there the processes would have to choose the outcome r all to reach n f because otherwise, the run would not be final. The time taken for the path would be 2 units. So total time associated will this run will be 2 units which will also be the mintime(N φ,φ ).

For equality decision problem of MaxTime, the proof is similar; only the γ(Lone vi , r) = [START_REF] Desel | Negotiation as concurrency primitive[END_REF][START_REF] Desel | Negotiation as concurrency primitive[END_REF] for all v i ∈ φ , γ(n all , r all ) = [1, 1] and γ(n, r) = [0, 0] for all other nodes. The question asked is maxtime(N φ,φ ) = 2 which is true if only if φ is satisfiable and φ is unsatisfiable.

Finally, we consider a related problem of deciding if a bit of mintime(N ) is 1 (or similarly with maxtime(N )). Perhaps surprisingly, we obtain that these problems goes even beyond DP (the second level of the Boolean Hierarchy) and is in fact hard for ∆ P 2 , which contains the whole Boolean Hierarchy:

Theorem 4. Given an acyclic deterministic timed negotiation and a positive integer k, computing the k th bit of the maximum/minimum execution time is

∆ P 2 complete.
Proof. Containment is again relatively easy. Given an acyclic deterministic timed negotiation, we can compute the largest possible time attainable as a function of the number of nodes and maximal constant in each node. Now guess the min/max time (in binary) and then check it using NP-oracle or equivalently Co-NP oracle calls.

The hardness is not so simple to obtain. We first notice that it suffices to show the problem of whether maxtime/mintime(N ) = odd ? is ∆ p 2 hard. This is because odd or even is the same as the last bit. We first show that maxtime(N ) = odd is ∆ p 2 complete.

Consider the following problem: Given a Boolean formula φ(x 1 , x 2 , ...x n ), is

x n = 1 in the lexicographically largest satisfying assignment of φ?

The above problem is known to be ∆ p 2 complete [START_REF] Mark | The complexity of optimization problems[END_REF] and we reduce it to the decision problem of maxtime(N ) = odd? First, we convert φ to 3

v i = x i for i ≤ n and v i = t i for i > n.
We convert φ to a negotiation N φ . N φ has the same structure as that of N φ which was constructed in Theorem 3 apart from some change in arcs and participation of processes in nodes.

Paritcipation changes are the following : The node Lone vi associated with each variable v i of φ now involve two processes namely V i and V i-1 . (Lone v1 has only V 1 as process). Both of the outcomes, true and false associated with Lone vi take V i-1 to n f while true takes V i to T Lone vi,1 and false takes V i to F lone vi,1 .

Change in arcs is the following: The outcome vton of F Lone vi,r where r = |S i,f | and T Lone vi,r where r = |S i,t | takes V i to Lone vi+1 (Except for i = n + k for which there is no change). We now define timing function γ as follows:

γ(Lone vi , true) = [2 n-i , 2 n-i ] for all i ≤ n and γ(n, r) = 0 for all other combination of nodes and outcomes.

The claim is that maxtime(N φ ) = odd iff x n = 1 in the lexicographically largest satisfying assignment of φ.

To prove the claim, we prove a stronger outcome that there is a run which is final and takes time t iff there is a satisfying assignment to φ whose lexicographic value is same as t in binary.

To prove the forward implication, consider any run σ which is final. Now, just like the proof in 3, the process V i must have choosen either true or false at node Lone vi . The assignment f , corresponding to this outcome chosen by each V i is essentially the one whose lexicographic value is same as t. The fact that this assignment is satisifable follows from the proof of theorem 3. To show that that lexicorgraphic value is same, first of all the observe that time taken t can be written as 2 n-i1 + 2 n-i2 + ... + 2 n-i k where V ij are those processes which chose true at Lone vi . Moreover i j ≤ n, which implies that all these variables are also present in φ. Also the the contribution of a variable x ij (which is same as v ij )

in lexicographic value will be 2 n-ij which is same as its contribution in t. Hence the forward implication.

For backward implication, consider any satisfiable assignment f of φ. Since φ and φ are equisatisfiable hence there will exist an satisfiable assignment f to φ , such that f (x i ) = f (v i ) for i ≤ n. Now following the proof of Thm. 3, it is easy see that the run σ corresoponding to the assignment f will be final. Moreover the time taken for the path will be 2 n-i1 + 2 n-i2 + ... + 2 n-i k where f (v i k ) = true. Since all these i j ≤ n, these variables will also be present in φ and their contribution in lexicographic value of f would also be 2 n-ij . And hence the backward implication.

This proves the claim and shows that maxtime(N φ ) = odd iff x n = 1 in the lexicographically largest satisfying assignment of φ.

Finally, we note that if we were interested in the optimization and not the decision variant of the problem, the above proof can be adapted to show that the optimization variants are OptP-Complete (as defined in [START_REF] Mark | The complexity of optimization problems[END_REF]).

Appendix B: Sound Negotiations

Sound negotiations are negotiations in which every run can be extended to a final run, as in Fig. 1. In this section, we show that maxtime(N ) can be computed in PTIME for sound negotiations, hence giving PTIME complexities for the maxtime(N ) ≤ T ? and maxtime(N ) = T ? questions. However, we show that mintime(N ) ≤ T is NP-complete for sound negotiations, and that mintime(N ) = T is DP-complete, even if T is given in unary.

Consider the graph G N of a negotiation N . Let π = (n 0 , (p 0 , r 0 ), n 1 ) • • • (n k , (p k , r k ), n k+1 ) be a path of G N . We define the maximal execution time of a path π as the value δ + (π) = i∈0..k γ + (n i , r i ). We say that a path π = (n 0 , (p 0 , r 0 ), n 1 ) • • • (n , (p , r ), n +1) is a path of some run ρ = (M 1 , µ 1 ) Proof. Let us first prove that maxtime(N ) ≥ max π∈P aths(G N ) δ + (π)+γ + (n f , r f ).

(n1,r 1 ) -→ • • • (M k , µ k ) if r 0 , . . . ,
Consider any path π of G N , ending in some node n. First, as N is sound, we can compute a run ρ π such that π is a path of ρ π , and ρ π ends in a configuration in which n is enabled. We associate with ρ π the timed run ρ + π which associates to every node the latest possible execution date. We have easily δ(ρ + π ) ≥ δ(π), and then we obtain max π∈P aths(G N ) δ(ρ + π ) ≥ max π∈P aths(G N ) δ(π). As maxtime(N ) is the maximal duration over all runs, it is hence necessarily greater

than max π∈P aths(G N ) δ(ρ + π ) + γ + (n f , r f ) We now prove that maxtime(N ) ≤ max π∈P aths(G N ) δ + (π) + γ + (n f , r f ).
Take any timed run ρ = (M 1 , µ 1 )

(n1,r1) -→ • • • (M k , µ k )
of N with a unique maximal node n k . We show that there exists a path π of ρ such that δ(ρ) ≤ δ + (π) by induction on the length k of ρ. The initialization is trivial for k = 1. Let k ∈ N.

Because n k is the unique maximal node of ρ, we have δ(ρ) = max p∈Pn k µ k-1 (p)+ γ + (n k , r k ). We choose one p k-1 maximizing µ k-1 (p). Let < k be maximal index of a decision involving process p k-1 (i.e. p k-1 ∈ P n ). Now, consider the timed run ρ subword of ρ, but with n as unique maximal node (that is, it is ρ where nodes n i , i > has been removed, but also where some nodes n i , i < have been removed if they are not causally before n (in particular, P ni ∩ P n = ∅).

By definition, we have that δ(ρ) = δ(ρ ) + γ + (n , r ) + γ + (n k , r k ). We apply the induction hypothesis on ρ , and obtain a path π of ρ ending in n such that δ(ρ

) + γ + (n , r ) ≤ δ + (π ). It suffices to consider the path π = π (n , (p k-1 , r ), n k ) to prove the inductive step δ(ρ) ≤ δ + (π) + γ + (n k , r k ). Thus maxtime(N ) = max δ(ρ) ≤ max π∈P aths(G N ) δ + (π) + γ + (n f , r f ).
Lemma 1 gives a way to evaluate the maximal execution time. This amounts to finding a path of maximal weight, which is a standard PTIME graph problem that can be solved using standard max-cost calculation. Proof. First of all, we compute a topological order < on nodes of the graph G N , that is for all n ∈ X (n, r), we have n < n . This can be done in

O(|N | + |X |) [3].
Then, we follow the total order < on nodes of G N and attach to each node n a maximal time δ + (n) for runs ending at node n in the following way: δ + (n 0 ) = 0 and for each node n, we let δ A direct consequence is that maxtime(N ) ≤ T and maxtime(N ) = T problems can be solved in polynomial time when N is. Notice that if N is deterministic but not sound, then Lemma 1 does not hold: we only have an inequality.

+ (n) = max n |(n ,(p,r),n)∈G N (γ + (n , r) + δ + (n )). It
We now turn to mintime(N ). We show that it is strictly harder to compute for sound negotiations than maxtime(N ).

Theorem 5. mintime(N ) ≤ T is NP-complete in the strong sense for sound acyclic negotiations, even if N is very weakly non-deterministic.

Proof. First, we can decide mintime(N ) ≤ T in NP. Indeed, one can guess a final (untimed) run ρ of size ≤ |N |, consider ρ -the timed run corresponding to ρ where all outcomes are taken at the earliest possible dates, and compute in linear time δ(ρ -), and check that δ(ρ -) ≤ T .

The hardness part is obtained by reduction from the Bin Packing problem.

We give a set U of items, a size s(u) ∈ N for each u ∈ U , a positive integer B defining a bin capacity. The bin packing problem asks whether there exists a partition of U into k disjoint subsets U 1 , U 2 ...U k such that the sum of sizes of items in each U i is smaller or equal to B. Bin Packing is known to be NP-Complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] in the strong sense, that is even if the constants are given in unary. Let us now show that every instance of Bin Packing can be reduced to a min-time problem for very-weakly non-deterministic sound negotiations.

Given a set U of items, a bin capacity B and number k of bins, we build a timed negotiation N U,k with k processes u i,1 , u i,2 , ..., u i,k for each item u i ∈ U , and k additional processes v 1 , v 2 , ..v k . The timing of a process v i will encode the total size of items put in the bin i. We then show that Bin Packing with items U , k bins, and a bound B has a solution iff mintime(N U,k ) ≤ B.

We describe the negotiation N U,k layer by layer. In total we will have |U | + 1 layers: intuitively, we will consider one item in each layer, and make one global decision to decide in which bin this item goes. The first layer has only the initial node n 0 . The set of processes involved in n 0 is the set of all processes. The outcomes from the initial node are r 1,1 , . . . , r 1,k , which tell in which bin 1, . . . , k the first item is placed. Outcome r 1,i leads process u i,1 and v i to node YES 1 i .

It leads processes u j,1 and v j to NO Inductively, layer i is defined as in Fig 6 . Node n i contains processes u j, for all j > i and all . It is similar to n 0 , with outcome r i+1,1 , . . . , r i+1,k . Outcome r i+1, leads process u i+1, to node Y es i+1 , and process u i+1,j to N o i+1 j for all j = . Other processes u i ,j with i > i + 1 are sent to n i+1 . The associated timings are [0, 0].

Node Garbage i collects all nodes u ,j with < i. There is a unique outcome, with associated timing [0, 0], leading all processed to Garbage i+1 .

Node YES i j has a unique outcome r, with timing γ(YES i j , r) = [s(u i ), s(u i )],

and with X (YES i j , r) = {YES i+1 j , No i+1 j }. That is, node YES i j is non deterministic, and it awaits the decision from u i+1,j to known whether it will go to YES i+1 j or to No i+1 j . Last, u i,j is sent to node Garbage i+1 . This allows each nodes to have at least one deterministic process, as v i only are non-deterministic.

In the same way, NO i j has a unique outcome r, timed with γ(NO i j , r) = [0, 0], and with X (NO i j , r) = {YES i+1 j , No i+1 j }. It sends process u j,i to Garbage For maximal execution time, we keep for each subset X ∈ S i and each node n ∈ X, the maximal time f i (n, X) ∈ N associated with n and X. From S i+1 and f i , we inductively compute f i+1 in the following way: for all X ∈ S i with successor Y ∈ S i+1 for outcomes (r p ) p∈P , we denote f i+1 (Y, n, X) = max p∈P (n) f i (X, n(X, p))+γ + (n(X, p), r p ). If there are several choices of (r p ) p∈P leading to the same Y , we take r p with the maximal f i (X, n(X, p))+γ + (n(X, p), r p ). We then define f i+1 (Y, n) = max X∈Si f i+1 (Y, n, X). Again, the initialization is trivial, with f 0 ({n 0 }, n 0 ) = 0. The maximal execution time of N is f ({n f }, n f ). k * = max X∈ i Si |X| ≤ k. We say that N is k * -thread bounded, meaning that there cannot be more that k * nodes in the same context X of any layer.

Usually, k * is strictly smaller than k = max i |N i |, as N i = X∈Si X. Consider again the Brexit example Figure 1. We have (k + 1) = 7, while we have the depth d(N ) = 6, the negotiation is k * = 3-thread bounded (k * is bounded by the number of processes), and the number of contexts is at most C(N ) = 4 (EU chooses to enforce backstop or not, and Pa chooses to go to court or not).

Minimal Execution Time

As with sound negotiations, computing minimal time is much harder than computing the maximal time for k-layered negotiations: Proof. We will remember for each layer i a set T i of functions τ from nodes N i of layer i to a value in {1, . . . , T, ⊥}. Basically, we have τ ∈ T i if there exists a path ρ reaching X = {n ∈ N i | f (n) = ⊥}, and this path reaches node n ∈ X after τ (n) time units. As for S i , for all p, we should have a unique node n(τ, p) such that p ∈ n(f, p) and τ (n(τ, p)) = ⊥. Again, it is easy to initialize T 0 = {τ 0 }, with τ 0 (n 0 ) = 0, and τ 0 (n) = ⊥ for all n = n 0 .

Inducively, we build T i+1 in the following way: τ i+1 ∈ T i+1 iff there exists a τ i ∈ T i and r p ∈ R n(τi,p) for all p ∈ P such that for all n with τ i+1 (n) = ⊥, we have τ i+1 (n) = max p τ i (n(τ i , p)) + γ(n(τ i , p), r p ).

We have that the minimum execution time for N is min τ ∈Tn τ (n τ ), for n the depth of n f . There are at most T k functions τ in any T i , and there are at most |N | layers to consider, giving the complexity.

As with Thm. 6, we can more accurately state the complexity as O(d(N ) •

C(N ) • ||R|| k * • T k * -1
). The k * -1 is because we only need to remember minimal functions τ ∈ T i : if τ (n) ≥ τ (n) for all n, then we do not need to keep τ in T i .

In particular, for the knapsack encoding in the proof of Thm. Notice that if k is part of the input, then the problem is strongly NP-hard, even if T is given in unary, as e.g. encoding bin packing with k bins result to a k + 1-layered negotiations.

[ 5 , 5 ]

 55 , and PM can meet EU immediatly γ(meet) = [0, 0]. In case of court action, PM needs to spend 2 weeks in court γ(c-meet) = [2, 2], and depending on the court delay and decision, Pa needs between 3 (court overules recess) to 5 (court confirms recess) weeks, γ(defend) = [3, 5]. Agreeing on a deal can take anywhere from 2 weeks to 2 years (104 weeks): γ(deal agreed) = [2, 104] -some would say infinite time is even possible! It needs more time with the backstop, γ(deal w/backstop) = [5, 104]. All others outcomes are assumed to be immediate, i.e., associated with [0, 0].

Proposition 3 .

 3 We apply the induction hypothesis on ρ , and obtain a path π of ρ ending in nsuch that δ(ρ ) + γ + (n , r ) ≤ δ + (π ). It suffices to consider the path π = π .(n , (p k-1 , r ), n k ) to prove the inductive step δ(ρ) ≤ δ + (π) + γ + (n k , r k ). Thus maxtime(N ) = max δ(ρ) ≤ max π∈P aths(G N ) δ + (π) + γ + (n f , r f ).Lemma 1 gives a way to evaluate the maximal execution time. This amounts to finding a path of maximal weight in an acyclic graph, which is a standard PTIME problem that can be solved using standard max-cost calculation. Computing the maximal execution time for an acyclic sound negotiation N = (N, n 0 , n f , X ) can be done in time O(|N | + |X |).

Theorem 5 .

 5 mintime(N ) ≤ T is NP-complete in the strong sense for sound acyclic negotiations, even if N is very weakly non-deterministic.Proof (sketch). First, we can decide mintime(N ) ≤ T in NP. Indeed, one can guess a final (untimed) run ρ of size ≤ |N |, consider ρ -the timed run corresponding to ρ where all outcomes are taken at the earliest possible dates, and compute in linear time δ(ρ -), and check that δ(ρ -) ≤ T .

Proposition 4 .

 4 The mintime(N ) = T ? decision problem is DP-complete for sound acyclic negotiations, even if it is very weakly non-deterministic.

Theorem 6 .

 6 Let k ∈ N + . Computing the maximum execution time for a klayered acyclic negotiation N can be done in PTIME. More precisely, the worstcase time complexity is O(|P | • |N | k+1 ). Proof (Sketch). The first step is to compute S i layer by layer, by following its inductive definition. The set S i is of size at most 2 k , as |N i | < k by definition of k-layeredness. Knowing S i , it is easy to build S i+1 by induction. This takes time in O(|P ||N | k+1 ) : We need to consider all k-uple of outcomes for each layer. There can be |N | k such tuples. We need to do that for all processes (|P |), and for all layers (at most |N |).

  We can bound the complexity precisely byO(d(N ) • C(N ) • ||R|| k * ), with: d(N ) ≤ |N | the depth of n f ,that is the number of layers of N , and ||R|| is the maximum number of outcomes of a node,-C(N ) = max i |S i | ≤ 2 k ,which we will call the number of contexts of N , and which is often much smaller than 2 k .

Figure 1 .

 1 We have (k + 1) = 7, while we have the depth d(N ) = 6, the negotiation is k * = 3-thread bounded (k * is bounded by the number of processes), ||R|| = 2, and the number of contexts is at most C(N ) = 4 (EU chooses to enforce backstop or not, and Pa chooses to go to court or not).

Theorem 7 .

 7 Let k ≥ 6. The M in ≤ T problem is NP-Complete for k-layered acyclic negotiations, even if the negotiation is sound and very weakly non-deterministic. Proof. One can guess in polynomial time a final run of size ≤ |N |. If the execution time of this final run is smaller than T then we have found a final run witnessing mintime(N ) ≤ T . Hence the problem is in NP.

Fig. 5 .

 5 Fig. 5. The negotiation encoding Knapsack

Theorem 8 .

 8 Let k ∈ N. Given a k-layered negotiation N and T written in unary, one can decide in PTIME whether the minimum execution time of N is ≤ T . The worst-case time complexity is O(|N | • |P | • (T • |N |) k ).

Theorem 3 .

 3 Appendix A: Deterministic NegotiationsWe start by considering the class of deterministic acyclic negotiations. We show that both maximal and minimal execution time cannot be computed in PTIME (unless NP=PTIME), as the threshold problems are (co-)NP-complete. The mintime(N ) ≤ T decision problem is NP complete, and the maxtime(N ) ≤ T decision problem is co-NP complete for acyclic deterministic timed negotiations.

Fig. 4 .Proposition 2 .

 42 Fig. 4. Structure of N φ,φ

  r is a subword of r 1 , . . . , r k . Lemma 1. Let N be an acyclic and sound timed negotiation. Then maxtime(N ) = max π∈P aths(G N ) δ + (π) + γ + (n f , r f ).

Proposition 3 .

 3 Computing the maximal execution time for an acyclic sound negotiation N = (N, n 0 , n f , X ) can be done in time O(|N | + |X |).

  is easy to see that δ + (n) is the maximal δ(π) over all paths π from n 0 to n. As every transition of G N is considered only once, the computation of δ + can be done in O(|N | + |X |). It then suffices to return δ + (n f ) + γ + (n f , r f ).

Fig. 6 .

 6 Fig. 6. Layer i of the very weakly non-deterministic N (U, k)

i+1 . from n 0 is 3 * B 1 + 1 .

 311 So mintime(N P 1 ,P 2 ) = 2 * B 2 + 3 * B 1 + 1. Hence this leaves us with the only case when P 1 satisfies Bin-Packing and P 2 satisfies Non-Bin-Packing for which we already know that the min time taken is 3 * B 1 + 2 * B 2 + 2 from the reverse implication.An open question is whether the minimal execution time can be computed in PTIME if the negotiation is both sound and deterministic. The reduction to bin packing does not work with deterministic (and sound) negotiations. is a Y ⊆ N ext(X, (r n ) n∈X ) such that every process p is in exactly one node n(Y, p) of Y . All nodes of N ext(X, (r n ) n∈X ) are at depth i + 1, and thus there are at most k nodes in N ext(X, (r n ) n∈X ). There are thus at most 2 k subset Y ⊆ N ext(X, (r n ) n∈X ) and we can check them one by one.

  That is, for all nodes (at most |N |), we have to consider every k-uple of outcomes, and there are at most |N | k of them, and every process to compute the max, and the complexity is still in O(|P | • |N | k+1 ). We can bound the complexity precisely by O(d(N ) • C(N ) • ||R|| k * ), with: d(N ) ≤ |N | the depth of n f , that is the number of layers of N , and ||R|| is the maximum number of outcomes of a node, -C(N ) = max i |S i | ≤ 2 k , which we will call the number of contexts of N , and which is often much smaller than 2 k .

Theorem 7 .Theorem 8 .

 78 Let k ≥ 6. The M in ≤ T problem is NP-Complete for k-layered acyclic negotiations, even if the negotiation is sound and very weakly non-deterministic. Proof. One can guess in polynomial time a final run of size ≤ |N |. If the execution time of this final run is smaller than T then we have found a final run witnessing M in(N ) ≤ T . Hence the problem is in NP. Let us now show that the problem is NP-hard. We proceed by reduction from the knapsack decision problem. Let us consider a set of items U = {u 1 , . . . u n } of respective values v 1 , . . . v n and weight w 1 , . . . , w n and a knapsack of maximal capacity W . The knapsack problem asks, given a value V whether there exists a subset of items U ⊆ U such that ui∈U v i ≥ V and such that ui∈U w i ≤ W . Let k ∈ N. Given a k-layered negotiation N and T written in unary, one can decide in PTIME whether the minimum execution time of N is ≤ T . The worst-case time complexity is O(|N | • |P | • (T • |N |) k ).

  7, we have k * = 3, ||R|| = 2 and C(N ) = 4.

  the set of intervals with endpoints that are non-negative integers or ∞.

	For
	convenience we only use closed intervals in this paper (except for ∞), but the
	results we show can also be extended to open intervals with some notational
	overhead. Intuitively, outcome r can be taken at a node n with associated time
	interval [a, b] only after a time units have elapsed from the time all processes
	contributing to n are ready to engage in n, and at most b time units later.
	Definition 6. A timed negotiation is a pair (N , γ) where N is a negotiation,
	and γ : N ×R → I associates an interval to each pair (n, r) of node and outcome
	such that r ∈ R

n . For a given node n and outcome r, we denote by γ -(n, r) (resp.

  on Theory of Computing, STOC '82, pages 255-260, New York, NY, USA, 1982.

	ACM.
	17. Robert H. Sloan and Ugo A. Buy. Reduction rules for time petri nets. Acta Inf.,
	33(7):687-706, 1996.

  -CNF form using Tseitin transformation. Let the new variables introduced be called t 1 , t 2 , ...t k . So φ(x 1 , x 2 , ...x n ) is equisatisfiable to 3-CNF φ (v 1 , v 2 , ...v n , v n+1 , ...v n+k ) where

  1 j for every j = i. Last, it leads all other processes in {u j,m | j > 1, 1 ≤ m ≤ k} to node n 1 . Intuitively, moving to node YES 1 i means that item u 1 is placed in bin i. The second layer has 2k + 1 nodes:

	YES 2 1 . . . YES 2 k , NO 2 1 . . . NO 2

k and n 1 . The timing of outcome r 1,i from node n 0 is γ(n 0 , r 1,i ) = [0, 0].

the authors of[START_REF] Esparza | Static analysis of deterministic negotiations[END_REF] acknowledged the issue with their algorithm for mintime.

Fig. 5. A part of N φ . Here if i > n, then timing with arcs true and false will be [0, 0].

The last layer has only node n f . Nodes Y es k i and N o k i both have a single outcome which take all their processes to n f .

The timing function γ is defined as follows: γ(Y es i j , r i ) = [s(u i ), s(u i )] and γ(n, r) = [0, 0] for all other node and outcome r.

We now prove that M inT ime(N U,k ) ≤ B iff the answer to Bin Packing is positive. The maximal execution time over runs ρ of N U,k is the maximal value of all valuations µ(v j ) and µ(u i,j ), with i ∈ 1..|U |, j ∈ 1..k. Take the valuation µ at the last step before (n f , r f ). Consider t = max j µ(v j ). We have easily that µ(u i,j ) ≤ t for all i, j by construction, because each u i,j had the same timing as v j before reaching a garbage node. Now, we have µ(v j ) = (Yes i j ,ri)∈ρ s(u i ).

Hence, δ(ρ) = max j∈1..k µ(v j ). That is, mintime(N (U, B, k) ≤ B iff there is a path ρ such that µ(v j ) = (Yes i j ,ri)∈ρ s(u i ) ≤ B for all j, ie there exists a valuation such that each item is in one bin, and no bin exceeds its bound B.

Last, we now show that N U,k is a very weakly non-deterministic, sound and layered negotiations. First, the only processes that have non-deterministic transitions are processes v 1 , . . . v k , from Y es i j and N O i j nodes. However, both nodes also have the same deterministic process u i j . Thus N U,k is very weakly nondeterministic. Let us now prove soundness. The only choices are made from node n i , the rest just follow in a unique way. From any configuration M , let i such that M (u i+1 , j) = {n i } for some j. By construction, i is unique. We can then do steps r i+1,1 . . . r n,1 , that is chosing to place items i + 1, . . . , n to the first bin. The steps from other processes are uniquely derived, and all processes reach n f . The layeredness comes from the definition. Actually, N U,k is 2k + 2-layered, for k the number of bins. However, as k is part of the input, it does not fall in our k-layered restriction.

We show that mintime(N ) = T is harder to decide than mintime(N ) ≤ T :

In N U 1 ,B 1 ,k1 , we add a new node n 0 with a single outcome r which now acts as the first node. The older n 0 is now called n 0 . We also add a new process a 1 , which goes to another new node n a1 (has only a 1 as process) from n 0 for its single outcome r. Outcome r sends all other processs from n 0 to n 0 . Node n a1 has a single outcome r 1 which takes a 1 to n f . Also, γ(n a1 , r

, we add a new node n 0 with two outcomes r and r new which now acts as the first node. The older n 0 is now called n 0 . We also add a new process a 2 , which goes to another new node n a2 (has only a 2 as process) from n 0 for its outcome r. Outcome r sends all other processes from n 0 to n 0 . Node

Now we merge the two negotiations N U 1 ,B 1 ,k1 and N U 2 ,B 2 ,k2 in the same way as we merged in Corollary 2, merging the

and making other similar changes we did in Corollary 2. We call this new negotiation N P 1 ,P 2 . Note the negotiation N P 1 ,P 2 is sound as well as very weakly non-deterministic.

The claim is that mintime

We first show the reverse implication i.e if (P

For forward implication, we consider all four scenerios of (P 1 , P 2 ) and argue that P 1 satisfies Bin-Packing and P 2 satisfies Non-Bin-Packing is the only possibility.

First let's assume that P 1 does not satisfy Bin-Packing. Then the mintime to complete the structure above n sep is (≥ 3 * (B 1 + 1)). This is beacuse processes In this section, we consider k-layeredness (see Section 2), a syntactic property that can be efficiently verified (it suffices to compute the depth of each node, which can be done in polynomial time).

Algorithmic properties

Let k be a fixed integer. We first show that Reachability, Soundness and maximum execution time can be checked in PTIME for k-layered negotiations (the two first results were stated in Section 2). Let N i be the set of nodes at layer i. We define for every layer i the set S i of subsets of nodes X ⊆ N i which can be jointly enabled and such that for every process p, there is exactly one node n(X, p) in X with p ∈ n(X, p). Formally, we define S i inductively. We start with S 0 = {n 0 }. We then define S i+1 from the contents of layer S i : we have Y ∈ S i+1 iff n∈Y P n = P and there exist X ∈ S i and an outcome r m ∈ R m for every m ∈ X, such that n ∈ X (n(X, p), p, r m ) for each n ∈ Y and p ∈ P n . For reachability, we just need to check whether layer S d = {n f }, where d is the depth of n f .

For soundness, let us denote by N ext(X, (r n ) n∈X ) the set of nodes that are successors of nodes in X after outcomes (r n ) n∈X . We need to check that for all layer i, for all set X ∈ S i and all tuple of outcomes (r n ) n∈X , there

We build a negotiation with 2n processes P = {p 1 , . . . p 2n }. Intuitively, p i , i ≤ n will serve to encode the value as timing, while p i , i > n will serve to encode the weight as timing. We set the set of nodes

be used to remember that item i is placed in the knapsack and that its value (resp. weight) needs to be added. For all i, node n L,1,i (resp. n R,1,i ) has a unique possible outcome, b i (resp. c i ). Nodes of the form n L,0,i remember that item i has not been placed in the knapsack, and they have outcome a i . Nodes of the form n R,0,i remember that item i has not been placed in the knapsack, and they all have outcome 0. This outcome does not change the execution time, matching the fact that the current weight and value of the knapsack is not increased.

Last, nodes of the form C i will just remember the items that have already been considered. These nodes have two outputs, yes and no, telling whether the item i should be placed in the knapsack or not, consistently for weight and value processes.

We set P n0 = P n f = P , and for other nodes n L,0,i ,

We define the transition relation as follows: X (n 0 , yes, p 1 ) = {n L,1,i }, and X (n 0 , no, p 1 ) = {n L,0,1 }, such that process p 1 remembers that the item is picked/notpicked.

In the same way, X (n 0 , no, p n+1 ) = {n R,0,1 } and X (n 0 , yes, p n+1 ) = {n R,1,1 } for process p i+1 . Hence both process p 1 , p n+1 will have the same information about whether the first item is picked or not. Finally, for every k ∈ 2..n, we define

Other layers are similar: for i ∈ 1..n, we have X (C i , no, p i ) = {n L,0,i+1 } X (C i , yes, p i ) = {n L,1,i+1 }, Similarly, for every i ∈ 1..n, X (C i , no, p i+n ) = {n R,0,i+1 }, and X (C i , yes, p i+n ) = {n R,1,i+1 }. We set X (C i , no, p j ) = X (C i , yes, p j ) =

The most interesting set of transitions are to interface n L,0,i , n L,1,i , n R,0,i , n R,1,i with the next layer, in a non deterministic way because they dont know whether the next item will be picked or not: X (n L,0,i , a i , p j ) = X (n L,1,i , b i , p j ) = {n L,0,i+1 , n L,1,i+1 } for j ∈ 1..i and, X (n R,0,i , 0, p j ) = X (n R,1,i , c i , p j ) = {n R,0,i+1 , n R,1,i+1 } for

Last, all processes synchronize on n f by setting )X (n L,0,n , 0,

We now have to set timing constraints for outcomes. Outcomes 0, yes and no are associated with [0, 0]. Outcome c i is associated with [w i , w i ], the weight of u i . Last, outcome b i is associated with a more complex function, such that

, where v max is the largest value of an item, and V is the total value we want to reach at least. Also, we set [ (vmax)W n•vmax-V , vmaxW n•vmax-vi ] for outcome a i . We set T = W , the maximal weight of the knapsack. Now, consider a final run ρ in N . The only choice is about yes, no from C i . Let I be the set of indices such that yes is the outcome from all C i in this path. We obtain δ

i.e. i∈I v i ≥ V . Hence, there exists a path ρ with δ(ρ) ≤ T = W iff there exists a set of items of weight less than W and of value more than V . So, given a knapsack of size n, a value V and a weight limit W one can build a negotiation N Knap V with O(3n + 2) nodes. We can encode all weights with log(v max .W ) + log(n.v max ) bits. One can notice that N Knap V is 5-layered and sound. However, it is not (weakly) non-deterministic because of nodes n L,0,i , n L,1,i , n R,0,i , n R,1,i .

It is easy to add two processes V (resp. W ), present in all nodes n L,0,i , n L,1,i (resp n R,0,i , n R,1,i ), and make process P i (resp. P n+i leave these nodes, deterministically leading to a new node garbage i+1 at layer i+1. Then the negotiation is very weakly deterministic, and 6-layered.

Following the same lines as for the proofs of Propositions 2 and 4, a consequence of Theorem 7 is that the M in = T problem is in DP for k-layered acyclic negotiations.

It is well known that Knapsack is weakly NP-hard, that is it NP-hard only when weights/values are given in binary. This means that Thm. 7 shows that minimum execution time ≤ T is NP-hard only when T is given in binary. We can actually show that for k-layered negotiations, the mintime(N ) ≤ T problem can be decided in PTIME if T is given in unary (i.e. if T is not too large):