Timed Negotiations

S. Akshay, Blaise Genest, Loïc Hélouët, Sharvik Mital

TL;DR

This paper introduces "timed negotiations," a model for concurrent systems where decisions have associated time durations. They analyze the complexity of computing minimum and maximum execution times, finding that minimum time is generally harder to compute than maximum time, with complexities ranging up to $\Delta_2^P$-complete.

What Problem Does This Paper Address?

Analyzing complex distributed systems often involves dealing with a vast number of possible states. "Negotiations" offer a model for multiparty decision-making in such systems, with some properties like deadlock-freedom being efficiently solvable. However, these existing models are often qualitative and lack the ability to reason about the time it takes for these negotiations to complete. This paper addresses this gap by introducing "timed negotiations," where outcomes of decisions have associated time intervals. The core problem is to efficiently compute the minimum and maximum possible execution times for these timed negotiations, especially in more general scenarios beyond just sound and deterministic ones.

Methods

The paper extends the existing model of negotiations by associating time intervals with outcomes of decisions at each node. They define semantics for timed runs and introduce the concepts of minimum execution time (mintime) and maximum execution time (maxtime). A significant portion of the work involves analyzing the computational complexity of deciding problems related to these times (e.g., "is mintime <= T?"). They introduce a new class of "k-layered negotiations" which allows for more efficient computation of maxtime. The analysis relies heavily on complexity theory, reducing problems to known NP-hard problems like 3-CNF-SAT and Knapsack to establish lower bounds.

Datasets

Not discussed in the paper. The paper uses a running example (Brexit negotiation) to illustrate concepts, but no formal datasets are used for evaluation.

Key Insights and Ideas

  • Time is Asymmetric: Computing minimum execution time is generally harder than computing maximum execution time. This is a surprising finding that contrasts with some intuitions and existing work.
  • Beyond Soundness and Determinism: The paper shows that the complexity of timed negotiation problems remains high even when relaxing the strict requirements of soundness and determinism, which were limitations of prior work.
  • k-Layered Negotiations: Introducing a structural property (k-layeredness) on negotiations can significantly improve the tractability of computing maximum execution time, making it PTIME for fixed k.
  • Knapsack Connection: The NP-hardness of minimum execution time problems is demonstrated through reductions from the Knapsack problem, highlighting the inherent difficulty.

Key Results

  • For deterministic acyclic negotiations:
  • mintime(N) < T is NP-complete.
  • maxtime(N) < T is co-NP-complete.
  • Equality problems (mintime(N) = T, maxtime(N) = T) are DP-complete.
  • For sound acyclic negotiations:
  • maxtime(N) can be computed in PTIME.
  • mintime(N) < T is NP-complete (even for very weakly non-deterministic negotiations).
  • mintime(N) = T is DP-complete.
  • For k-layered acyclic negotiations (k fixed):
  • maxtime(N) can be computed in PTIME.
  • mintime(N) < T is NP-complete (even if sound and very weakly non-deterministic).
  • mintime(N) < T can be solved in PTIME if T is given in unary (pseudo-PTIME).

Limitations and Future Work

  • Open Question: Whether minimum execution time can be computed in PTIME for deterministic and sound negotiations remains an open question.
  • k-Layeredness: While k-layered negotiations offer algorithmic advantages, the definition of "layered" might require transformations that increase the size of the negotiation.
  • Optimization vs. Decision: The paper focuses on decision problems (e.g., "is time <= T?"). The authors note that optimization variants (finding the exact min/max time) can be related to OptP-completeness, but formal details are omitted.
  • General Negotiations: The results for minimum and maximum execution times are primarily stated for acyclic negotiations, as cycles can lead to infinite maximum times. Extending these results to cyclic negotiations would be a natural next step.

Summary updated

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.
BibTeX
@inproceedings{akshay2020timed,
  author = {S. Akshay and Blaise Genest and Loïc Hélouët and Sharvik Mital},
  title = {{Timed Negotiations}},
  booktitle = {FoSSaCS},
  year = {2020},
  doi = {10.1007/978-3-030-45231-5\_3},
}
Figure