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) < Tis NP-complete.maxtime(N) < Tis 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) < Tis NP-complete (even for very weakly non-deterministic negotiations).mintime(N) = Tis DP-complete.- For k-layered acyclic negotiations (k fixed):
maxtime(N)can be computed in PTIME.mintime(N) < Tis NP-complete (even if sound and very weakly non-deterministic).mintime(N) < Tcan 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