文章基本信息

标题：Soundness in negotiations
本地全文：下载
作者：Walukiewicz, Igor ; Muscholl, Anca ; Kuperberg, Denis 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2018
卷号：14
期号：1
语种：English
出版社：Technical University of Braunschweig
摘要：Negotiations are a formalism for describing multiparty distributedcooperation. Alternatively, they can be seen as a model of concurrency withsynchronized choice as communication primitive. Well-designed negotiations mustbe sound, meaning that, whatever its current state, the negotiation can stillbe completed. In earlier work, Esparza and Desel have shown that decidingsoundness of a negotiation is Pspace-complete, and in Ptime if the negotiationis deterministic. They have also extended their polynomial soundness algorithmto an intermediate class of acyclic, non-deterministic negotiations. However,they did not analyze the runtime of the extended algorithm, and also left openthe complexity of the soundness problem for the intermediate class. In thefirst part of this paper we revisit the soundness problem for deterministicnegotiations, and show that it is Nlogspace-complete, improving on the earlieralgorithm, which requires linear space. In the second part we answer thequestion left open by Esparza and Desel. We prove that the soundness problemcan be solved in polynomial time for acyclic, weakly non- deterministicnegotiations, a more general class than the one considered by them. In thethird and final part, we show that the techniques developed in the first twoparts of the paper can be applied to analysis problems other than soundness,including the problem of detecting race conditions, and several classicalstatic analysis problems. More specifically, we show that, while these problemsare intractable for arbitrary acyclic deterministic negotiations, they becometractable in the sound case. So soundness is not only a desirable behavioralproperty in itself, but also helps to analyze other properties.
关键词：F.3.2;F.3.1;F.1.2;F.1.1;Computer Science - Logic in Computer Science;Computer Science - Formal Languages and Automata Theory